/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2001,2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 */

//  ServiceStoreInMemory.java: An in-memory implementation
//                             of the service store.
//  Author:           James Kempf
//  Created On:       Mon Oct 20 12:36:35 1997
//  Last Modified By: James Kempf
//  Last Modified On: Tue Mar  2 15:32:23 1999
//  Update Count:     472
//

package com.sun.slp;

import java.util.*;
import java.io.*;

/**
 * The ServiceStoreInMemory class implements the ServiceStore interface
 * on in-memory data structures.
 * <details of those structures here>
 *
 * @author James Kempf
 */

class ServiceStoreInMemory extends Object implements ServiceStore {

    /**
     * The BVCollector interface allows various
     * data structures to collect stuff from the BtreeVector.
     *
     * @author James Kempf
     */

    private interface BVCollector {

        // Set the return value.

        abstract void setReturn(ServiceRecordInMemory rec);

    }

    /**
     * The ParserBVCollector class implements a BtreeVector
     * collector for the parser.
     *
     * @author James Kempf
     */

    private class ParserBVCollector extends Object implements BVCollector {

        Parser.ParserRecord prReturns = null;
        private Vector scopes = null;

        ParserBVCollector(Vector scopes) {
            this.scopes = scopes;

        }

        public void setReturn(ServiceRecordInMemory rec) {

            Hashtable services = prReturns.services;
            Hashtable signatures = prReturns.signatures;
            ServiceURL surl = rec.getServiceURL();

            // Add if we don't already have it.

            if (services.get(surl) == null) {
                Vector s = (Vector)rec.getScopes().clone();

                DATable.filterScopes(s, scopes, false);

                // Need to adjust lifetime to reflect the time to live. Don't
                //  set the lifetime if it has already expired.

                long lifetime =
                    (rec.getExpirationTime() -
                     System.currentTimeMillis()) / 1000;

                if (lifetime > 0) {
                    ServiceURL url =
                        new ServiceURL(surl.toString(), (int)lifetime);

                    services.put(surl, s);

                    Hashtable sig = rec.getURLSignature();

                    if (sig != null) {
                        signatures.put(url, sig);

                    }
                }
            }
        }
    }

    /**
     * The AttributeBVCollector class implements a BtreeVector
     * collector for the collecting attribute values by type.
     *
     * @author James Kempf
     */

    private class AttributeBVCollector extends Object implements BVCollector {

        private Hashtable alreadySeen = new Hashtable();
                                                // records already seen.
        private Vector attrTags = null; // tags to match against records
        private Hashtable ht = new Hashtable(); // for collecting attributes.
        private Vector ret = null;              // for returns.

        AttributeBVCollector(Vector attrTags, Vector ret) {
            this.attrTags = attrTags;
            this.ret = ret;

        }

        public void setReturn(ServiceRecordInMemory rec) {

            // If we've got it already, then don't add again.

            if (alreadySeen.get(rec) == null) {
                alreadySeen.put(rec, rec);

                try {
                    findMatchingAttributes(rec, attrTags, ht, ret);

                } catch (ServiceLocationException ex) {

                    Assert.slpassert(false,
                                  "ssim_attrbvc_botch",
                                  new Object[] {ex.getMessage()});
                }
            }
        }
    }

    /**
     * The ScopeBVCollector class implements a BtreeVector
     * collector for the collecting records if scopes match.
     *
     * @author James Kempf
     */

    private class ScopeBVCollector extends Object implements BVCollector {

        private Hashtable alreadySeen = new Hashtable();
                                                // for those we've seen
        private Vector records = null;          // for returns.
        private Vector scopes = null;           // the scopes we're looking for

        ScopeBVCollector(Vector records, Vector scopes) {
            this.records = records;
            this.scopes = scopes;

        }

        public void setReturn(ServiceRecordInMemory rec) {

            // If we've got it already, then don't add.

            if (alreadySeen.get(rec) == null) {
                alreadySeen.put(rec, rec);

                if (scopes == null) {
                    records.addElement(rec);

                } else {

                    // Check scopes.

                    int i;
                    Vector rscopes = rec.getScopes();
                    int len = scopes.size();

                    for (i = 0; i < len; i++) {
                        if (rscopes.contains(scopes.elementAt(i))) {
                            records.addElement(rec);
                            break;

                        }
                    }
                }
            }
        }
    }

    /**
     * The AllBVCollector class implements a BtreeVector
     * collector for collecting all records.
     *
     * @author James Kempf
     */

    private class AllBVCollector extends Object implements BVCollector {

        private Vector records = null;                  // for returns.

        AllBVCollector(Vector records) {
            this.records = records;

        }

        public void setReturn(ServiceRecordInMemory rec) {

            // If we've got it already, then don't add.

            if (!records.contains(rec)) {
                records.addElement(rec);

            }
        }
    }

    /**
     * The List class implements a linked list for storing records
     * in the BtreeVector structure.
     *
     * @author James Kempf
     */

    private class List extends Object {

        ServiceRecordInMemory record = null;
        List next = null;
        List prev = null;

        // Create a new list object.

        List(ServiceRecordInMemory record) {
            this.record = record;

        }

        // Insert a new record after this one. Return the new
        //  record.

        synchronized List insertAfter(ServiceRecordInMemory record) {
            List newRec = new List(record);
            newRec.next = next;
            newRec.prev = this;

            if (next != null) {
                next.prev = newRec;

            }

            this.next = newRec;

            return newRec;

        }

        // Delete this record from the list.

        synchronized void delete() {

            if (next != null) {
                next.prev = prev;
            }

            if (prev != null) {
                prev.next = next;

            }

            prev = null;
            next = null;

        }
    }

    /**
     * The RegRecord class implements a record with the value for the
     * record buckets. It is used as elements in BtreeVector.
     *
     * @author James Kempf
     */

    private class RegRecord extends Object {

        Object value = null;            // the value for these registrations.
        List head = new List(null);     // head of the list always null,
                                        //  never changes.
        // Construct a new one.

        RegRecord(Object value) {
            this.value = value;

        }

        // Add a new record to the buckets, return new element.

        List add(ServiceRecordInMemory rec) {

            return head.insertAfter(rec);

        }

        // For every element in record's list, set the return value in the
        // returns object. Since deletions may have removed everything
        // from this record, return true only if something was there.

        boolean setReturn(BVCollector returns) {

            boolean match = false;
            List l = head;

            for (l = l.next; l != null; l = l.next) {
                ServiceRecordInMemory rec = l.record;
                returns.setReturn(rec);
                match = true;

            }

            return match;
        }

        public String toString() {
            return "<RegRecord value="+value+"list="+head.next+">";

        }
    }

    /**
     * The BtreeVector class stores registrations in sorted order. The
     * Quicksort algorithm is used to insert items and search for something.
     *
     * @author James Kempf
     */

    private class BtreeVector extends Object {

        // Contains the sorted vector.

        private Vector contents = new Vector();

        public String toString() {
            return "<BtreeVector "+contents.toString()+">";

        }

        // Return the contents as a sorted vector of RegRecord.
        //  Note that this doesn't return a copy, so
        //  the vector can be side-effected.

        Vector getContents() {
            return contents;

        }

        // Add the entire contents of the vector to the return record.

        boolean getAll(BVCollector returns) {

            int i, n = contents.size();
            boolean match = false;

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                match = match | rec.setReturn(returns);
            }

            return match;
        }

        // Add a new record to this vector. We also garbage collect any
        // records that are empty. Return the list object added.

        List add(Object value, ServiceRecordInMemory record) {
            RegRecord rec = walkVector(value, true);  // an update...

            // Add the record to this one.

            return rec.add(record);

        }


        // Add only if no element in the vector matches the tag.

        boolean matchDoesNotContain(Object pattern, BVCollector returns) {

            // Go through the vector, putting in anything that isn't equal.

            int i, n = contents.size();
            Vector noMatch = new Vector();
            boolean match = false;

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (!compareEqual(rec.value, pattern)) {

                    // Add to prospective returns.

                    noMatch.addElement(rec);

                }

            }

            // If we got this far, there are some no matches.

            n = noMatch.size();

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)noMatch.elementAt(i);

                match = match | rec.setReturn(returns);

            }

            return match;

        }

        boolean
            matchEqual(Object pattern, BVCollector returns) {

            boolean match = false;

            // We can't walk the vector if the value is an AttributePattern,
            //  because equals doesn't apply.

            if (pattern instanceof AttributePattern) {
                int i, n = contents.size();

                for (i = 0; i < n; i++) {
                    RegRecord rec = (RegRecord)contents.elementAt(i);
                    AttributeString val = (AttributeString)rec.value;
                    AttributePattern pat = (AttributePattern)pattern;

                    if (pat.match(val)) {
                        match = match | rec.setReturn(returns);

                    }
                }
            } else {
                RegRecord rec = walkVector(pattern, false);
                                                        // not an update...

                // If nothing came back, return false.

                if (rec == null) {
                    match = false;

                } else {

                    // Otherwise set returns in the vector.

                    match = rec.setReturn(returns);

                }
            }

            return match;
        }

        boolean
            matchNotEqual(Object pattern, BVCollector returns) {

            // Go through the vector, putting in anything that isn't equal.

            int i, n = contents.size();
            boolean match = false;

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (!compareEqual(rec.value, pattern)) {
                    match = match | rec.setReturn(returns);

                }
            }

            return match;
        }

        boolean
            matchLessEqual(Object pattern,
                           BVCollector returns) {

            // Go through the vector, putting in anything that is
            // less than or equal.

            int i, n = contents.size();
            boolean match = false;

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (!compareLessEqual(rec.value, pattern)) {
                    break;

                }

                match = match | rec.setReturn(returns);
            }

            return match;
        }

        boolean
            matchNotLessEqual(Object pattern,
                              BVCollector returns) {
            // Go through the vector, putting in anything that is not
            // less than or equal. Start at the top.

            int i, n = contents.size();
            boolean match = false;

            for (i = n - 1; i >= 0; i--) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (compareLessEqual(rec.value, pattern)) {
                    break;

                }

                match = match | rec.setReturn(returns);
            }

            return match;
        }

        boolean
            matchGreaterEqual(Object pattern,
                              BVCollector returns) {
            // Go through the vector, putting in anything that is greater
            // than or equal. Start at the top.

            int i, n = contents.size();
            boolean match = false;

            for (i = n - 1; i >= 0; i--) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (!compareGreaterEqual(rec.value, pattern)) {
                    break;

                }

                match = match | rec.setReturn(returns);
            }

            return match;
        }

        boolean
            matchNotGreaterEqual(Object pattern,
                                 BVCollector returns) {
            // Go through the vector, putting in anything that is not
            // than or equal.

            int i, n = contents.size();
            boolean match = false;

            for (i = 0; i < n; i++) {
                RegRecord rec = (RegRecord)contents.elementAt(i);

                if (compareGreaterEqual(rec.value, pattern)) {
                    break;

                }

                match = match | rec.setReturn(returns);
            }

            return match;
        }

        // Binary tree walk the vector, performing the operation. Note that
        //  we use dynamic typing heavily here to get maximum code reuse.

        private RegRecord
            walkVector(Object pattern, boolean update) {

            // Get the starting set of indicies.

            int size = contents.size();
            int middle = size / 2;
            int top = size - 1;
            int bottom = 0;
            RegRecord rec = null;

            top = (top < 0 ? 0:top);

            while (size > 0) {

                // Get the one at the current middle.

                rec = (RegRecord)contents.elementAt(middle);

                // Garbage Collection.
                //  If it was null, then delete. But only if we're
                //  inserting. We leave it alone on lookup.

                if (update) {
                    if (rec.head.next == null) {

                        contents.removeElementAt(middle);

                        size = size - 1;
                        middle = bottom + (size / 2);
                        top = top - 1;

                        top = (top < 0 ? 0:top);

                        continue;
                    }
                }

                // Compare value to record, if equal, return record.
                //  code.

                if (compareEqual(rec.value, pattern)) {
                    return rec;

                } else if (compareLessEqual(pattern, rec.value)) {

                    // Recalculate index. We move left, because the value is
                    // less that the value in the vector, so an equal value
                    // must be to the left. Note that the top is not in the
                    // interval because it has already been checked and
                    // found wanting.

                    top = middle;
                    size = (top - bottom);
                    middle = top - (size / 2);
                    middle = (middle < 0 ? 0:middle);

                    if (middle == top) {

                        // Neither top nor middle are in the interval,
                        // so size is zero. We need to compare with bottom.

                        rec = null;
                        RegRecord trec = (RegRecord)contents.elementAt(bottom);

                        if (update) {
                            rec = new RegRecord(pattern);

                            // If the pattern is equal to bottom, return it.
                            // If the pattern is less than or equal to bottom,
                            // we insert it at bottom. If it is greater
                            // than or equal, we insert it at middle.

                            if (compareEqual(trec.value, pattern)) {
                                return trec;

                            } else if (compareLessEqual(pattern, trec.value)) {

                                // Pattern is less than bottom, so insert
                                // at bottom.

                                contents.insertElementAt(rec, bottom);

                            } else {
                                contents.insertElementAt(rec, middle);

                            }
                        } else {

                            // If it equals bottom, then return bottom rec.

                            if (compareEqual(trec.value, pattern)) {
                                rec = trec;

                            }
                        }

                        break;

                    }

                } else if (compareGreaterEqual(pattern, rec.value)) {

                    // Recalculate index. We move right, because the value is
                    // greater that the value in the vector, so an equal
                    // value must be to the right. Note that the top is not
                    // in the interval because it has already been checked
                    // and found wanting.

                    bottom = middle;
                    size = (top - bottom);
                    middle = bottom + (size / 2);

                    if (middle == bottom) {

                        // Neither bottom nor middle is in the interval,
                        // so size is zero. We need to compare with top.

                        rec = null;
                        RegRecord trec = (RegRecord)contents.elementAt(top);

                        if (update) {
                            rec = new RegRecord(pattern);

                            // If the pattern is equal to the top, we
                            // return the top. If the pattern is greater
                            // then top, we insert it after top, else we
                            // insert it at top.

                            if (compareEqual(trec.value, pattern)) {
                                return trec;

                            } else if (compareGreaterEqual(pattern,
                                                           trec.value)) {

                                // Pattern is greater than top, so insert
                                // after top.

                                int i = top + 1;

                                if (i >= contents.size()) {
                                    contents.addElement(rec);

                                } else {
                                    contents.insertElementAt(rec, i);

                                }
                            } else {

                                // Pattern is less than top, so insert at
                                // top, causing top to move up.

                                contents.insertElementAt(rec, top);

                            }
                        } else {

                            // If it equals top, then return top rec.

                            if (compareEqual(trec.value, pattern)) {
                                rec = trec;

                            }
                        }

                        break;

                    }
                }
            }

            // Take care of update where vector is empty or cleaned out.

            if (update && rec == null) {
                rec = new RegRecord(pattern);

                Assert.slpassert((contents.size() == 0),
                              "ssim_btree_botch",
                              new Object[0]);

                contents.addElement(rec);
            }

            return rec;
        }

        // Add any registrations that match the pattern.

        boolean
            compareEqual(Object target, Object pattern) {

            if (target instanceof Integer ||
                target instanceof Boolean ||
                target instanceof Opaque ||
                target instanceof Long) {
                if (pattern.equals(target)) {
                    return true;

                }

            } else if (target instanceof AttributeString) {

                // If the pattern is an AttributePattern instead of an
                // AttributeString, the subclass method will get invoked.

                if (((AttributeString)pattern).match(
                                                (AttributeString)target)) {
                    return true;

                }

            } else {
                Assert.slpassert(false,
                              "ssim_unk_qtype",
                              new Object[] {pattern.getClass().getName()});
            }

            return false;

        }

        // Add any registrations that are less than or equal to the pattern.

        boolean
            compareLessEqual(Object target, Object pattern) {

            if (target instanceof Integer) {
                if (((Integer)target).intValue() <=
                    ((Integer)pattern).intValue()) {
                    return true;

                }

            } else if (target instanceof AttributeString) {

                if (((AttributeString)target).lessEqual(
                                                (AttributeString)pattern)) {
                    return true;

                }

            } else if (target instanceof Long) {
                if (((Long)target).longValue() <=
                    ((Long)pattern).longValue()) {
                    return true;

                }

            } else if (target instanceof Boolean ||
                       target instanceof Opaque) {
                if (target.toString().compareTo(pattern.toString()) <= 0) {
                    return true;

                }
            } else {
                Assert.slpassert(false,
                              "ssim_unk_qtype",
                              new Object[] {target.getClass().getName()});
            }

            return false;

        }

        // Add any registrations that are greater than or equal to the pattern.

        boolean
            compareGreaterEqual(Object target, Object pattern) {

            if (target instanceof Integer) {
                if (((Integer)target).intValue() >=
                    ((Integer)pattern).intValue()) {
                    return true;

                }

            } else if (target instanceof AttributeString) {

                if (((AttributeString)target).greaterEqual(
                                                (AttributeString)pattern)) {
                    return true;

                }

            } else if (target instanceof Long) {
                if (((Long)target).longValue() >=
                    ((Long)pattern).longValue()) {
                    return true;

                }

            } else if (target instanceof Boolean ||
                       target instanceof Opaque) {
                if (target.toString().compareTo(pattern.toString()) >= 0) {
                    return true;

                }

            } else {
                Assert.slpassert(false,
                              "ssim_unk_qtype",
                              new Object[] {target.getClass().getName()});
            }

            return false;

        }
    }

    /**
     * The InMemoryEvaluator evaluates queries for ServiceStoreInMemory.
     *
     * @author James Kempf
     */

    private class InMemoryEvaluator implements Parser.QueryEvaluator {

        private Hashtable attrLevel;    // Sorted attribute table.
        private BtreeVector attrLevelNot;   // Used for universal negation.
        private Vector inScopes;            // Input scopes.
        private ParserBVCollector returns;  // For gathering results.

        InMemoryEvaluator(Hashtable ht,
                          BtreeVector btv,
                          Vector nscopes) {
            attrLevel = ht;
            attrLevelNot = btv;
            inScopes = nscopes;
            returns = new ParserBVCollector(inScopes);


        }

        // Evaluate the query by matching the attribute tag and
        //  value, using the operator. If invert is true, then
        //  return records that do NOT match.

        public boolean
            evaluate(AttributeString tag,
                     char op,
                     Object pattern,
                     boolean invert,
                     Parser.ParserRecord prReturns)
            throws ServiceLocationException {

            boolean match = false;
            returns.prReturns = prReturns;

            // If inversion is on, then gather all from the
            //  table of registrations that do NOT have this
            //  attribute.

            if (invert) {
                match = attrLevelNot.matchDoesNotContain(tag, returns);

            }

            // Find the table of classes v.s. sorted value vectors.

            Hashtable ttable = (Hashtable)attrLevel.get(tag);

            // If attribute not present, then simply return.

            if (ttable == null) {

                return match;

            }

            // If operator is present, then return all.

            if (op == Parser.PRESENT) {

                // ...but only if invert isn't on.

                if (!invert) {

                    // We use attrLevelNot to get all, because it
                    //  will also pick up keywords. There are
                    //  no keywords in attrLevel because keywords
                    //  don't have any values.

                    match = attrLevelNot.matchEqual(tag, returns);

                }

                return match;
            }

            // We know that the type table is fully initialized with
            //  BtreeVectors for each type.

            // Get the pattern's class. Pattern will not be null because
            //  the parser has checked for it and PRESENT has been
            //  filtered out above.

            Class pclass = pattern.getClass();
            String typeKey = pclass.getName();

            // If the class is AttributePattern, then use AttributeString
            //  instead.

            if (pattern instanceof AttributePattern) {
                typeKey = pclass.getSuperclass().getName();

            }

            // If invert is on, collect those whose types don't match as
            //  well.

            if (invert) {
                Enumeration en = ttable.keys();

                while (en.hasMoreElements()) {
                    String key = (String)en.nextElement();

                    // Only record if the type does NOT match.

                    if (!key.equals(typeKey)) {
                        BtreeVector bvec = (BtreeVector)ttable.get(key);

                        match = match | bvec.getAll(returns);

                    }
                }
            }

            // Get the sorted value vector corresponding to the value class.

            BtreeVector bvec = (BtreeVector)ttable.get(typeKey);

            // Do the appropriate thing for the operator.

            switch (op) {

            case Parser.EQUAL:

                if (!invert) {
                    match = bvec.matchEqual(pattern, returns);

                } else {
                    match = bvec.matchNotEqual(pattern, returns);

                }
                break;

            case Parser.LESS:

                // Note that we've filtered out Opaque, Boolean, and wildcarded
                // strings before calling this method.

                if (!invert) {
                    match = bvec.matchLessEqual(pattern, returns);

                } else {
                    match = bvec.matchNotLessEqual(pattern, returns);

                }
                break;

            case Parser.GREATER:

                // Note that we've filtered out Opaque and Boolean
                // before calling this method.

                if (!invert) {
                    match = bvec.matchGreaterEqual(pattern, returns);

                } else {
                    match = bvec.matchNotGreaterEqual(pattern, returns);

                }
                break;

            default:
                Assert.slpassert(false,
                              "ssim_unk_qop",
                              new Object[] {Character.valueOf((char)op)});
            }

            return match;
        }
    }

    /**
     * The ServiceRecordInMemory class implements the
     * ServiceStore.ServiceRecord interface on in-memory data structures.
     * Each property is implemented as an instance variable.
     *
     * @author James Kempf
     */

    private class ServiceRecordInMemory extends Object
        implements ServiceStore.ServiceRecord {

        private ServiceURL serviceURL = null;   // the service URL
        private Vector attrList = null;         // the attribute list
        private Locale locale = null;           // the locale
        private long timeToDie = 0;             // when the record should die.
        private Vector scopes = null;           // the scopes
        private Hashtable urlSig = null;
                                // URL signature block list, if any.
        private Hashtable attrSig = null;
                                // Attribute signature block list, if any.

        // Create a ServiceStoreInMemory record.

        ServiceRecordInMemory(ServiceURL surl, Vector alist,
                              Vector nscopes, Locale loc,
                              Hashtable nurlSig,
                              Hashtable nattrSig) {

            // All need to be nonnull.

            Assert.nonNullParameter(surl, "surl");
            Assert.nonNullParameter(alist, "alist");
            Assert.nonNullParameter(nscopes, "nscopes");
            Assert.nonNullParameter(loc, "loc");

            serviceURL = surl;
            attrList = attributeVectorToServerAttribute(alist, loc);
            scopes = nscopes;
            locale = loc;
            urlSig = nurlSig;
            attrSig = nattrSig;

            int lifetime = serviceURL.getLifetime();

            timeToDie = lifetime * 1000 + System.currentTimeMillis();
        }

        /**
         * Return the ServiceURL for the record.
         *
         * @return The record's service URL.
         */

        public final ServiceURL getServiceURL() {
            return serviceURL;

        }

        /**
         * Return the Vector of ServerAttribute objects for the record.
         *
         * @return Vector of ServerAttribute objects for the record.
         */

        public final Vector getAttrList() {
            return attrList;

        }

        /**
         * Return the locale of the registration.
         *
         * @return The locale of the registration.
         */

        public final Locale getLocale() {
            return locale;

        }

        /**
         * Return the Vector of scopes in which the record is registered.
         *
         * @return Vector of strings with scope names.
         */

        public final Vector getScopes() {
            return scopes;

        }

        /**
         * Return the expiration time for the record. This informs the
         * service store when the record should expire and be removed
         * from the table.
         *
         * @return The expiration time for the record.
         */

        public long getExpirationTime() {
            return timeToDie;

        }

        /**
         * Return the URL signature list.
         *
         * @return URL signature block list.
         */

        public Hashtable getURLSignature() {
            return urlSig;

        }

        /**
         * Return the attribute signature list.
         *
         * @return Attribute signature list.
         */

        public Hashtable getAttrSignature() {
            return attrSig;

        }


        //
        // Package-local methods.

        final void setAttrList(Vector newList) {
            attrList = newList;

        }

        final void setScopes(Vector newScopes) {
            scopes = newScopes;

        }

        final void setURLSignature(Hashtable nauth) {
            urlSig = nauth;

        }

        final void setAttrSignature(Hashtable nauth) {
            attrSig = nauth;

        }

        public String toString() {

            String ret = "{";

            ret +=
                serviceURL + ", " + locale + ", " + attrList + ", " +
                scopes + ", " + locale + ", " + urlSig + ", " + attrSig;

            ret += "}";

            return ret;
        }

        // Convert a vector of ServiceLocationAttribute objects to
        // ServerAttibutes.

        private Vector
            attributeVectorToServerAttribute(Vector attrs, Locale locale) {
            int i, n = attrs.size();
            Vector v = new Vector();

            for (i = 0; i < n; i++) {
                ServiceLocationAttribute attr =
                    (ServiceLocationAttribute)attrs.elementAt(i);

                v.addElement(new ServerAttribute(attr, locale));
            }

            return v;
        }

    }

    /**
     * A record for scopeTypeLangTable table,
     *
     * @author James Kempf
     */

    private class STLRecord extends Object {

        Hashtable attrValueSort = new Hashtable();
                                // Table of attributes, sorted by value.
        BtreeVector attrSort = new BtreeVector();       // Btree of attributes.
        boolean isAbstract = false;
                                // True if the record is for an abstract
                                //  type.
        STLRecord(boolean isAbstract) {
            this.isAbstract = isAbstract;

        }
    }

    //
    // ServiceStoreInMemory instance variables.
    //

    // ServiceStoreInMemory maintains an invaraint that the record for a
    //  particular URL, set of scopes, and locale is the same object
    //  (pointer-wise) regardless of where it is inserted into the table.
    //  So it can be compared with ==.

    // The scopeTypeLangTable
    //
    //  Keys for this table are scope/service type/lang tag. Values are
    //  STLRecord objects. The STLRecord.attrValueSort field is a Hashtable
    //  where all registrations *having* the attribute tag keys in the
    //  table are contained. This table is used in queries for positive
    //  logical expressions. The STLRecord.attrSort field is a BtreeVector
    //  keyed by attribute. It is used for negative queries to find all
    //  records not having a particular attribute and to find all
    //  registrations. The STLRecord.isAbstract field tells whether the record
    //  is for an abstract type name.
    //
    //  The values in the STLRecord.attrValueSort hashtable are themselves
    //  hashtables. These hashtables are keyed by one of the type keys below,
    //  with  the values being BtreeVector objects. The BtreeVector objects
    //  contain sorted lists of RegRecord objects for Integer,
    //  AttributeString, Boolean, and Opaque types. All records having
    //  values equal to the value in the RegRecord are put into a list
    //  on the RegRecord. There is no STLRecord.attrValueSort
    //  hashtable for keyword attributes because they have no values.
    //  The parser evaluator must use the STLRecord.attrSort hashtable when a
    //  present operator is encountered (the only valid operator with a
    //  keyword).
    //
    //  The values in the STLRecord.attrSort BtreeVector are RegRecord
    //  objects with all records having that attribute tag being on the
    //  RegRecord list.

    // Keys for the various types.

    private final static String INTEGER_TYPE = "java.lang.Integer";
    private final static String ATTRIBUTE_STRING_TYPE =
        "com.sun.slp.AttributeString";
    private final static String BOOLEAN_TYPE = "java.lang.Boolean";
    private final static String OPAQUE_TYPE = "com.sun.slp.Opaque";

    private Hashtable scopeTypeLangTable = new Hashtable();

    //  The urlScopeLangTable
    //
    //  Keys for this table are service url as a string. We don't use
    //  the service URL itself because the hash code depends on the
    //  current service type rather than the original, and we need
    //  to be able to distinguish for a non-service: URL if a
    //  registration comes in with a different service type from the
    //  original. Values are hashtables with key being scope name,
    //  values are hashtables with lang tag key. Ultimate values are
    //  a vector of List objects for lists in which List.record is
    //  inserted. This table is used to perform deletions and for
    //  finding the attributes associated with a particular URL.

    private Hashtable urlScopeLangTable = new Hashtable();

    //  The sstLocales Table
    //
    //  The scope/service type v.s. number of languages. Keys are
    //  the type/scope, values are a hashtable keyed by lang tag.
    //  Values in the lang tag table are Integer objects giving
    //  the number of registrations for that type/scope in the
    //  given locale.

    private Hashtable sstLocales = new Hashtable();

    // A queue of records sorted according to expiration time.

    BtreeVector ageOutQueue = new BtreeVector();

    // Constants that indicate whether there are any registrations.

    private final static int NO_REGS = 0;
    private final static int NO_REGS_IN_LOCALE = 1;
    private final static int REGS_IN_LOCALE = 2;

    // Boot time. For DAAdvert timestamps.

    private long bootTime = SLPConfig.currentSLPTime();

    //
    // ServiceStore Interface Methods.
    //

    /**
     * Return the time since the last stateless reboot
     * of the ServiceStore.
     *
     * @return A Long giving the time since the last stateless reboot,
     *         in NTP format.
     */

    public long getStateTimestamp() {

        return bootTime;

    }

    /**
     * Age out all records whose time has expired.
     *
     * @param deleted A Vector for return of ServiceStore.Service records
     *               containing deleted services.
     * @return The time interval until another table walk must be done,
     *         in milliseconds.
     *
     */

    synchronized public long ageOut(Vector deleted) {

        // Get the ageOut queue and remove all records whose
        // time has popped.

        SLPConfig conf = SLPConfig.getSLPConfig();
        boolean traceDrop = conf.traceDrop();
        Vector queue = ageOutQueue.getContents();

        // Go through the queue, dropping records that
        //  have expired.

        int i;

        for (i = 0; i < queue.size(); i++) {
            RegRecord qRec = (RegRecord)queue.elementAt(i);
            long exTime = ((Long)(qRec.value)).longValue();
            long time = System.currentTimeMillis();

            // Break out when none expire now.

            if (exTime > time) {
                break;

            }

            // Remove the element from the queue.

            /*
             *  Must decrement the index 'i' otherwise the next iteration
             *  around the loop will miss the element immediately after
             *  the element removed.
             *
             *  WARNING: Do not use 'i' again until the loop has
             *           iterated as it may, after decrementing,
             *           be negative.
             */
            queue.removeElementAt(i);
            i--;

            // Deregister all on this list. We
            // take specific care to save the next
            // list element before we deregister, otherwise
            // it will be gone after the deregister.

            List l = qRec.head.next;

            while (l != null) {
                ServiceRecordInMemory rec = l.record;
                ServiceURL url = rec.getServiceURL();
                Vector scopes = rec.getScopes();
                Locale locale = rec.getLocale();

                if (traceDrop) {
                    conf.writeLog("ssim_ageout",
                                  new Object[] {
                        url,
                            rec.getAttrList(),
                            scopes,
                            locale,
                            rec.getURLSignature(),
                            rec.getAttrSignature(),
                            Long.toString(time),
                            Long.toString(exTime)});
                }

                // Save the record for the service table, in case more
                // processing needed.

                deleted.addElement(rec);

                // Save l.next NOW before deregisterInternal() removes it!

                l = l.next;

                String lang = locale.getLanguage();

                deregisterInternal(url, scopes, lang);

            }
        }

        // Calculate the new sleep time. If there's anything in the vector,
        // then use element 0, because the vector is sorted by time
        // and that will be minimum. Otherwise, use the maximum.

        long newSleepy = Defaults.lMaxSleepTime;

        if (queue.size() > 0) {
            RegRecord rec = (RegRecord)queue.elementAt(0);

            newSleepy =
                ((Long)(rec.value)).longValue() - System.currentTimeMillis();

            newSleepy = (newSleepy > 0 ? newSleepy:0);
                                                // it will wake right up, but
                                                // so what?

        }

        return newSleepy;

    }

    /**
     * Create a new registration with the given parameters.
     *
     * @param url The ServiceURL.
     * @param attrs The Vector of ServiceLocationAttribute objects.
     * @param locale The Locale.
     * @param scopes Vector of scopes in which this record is registered.
     * @param urlSig auth block Hashtable for URL signature, or null if none.
     * @param attrSig auth block Hashtable for URL signature, or null if none.
     * @return True if there is an already existing registration that
     *         this one replaced.
     * @exception ServiceLocationException Thrown if any
     *                  error occurs during registration or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public boolean
        register(ServiceURL url, Vector attrs,
                 Vector scopes, Locale locale,
                 Hashtable urlSig, Hashtable attrSig)
        throws ServiceLocationException {

        boolean existing = false;

        String lang = locale.getLanguage();

        // Find an existing record, in any set of scopes having this language.

        ServiceRecordInMemory rec = findExistingRecord(url, null, lang);

        // Deregister from existing scopes, if there is an existing record.

        if (rec != null) {
            if (urlSig != null) {
                // Ensure that the rereg SPI set and the record's SPI set are
                // equivalent. We need only check the URL sigs here, since
                // this operation is equivalent to a dereg followed by a reg,
                // and dereg requires only URL auth blocks.

                Enumeration spis = urlSig.keys();
                while (spis.hasMoreElements()) {
                    Object spi = spis.nextElement();
                    if (rec.urlSig.remove(spi) == null) {
                        throw new ServiceLocationException(
                                ServiceLocationException.AUTHENTICATION_FAILED,
                                "not_all_spis_present",
                                new Object[] {spi});
                    }
                }
                if (rec.urlSig.size() != 0) {
                    // not all required SPIs were present in SrvReg
                    throw new ServiceLocationException(
                                ServiceLocationException.AUTHENTICATION_FAILED,
                                "not_all_spis_present",
                                new Object[] {rec.urlSig.keys()});
                }
            }

            deregisterInternal(url, rec.getScopes(), lang);
            existing = true;

        }

        // Create a new record to register.

        rec = new ServiceRecordInMemory(url, attrs, scopes,
                                        locale, urlSig, attrSig);

        // Add new registration.

        registerInternal(rec);

        return existing;

    }

    /**
     * Deregister a ServiceURL from the database for every locale
     * and every scope. There will be only one record for each URL
     * and locale deregistered, regardless of the number of scopes in
     * which the URL was registered, since the attributes will be the
     * same in each scope if the locale is the same.
     *
     * @param url The ServiceURL
     * @param scopes Vector of scopes.
     * @param urlSig The URL signature, if any.
     * @exception ServiceLocationException Thrown if the
     *                  ServiceStore does not contain the URL, or if any
     *                  error occurs during the operation, or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public void
        deregister(ServiceURL url, Vector scopes, Hashtable urlSig)
        throws ServiceLocationException {

        // Find existing record. Any locale will do.

        ServiceRecordInMemory oldRec =
            findExistingRecord(url, scopes, null);

        // Error if none.

        if (oldRec == null) {
            throw
                new ServiceLocationException(
                                ServiceLocationException.INVALID_REGISTRATION,
                                "ssim_no_rec",
                                new Object[] {url});

        }

        // verify that the dereg SPI set and the record's SPI set are
        // equivalent
        if (urlSig != null) {
            Enumeration spis = urlSig.keys();
            while (spis.hasMoreElements()) {
                Object spi = spis.nextElement();
                if (oldRec.urlSig.remove(spi) == null) {
                    throw new ServiceLocationException(
                                ServiceLocationException.AUTHENTICATION_FAILED,
                                "not_all_spis_present",
                                new Object[] {spi});
                }
            }
            if (oldRec.urlSig.size() != 0) {
                // not all required SPIs were present in SrvDereg
                throw new ServiceLocationException(
                                ServiceLocationException.AUTHENTICATION_FAILED,
                                "not_all_spis_present",
                                new Object[] {oldRec.urlSig.keys()});
            }
        }

        /*
         * Deregister the URL for all locales. Use the recorded service URL
         * because the one passed by the client is possibly incomplete e.g.
         * lacking the service type.
         */

        deregisterInternal(oldRec.getServiceURL(), scopes, null);

    }

    /**
     * Update the service registration with the new parameters, adding
     * attributes and updating the service URL's lifetime.
     *
     * @param url The ServiceURL.
     * @param attrs The Vector of ServiceLocationAttribute objects.
     * @param locale The Locale.
     * @param scopes Vector of scopes in which this record is registered.
     * @exception ServiceLocationException Thrown if any
     *                  error occurs during registration or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public void
        updateRegistration(ServiceURL url, Vector attrs,
                           Vector scopes, Locale locale)
        throws ServiceLocationException {

        String lang = locale.getLanguage();
        ServiceRecordInMemory oldRec =
            findExistingRecord(url, scopes, lang);

        // Error if none.

        if (oldRec == null) {
            throw
                new ServiceLocationException(
                                ServiceLocationException.INVALID_UPDATE,
                                "ssim_no_rec",
                                new Object[] {url});

        }

        // If this is a nonServiceURL, check whether it's registered
        //  under a different service type.

        ServiceType type = url.getServiceType();

        if (!type.isServiceURL()) {
            checkForExistingUnderOtherServiceType(url, scopes);

        }

        // Deregister the URL in this locale.

        deregisterInternal(url, scopes, lang);

        // Create a new record to update.

        ServiceRecordInMemory rec =
            new ServiceRecordInMemory(url, attrs, scopes,
                                      locale, null, null);

        // Merge old record into new.

        mergeOldRecordIntoNew(oldRec, rec);

        // Add the new record.

        registerInternal(rec);
    }

    /**
     * Delete the attributes from the ServiceURL object's table entries.
     * Delete for every locale that has the attributes and every scope.
     * Note that the attribute tags must be lower-cased in the locale of
     * the registration, not in the locale of the request.
     *
     * @param url The ServiceURL.
     * @param scopes Vector of scopes.
     * @param attrTags The Vector of String
     *                  objects specifying the attribute tags of
     *                  the attributes to delete.
     * @param locale Locale of the request.
     * @exception ServiceLocationException Thrown if the
     *                  ServiceStore does not contain the URL or if any
     *                  error occurs during the operation or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public void
        deleteAttributes(ServiceURL url,
                         Vector scopes,
                         Vector attrTags,
                         Locale locale)
        throws ServiceLocationException {

        String lang = SLPConfig.localeToLangTag(locale);

        // Get the scope level from urlScopeLangTable.

        Hashtable scopeLevel =
            (Hashtable)urlScopeLangTable.get(url.toString());

        // Error if no old record to update.

        if (scopeLevel == null) {
            throw
                new ServiceLocationException(
                                ServiceLocationException.INVALID_REGISTRATION,
                                "ssim_no_rec",
                                new Object[] {url});

        }

        // Check existing records to be sure that the scopes
        //  match. Attributes must be the same across
        //  scopes.

        checkScopeStatus(url,
                         scopes,
                         ServiceLocationException.INVALID_REGISTRATION);

        // Create attribute patterns for the default locale. This
        //  is an optimization. Only Turkish differs in lower
        //  case from the default. If there are any other exceptions,
        //  we need to move this into the loop.

        Vector attrPatterns =
            stringVectorToAttributePattern(attrTags, Defaults.locale);

        // Look through the language table for this language at scope level.

        Enumeration en = scopeLevel.keys();

        Assert.slpassert(en.hasMoreElements(),
                      "ssim_empty_scope_table",
                      new Object[] {url});

        Hashtable ht = new Hashtable();
        boolean foundIt = false;

        while (en.hasMoreElements()) {
            String scope = (String)en.nextElement();
            Hashtable langLevel = (Hashtable)scopeLevel.get(scope);
            Enumeration een = langLevel.keys();

            Assert.slpassert(een.hasMoreElements(),
                          "ssim_empty_lang_table",
                          new Object[] {url});

            // Find the list of records for this language.

            Vector listVec = (Vector)langLevel.get(lang);

            if (listVec == null) {
                continue;

            }

            foundIt = true;

            List elem = (List)listVec.elementAt(0);
            ServiceRecordInMemory rec = elem.record;
            Locale loc = rec.getLocale();

            // If we've done this one already, go on.

            if (ht.get(rec) != null) {
                continue;

            }

            ht.put(rec, rec);

            // Delete old registration.

            deregisterInternal(url, rec.getScopes(), lang);

            // Delete attributes from this record.

            // If the locale is Turkish, then use the Turkish patterns.

            if (loc.getLanguage().equals("tr")) {
                Vector turkishTags =
                    stringVectorToAttributePattern(attrTags, loc);

                deleteAttributes(rec, turkishTags);

            } else {
                deleteAttributes(rec, attrPatterns);

            }

            // Reregister the record.

            registerInternal(rec);
        }

        // If no record found, report error.

        if (!foundIt) {
            throw
                new ServiceLocationException(
                                ServiceLocationException.INVALID_REGISTRATION,
                                "ssim_no_rec_locale",
                                new Object[] {url, locale});

        }

    }

    /**
     * Return a Vector of String containing the service types for this
     * scope and naming authority. If there are none, an empty vector is
     * returned.
     *
     * @param namingAuthority The namingAuthority, or "*" if for all.
     * @param scopes The scope names.
     * @return A Vector of String objects that are the type names, or
     *          an empty vector if there are none.
     * @exception ServiceLocationException Thrown if any
     *                  error occurs during the operation or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public Vector
        findServiceTypes(String namingAuthority, Vector scopes)
        throws ServiceLocationException {

        Vector ret = new Vector();
        Enumeration keys = scopeTypeLangTable.keys();
        boolean isWildCard = namingAuthority.equals("*");
        boolean isIANA = (namingAuthority.length() <= 0);

        // Get all the keys in the table, look for scope.

        while (keys.hasMoreElements()) {
            String sstKey = (String)keys.nextElement();

            // Check whether this is an abstract type entry.
            //  If so, then we ignore it, because we only
            //  want full type names in the return.

            if (isAbstractTypeRecord(sstKey)) {
                continue;

            }

            // If the scope matches then check the naming authority.

            String keyScope = keyScope(sstKey);

            if (scopes.contains(keyScope)) {
                String keyType = keyServiceType(sstKey);

                // If not already there, see if we should add this one to the
                //  vector.

                if (!ret.contains(keyType)) {
                    ServiceType type = new ServiceType(keyType);

                    // If wildcard, then simply add it to the vector.

                    if (isWildCard) {
                        ret.addElement(type.toString());

                    } else {

                        // Check naming authority.

                        String na = type.getNamingAuthority();

                        if (type.isNADefault() && isIANA) { // check for IANA..
                            ret.addElement(type.toString());

                        } else if (namingAuthority.equals(na)) { // Not IANA..
                            ret.addElement(type.toString());

                        }
                    }
                }
            }
        }

        return ret;
    }

    /**
     * Return a Hashtable with the key FS_SERVICES matched to the
     * hashtable of ServiceURL objects as key and a vector
     * of their scopes as value, and the key FS_SIGTABLE
     * matched to a hashtable with ServiceURL objects as key
     * and the auth block Hashtable for the URL (if any) for value. The
     * returned service URLs will match the service type, scope, query,
     * and locale. If there are no signatures, the FS_SIGTABLE
     * key returns null. If there are no
     * registrations in any locale, FS_SERVICES is bound to an
     * empty table.
     *
     * @param serviceType The service type name.
     * @param scope The scope name.
     * @param query The query, with any escaped characters as yet unprocessed.
     * @param locale The locale in which to lowercase query and search.
     * @return A Hashtable with the key FS_SERVICES matched to the
     *         hashtable of ServiceURL objects as key and a vector
     *         of their scopes as value, and the key FS_SIGTABLE
     *         matched to a hashtable with ServiceURL objects as key
     *         and the auth block Hashtable for the URL (if any) for value.
     *         If there are no registrations in any locale, FS_SERVICES
     *        is bound to an empty table.
     * @exception ServiceLocationException Thrown if a parse error occurs
     *                  during query parsing or if any
     *                  error occurs during the operation or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures.
     */

    synchronized public Hashtable
        findServices(String serviceType,
                     Vector scopes,
                     String query,
                     Locale locale)
        throws ServiceLocationException {

        String lang = locale.getLanguage();
        Parser.ParserRecord ret = new Parser.ParserRecord();
        Hashtable services = null;
        Hashtable signatures = null;
        int i, n = scopes.size();
        int len = 0;

        // Get the services and signatures tables.

        services = ret.services;
        signatures = ret.signatures;

        // Remove leading and trailing spaces.

        query = query.trim();
        len = query.length();

        // Check whether there are any registrations for this type/scope/
        //  language tag and, if not, whether there are others.
        //  in another language, but not this one.

        int regStatus = languageSupported(serviceType, scopes, lang);

        if (regStatus == NO_REGS_IN_LOCALE) {
            throw
                new ServiceLocationException(
                        ServiceLocationException.LANGUAGE_NOT_SUPPORTED,
                        "ssim_lang_unsup",
                        new Object[] {locale});

        } else if (regStatus == REGS_IN_LOCALE) {

            // Only do query if regs exist.

            for (i = 0; i < n; i++) {
                String scope = (String)scopes.elementAt(i);
                String sstKey =
                    makeScopeTypeLangKey(scope, serviceType, lang);
                STLRecord regRecs =
                    (STLRecord)scopeTypeLangTable.get(sstKey);

                // If no record for this combo of service type and
                //  scope, continue.

                if (regRecs == null) {
                    continue;
                }

                // Special case if the query string is empty. This
                //  indicates that all registrations should be returned.

                if (len <= 0) {
                    BtreeVector bvec = regRecs.attrSort;
                    ParserBVCollector collector =
                        new ParserBVCollector(scopes);
                    collector.prReturns = ret;

                    // Use the BtreeVector.getAll() method to get all
                    //  registrations. We will end up revisiting some
                    //  list elements because there will be ones
                    //  for multiple attributes, but that will be
                    //  filtered in the BVCollector.setReturn() method.

                    bvec.getAll(collector);

                } else {

                    // Otherwise, use the LDAPv3 parser to evaluate.

                    InMemoryEvaluator ev =
                        new InMemoryEvaluator(regRecs.attrValueSort,
                                              regRecs.attrSort,
                                              scopes);

                    Parser.parseAndEvaluateQuery(query, ev, locale, ret);

                }
            }
        }

        // Create return hashtable.

        Hashtable ht = new Hashtable();

        // Set up return hashtable.

        ht.put(ServiceStore.FS_SERVICES, services);

        // Put in signatures if there.

        if (signatures.size() > 0) {
            ht.put(ServiceStore.FS_SIGTABLE, signatures);

        }

        return ht;
    }

    /**
     * Return a Hashtable with key FA_ATTRIBUTES matched to the
     * vector of ServiceLocationAttribute objects and key FA_SIG
     * matched to the auth block Hashtable for the attributes (if any)
     * The attribute objects will have tags matching the tags in
     * the input parameter vector. If there are no registrations in any locale,
     * FA_ATTRIBUTES is an empty vector.
     *
     * @param url The ServiceURL for which the records should be returned.
     * @param scopes The scope names for which to search.
     * @param attrTags The Vector of String
     *                  objects containing the attribute tags.
     * @param locale The locale in which to lower case tags and search.
     * @return A Hashtable with a vector of ServiceLocationAttribute objects
     *         as the key and the auth block Hashtable for the attributes
     *         (if any) as the value.
     *         If there are no registrations in any locale, FA_ATTRIBUTES
     *         is an empty vector.
     * @exception ServiceLocationException Thrown if any
     *                  error occurs during the operation or if the table
     *                  requires a network connection that failed. This
     *                  includes timeout failures. An error should be
     *                  thrown if the tag vector is for a partial request
     *                  and any of the scopes are protected.
     */

    synchronized public Hashtable
        findAttributes(ServiceURL url,
                       Vector scopes,
                       Vector attrTags,
                       Locale locale)
        throws ServiceLocationException {

        Hashtable ht = new Hashtable();
        Vector ret = new Vector();
        String lang = locale.getLanguage();
        Hashtable sig = null;

        // Check whether there are any registrations for this scope/type
        //  language and, if not, whether there are others.
        //  in another language, but not this one.

        int regStatus =
            languageSupported(url.getServiceType().toString(), scopes, lang);

        if (regStatus == NO_REGS_IN_LOCALE) {
            throw
                new ServiceLocationException(
                        ServiceLocationException.LANGUAGE_NOT_SUPPORTED,
                        "ssim_lang_unsup",
                        new Object[] {locale});

        } else if (regStatus == REGS_IN_LOCALE) {

            // Only if there are any regs at all.

            // Process string tags into pattern objects. Note that, here,
            //  the patterns are locale specific because the locale of
            //  the request determines how the attribute tags are lower
            //  cased.

            attrTags = stringVectorToAttributePattern(attrTags, locale);

            // Return attributes from the matching URL record.

            Hashtable scopeLevel =
                (Hashtable)urlScopeLangTable.get(url.toString());

            // If nothing there, then simply return. The URL isn't
            //  registered.

            if (scopeLevel != null) {

                // We reuse ht here for attributes.

                int i, n = scopes.size();

                for (i = 0; i < n; i++) {
                    String scope = (String)scopes.elementAt(i);
                    Hashtable langLevel =
                        (Hashtable)scopeLevel.get(scope);

                    // If no registration in this scope, continue.

                    if (langLevel == null) {
                        continue;
                    }

                    // Get the vector of lists.

                    Vector listVec = (Vector)langLevel.get(lang);

                    // If no registration in this locale, continue.

                    if (listVec == null) {
                        continue;

                    }

                    // Get the service record.

                    List elem = (List)listVec.elementAt(0);
                    ServiceRecordInMemory rec = elem.record;

                    // Once we've found *the* URL record, we can leave the loop
                    //  because there is only one record per locale.

                    findMatchingAttributes(rec, attrTags, ht, ret);

                    // Clear out the hashtable. We reuse it for the return.

                    ht.clear();

                    // Store the return vector and the signatures, if any.

                    ht.put(ServiceStore.FA_ATTRIBUTES, ret);

                    sig = rec.getAttrSignature();

                    if (sig != null) {
                        ht.put(ServiceStore.FA_SIG, sig);

                    }

                    break;

                }
            }
        }

        // Put in the empty vector, in case there are no regs at all.

        if (ht.size() <= 0) {
            ht.put(ServiceStore.FA_ATTRIBUTES, ret);

        }

        return ht;
    }

    /**
     * Return a Vector of ServiceLocationAttribute objects with attribute tags
     * matching the tags in the input parameter vector for all service URL's
     * of the service type. If there are no registrations
     * in any locale, an empty vector is returned.
     *
     * @param serviceType The service type name.
     * @param scopes The scope names for which to search.
     * @param attrTags The Vector of String
     *                  objects containing the attribute tags.
     * @param locale The locale in which to lower case tags.
     * @return A Vector of ServiceLocationAttribute objects matching the query.
     *         If no match occurs but there are registrations
     *        in other locales, null is returned. If there are no registrations
     *         in any locale, an empty vector is returned.
     * @exception ServiceLocationException Thrown if any
     *           error occurs during the operation or if the table
     *           requires a network connection that failed. This
     *           includes timeout failures. An error should also be
     *            signalled if any of the scopes are protected.
     */

    synchronized public Vector
        findAttributes(String serviceType,
                       Vector scopes,
                       Vector attrTags,
                       Locale locale)
        throws ServiceLocationException {

        String lang = locale.getLanguage();
        Vector ret = new Vector();

        // Check whether there are any registrations for this type/scope/
        //  language and, if not, whether there are others.
        //  in another language, but not this one.

        int regStatus = languageSupported(serviceType, scopes, lang);

        if (regStatus == NO_REGS_IN_LOCALE) {
            throw
                new ServiceLocationException(
                        ServiceLocationException.LANGUAGE_NOT_SUPPORTED,
                        "ssim_lang_unsup",
                        new Object[] {locale});

        } else if (regStatus == REGS_IN_LOCALE) {

            // Process string tags into pattern objects. Note that, here,
            //  the patterns are locale specific because the locale of
            //  the request determines how the attribute tags are lower
            //  cased.

            attrTags = stringVectorToAttributePattern(attrTags, locale);
            int len = attrTags.size();

            // Make a collector for accessing the BtreeVector.

            BVCollector collector =
                new AttributeBVCollector(attrTags, ret);
            int i, n = scopes.size();

            for (i = 0; i < n; i++) {
                String scope = (String)scopes.elementAt(i);
                String sstKey =
                    makeScopeTypeLangKey(scope, serviceType, lang);
                STLRecord regRecs = (STLRecord)scopeTypeLangTable.get(sstKey);

                // If no service type and scope, go to next scope.

                if (regRecs == null) {
                    continue;
                }

                // Get BtreeVector with all attributes for searching.

                BtreeVector bvec = regRecs.attrSort;

                // If there are no tags, then simply return everything in
                //  the BtreeVector.

                if (len <= 0) {
                    bvec.getAll(collector);

                } else {

                    // Use Btree vector to match the attribute tag patterns,
                    //  returning matching records.

                    int j;

                    for (j = 0; j < len; j++) {
                        AttributePattern pat =
                            (AttributePattern)attrTags.elementAt(j);

                        bvec.matchEqual(pat, collector);

                    }
                }
            }
        }

        return ret;
    }

    /**
     * Obtain the record matching the service URL and locale.
     *
     * @param URL The service record to match.
     * @param locale The locale of the record.
     * @return The ServiceRecord object, or null if none.
     */

    synchronized public ServiceStore.ServiceRecord
        getServiceRecord(ServiceURL URL, Locale locale) {

        if (URL == null || locale == null) {
            return null;

        }

        // Search in all scopes.

        return findExistingRecord(URL,
                                  null,
                                  SLPConfig.localeToLangTag(locale));

    }

    /**
     * Obtains service records with scopes matching from vector scopes.
     * If scopes is null, then returns all records.
     *
     * @param scopes Vector of scopes to match.
     * @return Enumeration   Of ServiceRecord Objects.
     */
    synchronized public Enumeration getServiceRecordsByScope(Vector scopes) {

        // Use a scope collector.

        Vector records = new Vector();
        BVCollector collector =
            new ScopeBVCollector(records, scopes);

        Enumeration keys = scopeTypeLangTable.keys();

        while (keys.hasMoreElements()) {
            String sstKey = (String)keys.nextElement();
            STLRecord regRecs = (STLRecord)scopeTypeLangTable.get(sstKey);

            // Get all records.

            BtreeVector bvec = regRecs.attrSort;
            bvec.getAll(collector);

        }

        return records.elements();
    }


    /**
     * Dump the service store to the log.
     *
     */

    synchronized public void dumpServiceStore() {

        SLPConfig conf = SLPConfig.getSLPConfig();

        conf.writeLogLine("ssim_dump_start",
                          new Object[] {this});

        Enumeration keys = scopeTypeLangTable.keys();

        while (keys.hasMoreElements()) {
            String sstKey = (String)keys.nextElement();
            STLRecord regRec = (STLRecord)scopeTypeLangTable.get(sstKey);

            // If the service type is abstract, then skip it. It will be
            //  displayed when the concrete type is.

            if (regRec.isAbstract) {
                continue;

            }

            // Get all records.

            BtreeVector bvec = regRec.attrSort;
            Vector vReturns = new Vector();
            BVCollector collector = new AllBVCollector(vReturns);

            bvec.getAll(collector);

            // Now write them out.

            int i, n = vReturns.size();

            for (i = 0; i < n; i++) {
                ServiceRecordInMemory rec =
                    (ServiceRecordInMemory)vReturns.elementAt(i);

                writeRecordToLog(conf, rec);
            }
        }

        conf.writeLog("ssim_dump_end",
                      new Object[] {this});
    }

    //
    // Protected/private methods.
    //

    // Register the record without any preliminaries. We assume that
    //  any old records have been removed and merged into this one,
    //  as necessary.

    private void registerInternal(ServiceRecordInMemory rec) {

        ServiceURL surl = rec.getServiceURL();
        ServiceType type = surl.getServiceType();
        String serviceType = type.toString();
        String abstractTypeName = type.getAbstractTypeName();
        Locale locale = rec.getLocale();
        String lang = locale.getLanguage();
        Vector scopes = rec.getScopes();

        // Make one age out queue entry. It will go into
        //  all scopes, but that's OK.

        List ageOutElem = addToAgeOutQueue(rec);

        // Go through all scopes.

        int i, n = scopes.size();

        for (i = 0; i < n; i++) {
            String scope = (String)scopes.elementAt(i);

            // Initialize the urltable list vector for this URL.

            Vector listVec =
                initializeURLScopeLangTableVector(surl, scope, lang);

            // Add to scope/type/lang table.

            addRecordToScopeTypeLangTable(scope,
                                          serviceType,
                                          lang,
                                          false,
                                          rec,
                                          listVec);

            // Add a new service type/scope record for this locale.

            addTypeLocale(serviceType, scope, lang);

            // Add ageOut record, so that it gets deleted when
            //  the record does.

            listVec.addElement(ageOutElem);

            // If the type is an abstract type, then add
            //  separate records.

            if (type.isAbstractType()) {
                addRecordToScopeTypeLangTable(scope,
                                              abstractTypeName,
                                              lang,
                                              true,
                                              rec,
                                              listVec);
                addTypeLocale(abstractTypeName, scope, lang);

            }
        }
    }

    // Create a urlScopeLangTable record for this URL.

    private Vector
        initializeURLScopeLangTableVector(ServiceURL url,
                                          String scope,
                                          String lang) {

        // Get scope level, creating if new.

        Hashtable scopeLevel =
            (Hashtable)urlScopeLangTable.get(url.toString());

        if (scopeLevel == null) {
            scopeLevel = new Hashtable();
            urlScopeLangTable.put(url.toString(), scopeLevel);

        }

        // Get lang level, creating if new.

        Hashtable langLevel =
            (Hashtable)scopeLevel.get(scope);

        if (langLevel == null) {
            langLevel = new Hashtable();
            scopeLevel.put(scope, langLevel);

        }

        // Check whether there's anything already there.
        //  Bug if so.

        Assert.slpassert(langLevel.get(lang) == null,
                      "ssim_url_lang_botch",
                      new Object[] {lang,
                                        url,
                                        scope});

        // Add a new list vector, and return it.

        Vector listVec = new Vector();

        langLevel.put(lang, listVec);

        return listVec;

    }

    // Add a record to the scope/type/language table.

    private void
        addRecordToScopeTypeLangTable(String scope,
                                      String serviceType,
                                      String lang,
                                      boolean isAbstract,
                                      ServiceRecordInMemory rec,
                                      Vector listVec) {

        // Make key for scope/type/language table.

        String stlKey = makeScopeTypeLangKey(scope, serviceType, lang);

        // Get record for scope/type/lang.

        STLRecord trec = (STLRecord)scopeTypeLangTable.get(stlKey);

        // If it's not there, make it.

        if (trec == null) {
            trec = new STLRecord(isAbstract);
            scopeTypeLangTable.put(stlKey, trec);

        }

        // Otherwise, add record to all.

        addRecordToAttrValueSort(trec.attrValueSort, rec, listVec);
        addRecordToAttrSort(trec.attrSort, rec, listVec);

    }

    // Add a new record into the attr value table.

    private void
        addRecordToAttrValueSort(Hashtable table,
                                 ServiceRecordInMemory rec,
                                 Vector listVec) {

        Vector attrList = rec.getAttrList();
        int i, n = attrList.size();

        // Go through the attribute list.

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)attrList.elementAt(i);
            AttributeString tag = attr.idPattern;
            Vector values = attr.values;

            // If a type table record exists, use it. Otherwise,
            //  create a newly initialized one.

            Hashtable ttable = (Hashtable)table.get(tag);

            if (ttable == null) {
                ttable = makeAttrTypeTable();
                table.put(tag, ttable);

            }

            // Get the class of values.

            String typeKey = null;

            if (values == null) {

                // We're done, since there are no attributes to add.

                continue;

            } else {
                Object val = values.elementAt(0);

                typeKey = val.getClass().getName();
            }

            // Get the BtreeVector.

            BtreeVector bvec =
                (BtreeVector)ttable.get(typeKey);

            // Insert a record for each value.

            int j, m = values.size();

            for (j = 0; j < m; j++) {
                List elem = bvec.add(values.elementAt(j), rec);

                // Put the element into the deletion table.

                listVec.addElement(elem);
            }
        }
    }

    // Return a newly initialized attribute type table. It will
    //  have a hash for each allowed type, with a new BtreeVector
    //  attached.

    private Hashtable makeAttrTypeTable() {

        Hashtable ret = new Hashtable();

        ret.put(INTEGER_TYPE, new BtreeVector());
        ret.put(ATTRIBUTE_STRING_TYPE, new BtreeVector());
        ret.put(BOOLEAN_TYPE, new BtreeVector());
        ret.put(OPAQUE_TYPE, new BtreeVector());

        return ret;
    }

    // Add a new record into the attrs table.

    private void
        addRecordToAttrSort(BtreeVector table,
                            ServiceRecordInMemory rec,
                            Vector listVec) {

        Vector attrList = rec.getAttrList();
        int i, n = attrList.size();

        // If no attributes, then add with empty string as
        //  the attribute tag.

        if (n <= 0) {
            List elem =
                table.add(new AttributeString("", rec.getLocale()), rec);

            listVec.addElement(elem);

            return;
        }

        // Iterate through the attribute list, adding to the
        //  BtreeVector with attribute as the sort key.

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)attrList.elementAt(i);

            List elem = table.add(attr.idPattern, rec);

            // Save for deletion.

            listVec.addElement(elem);

        }
    }

    // Add a record to the ageOut queue.

    private List addToAgeOutQueue(ServiceRecordInMemory rec) {

        Long exTime = Long.valueOf(rec.getExpirationTime());
        return ageOutQueue.add(exTime, rec);

    }

    // Remove the URL record from the database.

    private void
        deregisterInternal(ServiceURL url, Vector scopes, String lang) {

        ServiceType type = url.getServiceType();

        // To deregister, we only need to find the Vector of List objects
        //  containing the places where this registration is hooked into
        //  lists and unhook them. Garbage collection of other structures
        //  is handled during insertion or in deregisterTypeLocale(),
        //  if there are no more registrations at all.

        // Find the scope table..

        Hashtable scopeLangTable =
            (Hashtable)urlScopeLangTable.get(url.toString());

        // If it's not there, then maybe not registered.

        if (scopeLangTable == null) {
            return;

        }

        // For each scope, find the lang table.

        int i, n = scopes.size();

        for (i = 0; i < n; i++) {
            String scope = (String)scopes.elementAt(i);

            Hashtable langTable = (Hashtable)scopeLangTable.get(scope);

            if (langTable == null) {
                continue;
            }

            // If the locale is non-null, then just deregister from this
            //  locale.

            if (lang != null) {
                deregisterFromLocale(langTable, lang);

                // Record the deletion in the scope/type table, and
                //  also the number of regs table.

                deleteTypeLocale(type.toString(), scope, lang);

                // Check for abstract type as well.

                if (type.isAbstractType()) {
                    deleteTypeLocale(type.getAbstractTypeName(), scope, lang);

                }

            } else {

                // Otherwise, deregister all languages.

                Enumeration en = langTable.keys();

                while (en.hasMoreElements()) {
                    lang = (String)en.nextElement();

                    deregisterFromLocale(langTable, lang);

                    // Record the deletion in the scope/type table, and
                    //  also the number of regs table.

                    deleteTypeLocale(type.toString(), scope, lang);

                    // Check for abstract type as well.

                    if (type.isAbstractType()) {
                        deleteTypeLocale(type.getAbstractTypeName(),
                                         scope,
                                         lang);

                    }
                }
            }

            // If the table is empty, then remove the lang table.

            if (langTable.size() <= 0) {
                scopeLangTable.remove(scope);

            }
        }

        // If all languages were deleted, delete the
        //  urlScopeLangTable record. Other GC handled in
        //  deleteTypeLocale().

        if (scopeLangTable.size() <= 0) {
            urlScopeLangTable.remove(url.toString());

        }

    }

    // Deregister a single locale from the language table.

    private void deregisterFromLocale(Hashtable langTable, String lang) {

        // Get the Vector containing the list of registrations.

        Vector regList = (Vector)langTable.get(lang);

        Assert.slpassert(regList != null,
                      "ssim_null_reg_vector",
                      new Object[] {lang});

        // Walk down the list of registrations and unhook them from
        //  their respective lists.

        int i, n = regList.size();

        for (i = 0; i < n; i++) {
            List elem = (List)regList.elementAt(i);

            elem.delete();

        }

        // Remove the locale record.

        langTable.remove(lang);
    }

    // Find an existing record matching the URL by searching in all scopes.
    //  The record will be the same for all scopes in the same language.
    //  If locale is null, return any. If there are none, return null.

    private ServiceRecordInMemory
        findExistingRecord(ServiceURL surl, Vector scopes, String lang) {

        ServiceRecordInMemory rec = null;

        // Look in urlScopeLangTable.

        Hashtable scopeLevel =
            (Hashtable)urlScopeLangTable.get(surl.toString());

        if (scopeLevel != null) {

            // If scopes is null, then perform the search for all
            //  scopes in the table. Otherwise perform it for
            //  all scopes incoming.

            Enumeration en = null;

            if (scopes == null) {
                en = scopeLevel.keys();

            } else {
                en = scopes.elements();

            }

            while (en.hasMoreElements()) {
                String scope = (String)en.nextElement();
                Hashtable langLevel = (Hashtable)scopeLevel.get(scope);

                // If no langLevel table, continue searching.

                if (langLevel == null) {
                    continue;

                }

                Vector listVec = null;

                // Use lang tag if we have it, otherwise, pick arbitrary.

                if (lang != null) {
                    listVec = (Vector)langLevel.get(lang);

                } else {
                    Enumeration llen = langLevel.elements();

                    listVec = (Vector)llen.nextElement();

                }

                // If none for this locale, try the next scope.

                if (listVec == null) {
                    continue;

                }

                // Select out the record.

                List elem = (List)listVec.elementAt(0);

                rec = elem.record;
                break;

            }
        }

        return rec;
    }

    // Find attributes matching the record and place the matching attributes
    //  into the vector. Use the hashtable for collation.

    static void
        findMatchingAttributes(ServiceRecordInMemory rec,
                               Vector attrTags,
                               Hashtable ht,
                               Vector ret)
        throws ServiceLocationException {

        int len = attrTags.size();
        Vector attrList = rec.getAttrList();

        // For each attribute, go through the tag vector If an attribute
        //  matches, merge it into the return vector.

        int i, n = attrList.size();

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)attrList.elementAt(i);

            // All attributes match if the pattern vector is
            //  empty.

            if (len <= 0) {
                saveValueIfMatch(attr, null, ht, ret);

            } else {

                // Check each pattern against the attribute id.

                int j;

                for (j = 0; j < len; j++) {
                    AttributePattern attrTag =
                        (AttributePattern)attrTags.elementAt(j);

                    saveValueIfMatch(attr, attrTag, ht, ret);

                }
            }
        }
    }

    // Check the attribute against the pattern. If the pattern is null,
    //  then match occurs. Merge the attribute into the vector
    //  if match.

    static private void saveValueIfMatch(ServerAttribute attr,
                                         AttributePattern attrTag,
                                         Hashtable ht,
                                         Vector ret)
        throws ServiceLocationException {

        AttributeString id = attr.idPattern;

        // We save the attribute value if either
        //  the pattern is null or it matches the attribute id.

        if (attrTag == null || attrTag.match(id)) {

            Vector values = attr.getValues();

            // Create new values vector so record copy isn't
            //  modified.

            if (values != null) {
                values = (Vector)values.clone();

            }

            // Create new attribute so record copy isn't
            //  modified.

            ServiceLocationAttribute nattr =
                new ServiceLocationAttribute(attr.getId(), values);

            // Merge duplicate attributes into vector.

            ServiceLocationAttribute.mergeDuplicateAttributes(nattr,
                                                              ht,
                                                              ret,
                                                              true);
        }
    }

    // Check whether the incoming scopes are the same as existing
    //  scopes.

    private void
        checkScopeStatus(ServiceURL surl,
                         Vector scopes,
                         short errCode)
        throws ServiceLocationException {

        // Drill down in the urlScopeLangTable table.

        Hashtable scopeLevel =
            (Hashtable)urlScopeLangTable.get(surl.toString());

        if (scopeLevel == null) {
            return;  // not yet registered...

        }

        // We need to have exactly the same scopes as in
        //  the registration.

        int i, n = scopes.size();
        boolean ok = true;

        if (n != scopeLevel.size()) {
            ok = false;

        } else {

            for (i = 0; i < n; i++) {
                if (scopeLevel.get(scopes.elementAt(i)) == null) {
                    ok = false;
                    break;

                }
            }
        }

        if (!ok) {
            throw
                new ServiceLocationException(errCode,
                                             "ssim_scope_mis",
                                             new Object[0]);

        }
    }

    // Check whether an existing nonservice URL is registered under
    //  a different service type.

    private void checkForExistingUnderOtherServiceType(ServiceURL url,
                                                       Vector scopes)
        throws ServiceLocationException {

        // Drill down in the urlScopeLangTable table.

        Hashtable scopeLevel =
            (Hashtable)urlScopeLangTable.get(url.toString());

        if (scopeLevel == null) {
            return; // not yet registered.

        }

        // Get hashtable of locale records under scopes. Any scope
        //  will do.

        Object scope = scopes.elementAt(0);

        Hashtable localeLevel = (Hashtable)scopeLevel.get(scope);

        Assert.slpassert(localeLevel != null,
                      "ssim_null_lang_table",
                      new Object[] {scope});

        // Get a record from any locale.

        Enumeration en = localeLevel.elements();

        Assert.slpassert(en.hasMoreElements(),
                      "ssim_empty_lang_table",
                      new Object[] {scope});

        // Get vector of registrations.

        Vector vec = (Vector)en.nextElement();

        Assert.slpassert(vec.size() > 0,
                      "ssim_empty_reg_vector",
                      new Object[] {scope});

        List elem = (List)vec.elementAt(0);

        // OK, now check the registration.

        ServiceURL recURL = elem.record.getServiceURL();
        ServiceType recType = recURL.getServiceType();

        if (!recType.equals(url.getServiceType())) {
            throw
                new ServiceLocationException(
                                ServiceLocationException.INVALID_UPDATE,
                                "ssim_st_already",
                                new Object[0]);
        }
    }

    // Merge old record into new record.

    final private void mergeOldRecordIntoNew(ServiceRecordInMemory oldRec,
                                             ServiceRecordInMemory newRec)
        throws ServiceLocationException {

        Vector newAttrs = newRec.getAttrList();
        Vector oldAttrs = oldRec.getAttrList();
        Hashtable ht = new Hashtable();

        // Charge up the hashtable with the new attributes.

        int i, n = newAttrs.size();

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)newAttrs.elementAt(i);

            ht.put(attr.getId().toLowerCase(), attr);

        }

        // Merge in the old attributes.

        n = oldAttrs.size();

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)oldAttrs.elementAt(i);

            if (ht.get(attr.getId().toLowerCase()) == null) {
                newAttrs.addElement(attr);

            }
        }

        // Change the attribute vector on the rec.

        newRec.setAttrList(newAttrs);

        // Merge old scopes into new.

        Vector oldScopes = oldRec.getScopes();
        Vector newScopes = newRec.getScopes();
        int j, m = oldScopes.size();

        for (j = 0; j < m; j++) {
            String scope = (String)oldScopes.elementAt(j);

            if (!newScopes.contains(scope)) {
                newScopes.addElement(scope);

            }
        }

        // Note that we don't have to merge security because there
        //  will never be an incremental update to a record
        //  in a protected scope.

        // Change the scope vector on the rec.

        newRec.setScopes(newScopes);

    }

    // Delete attributes matching attrTags.

    private void deleteAttributes(ServiceRecordInMemory rec,
                                  Vector attrTags)
        throws ServiceLocationException {

        // For each attribute, go through the tag vector and put attributes
        // that do not match the tags into the new attribute vector.

        Vector attrList = rec.getAttrList();

        // If there are no attributes for this one, then simply return.

        if (attrList.size() <= 0) {
            return;

        }

        int i, n = attrList.size();
        Vector newAttrList = new Vector();
        int len = attrTags.size();

        for (i = 0; i < n; i++) {
            ServerAttribute attr =
                (ServerAttribute)attrList.elementAt(i);
            AttributeString id = attr.idPattern;
            boolean deleteIt = false;

            int j;

            // Now check the tags.

            for (j = 0; j < len; j++) {
                AttributePattern attrTag =
                    (AttributePattern)attrTags.elementAt(j);

                // If there's a match, mark for deletion.

                if (attrTag.match(id)) {
                    deleteIt = true;
                    break;

                }
            }

            if (!deleteIt) {
                newAttrList.addElement(attr);
            }
        }

        // Replace the attribute vector in the record.

        rec.setAttrList(newAttrList);
    }

    // Convert a vector of attribute tag strings to attribute pattern objects.

    private Vector stringVectorToAttributePattern(Vector tags, Locale locale)
        throws ServiceLocationException {

        // Takes care of findAttributes() case where no vector.

        if (tags == null) {
            return null;

        }

        Vector v = new Vector();
        int i, n = tags.size();

        for (i = 0; i < n; i++) {
            String value = (String)tags.elementAt(i);

            AttributePattern tag =
                new AttributePattern(value, locale);

            if (!v.contains(tag)) {
                v.addElement(tag);

            }
        }

        return v;
    }

    //
    // Output of service store to log.
    //

    // Write record to config log file.

    private void
        writeRecordToLog(SLPConfig conf, ServiceStore.ServiceRecord rec) {

        Locale locale = rec.getLocale();
        ServiceURL surl = rec.getServiceURL();
        Vector scopes = rec.getScopes();
        Vector attributes = rec.getAttrList();
        long exTime = rec.getExpirationTime();
        Hashtable urlSig = rec.getURLSignature();
        Hashtable attrSig = rec.getAttrSignature();

        conf.writeLogLine("ssim_dump_entry_start", new Object[0]);
        conf.writeLogLine("ssim_dump_entry",
                          new Object[] {
            locale,
                surl.toString(),
                Integer.toString(surl.getLifetime()),
                Long.toString(((exTime - System.currentTimeMillis())/1000)),
                surl.getServiceType(),
                scopes,
                attributes});

        if (urlSig != null) {
            conf.writeLogLine("ssim_dump_urlsig",
                              new Object[] {urlSig});

        }

        if (attrSig != null) {
            conf.writeLogLine("ssim_dump_attrsig",
                              new Object[] {
                attrSig});

        }
        conf.writeLogLine("ssim_entry_end", new Object[0]);
    }

    //
    // Utilities for dealing with service type/scope locale table.
    //

    // Bump up the number of registrations for this service type, scope and
    //  locale.

    private void
        addTypeLocale(String type, String scope, String lang) {

        String sstKey = makeScopeTypeKey(scope, type);

        // Get any existing record.

        Hashtable langTable = (Hashtable)sstLocales.get(sstKey);

        // Insert a new one if none there.

        if (langTable == null) {
            langTable = new Hashtable();

            sstLocales.put(sstKey, langTable);

        }

        // Look up locale.

        Integer numRegs = (Integer)langTable.get(lang);

        // Add a new one if none there, otherwise, bump up old.

        if (numRegs == null) {
            numRegs = Integer.valueOf(1);

        } else {
            numRegs = Integer.valueOf(numRegs.intValue() + 1);

        }

        // Put it back.

        langTable.put(lang, numRegs);

    }

    // Bump down the number of registrations for this service type, scope,
    //  in all locales.

    private void deleteTypeLocale(String type, String scope, String lang) {

        String sstKey = makeScopeTypeKey(scope, type);

        // Get any existing record.

        Hashtable langTable = (Hashtable)sstLocales.get(sstKey);

        // If none there, then error. But this should have been caught
        //  during deletion, so it's fatal.

        Assert.slpassert(langTable != null,
                      "ssim_ssttable_botch",
                      new Object[] {
            type,
                scope});

        // Get the Integer object recording the number of registrations.

        Integer numRegs = (Integer)langTable.get(lang);

        Assert.slpassert(numRegs != null,
                      "ssim_ssttable_lang_botch",
                      new Object[] {
            lang,
                type,
                scope});

        // Bump down by one, remove if zero.

        numRegs = Integer.valueOf(numRegs.intValue() - 1);

        if (numRegs.intValue() <= 0) {
            langTable.remove(lang);

            if (langTable.size() <= 0) {
                sstLocales.remove(sstKey);

            }

            // Garbage collection.

            // Remove records from the scopeTypeLangTable,
            //  since there are no registrations left for this
            //  type/scope/locale.

            String stlKey =
                makeScopeTypeLangKey(scope, type, lang);
            scopeTypeLangTable.remove(stlKey);

        } else {

            // Put it back.

            langTable.put(lang, numRegs);

        }
    }

    // Return REGS if the language is supported. Supported means that the
    //  there are some registrations of this service type in it or that
    //  there are none in any locale. Return NO_REGS if there are absolutely
    //  no registrations whatsoever, in any language. Return NO_REGS_IN_LOCALE
    //  if there are no registrations in that language but there are in
    //  others.

    private int
        languageSupported(String type, Vector scopes, String lang) {

        // Look through scope vector.

        boolean otherLangRegs = false;
        boolean sameLangRegs = false;
        int i, n = scopes.size();

        for (i = 0; i < n; i++) {
            String scope = (String)scopes.elementAt(i);
            String sstKey = makeScopeTypeKey(scope, type);

            // Get any existing record.

            Hashtable langTable = (Hashtable)sstLocales.get(sstKey);

            // If there are no regs, then check next scope.

            if (langTable == null) {
                continue;

            }

            Object numRegs = langTable.get(lang);

            // Check whether there are other language regs
            //  or same language regs.

            if (numRegs == null) {
                otherLangRegs = true;

            } else {
                sameLangRegs = true;

            }
        }

        // Return appropriate code.

        if (otherLangRegs == false &&
            sameLangRegs == false) {
            return NO_REGS;

        } else if (otherLangRegs == true &&
                   sameLangRegs == false) {
            return NO_REGS_IN_LOCALE;

        } else {
            return REGS_IN_LOCALE;

        }
    }

    //
    // Hash key calculations and hash table structuring.
    //

    // Return a key for type and scope.

    private String makeScopeTypeKey(String scope, String type) {
        return scope + "/" + type;

    }

    // Make a hash key consisting of the scope and service type.

    final private String
        makeScopeTypeLangKey(String scope,
                             String serviceType,
                             String lang) {

        return scope + "/" + serviceType + "/" + lang;
    }

    // Return the key's scope.

    final private String keyScope(String key) {
        int idx = key.indexOf('/');
        String ret = "";

        if (idx > 0) {
            ret = key.substring(0, idx);
        }

        return ret;
    }


    // Return the key's service type/NA.

    final private String keyServiceType(String key) {
        int idx = key.indexOf('/');
        String ret = "";
        int len = key.length();

        if (idx >= 0 && idx < len - 1) {
            ret = key.substring(idx+1, len);
        }

        // Parse off the final lang.

        idx = ret.indexOf('/');

        ret = ret.substring(0, idx);

        return ret;
    }

    // Return true if the record is for an abstract type.

    final private boolean isAbstractTypeRecord(String sstKey) {
        STLRecord rec = (STLRecord)scopeTypeLangTable.get(sstKey);

        return rec.isAbstract;

    }

}