common/hash/hashlook.c

da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*               This software is part of the ast package               *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                      and is licensed under the                       *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                  Common Public License, Version 1.0                  *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin*                    by AT&T Intellectual Property                     *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                A copy of the License is available at                 *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*            http://www.opensource.org/licenses/cpl1.0.txt             *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*              Information and Software Systems Research               *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                            AT&T Research                             *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                           Florham Park NJ                            *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                 Glenn Fowler <gsf@research.att.com>                  *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                  David Korn <dgk@research.att.com>                   *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                   Phong Vo <kpv@research.att.com>                    *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma prototyped
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Glenn Fowler
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * AT&T Research
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * hash table library
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "hashlib.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * hash table lookup
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinchar*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinhashlook(register Hash_table_t* tab, const char* name, long flags, const char* value)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register Hash_bucket_t* b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register unsigned int   n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register Hash_last_t*   last;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    Hash_table_t*       top;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    Hash_bucket_t*      prev;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    unsigned int        i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if ((flags & (HASH_LOOKUP|HASH_INTERNAL)) == (HASH_LOOKUP|HASH_INTERNAL))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        register char*      s1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        register const char*    s2;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        register int        c;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (flags & HASH_HASHED) n = *((unsigned int*)value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            s2 = name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            while (c = *s2++) HASHPART(n, c);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        i = n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        for (;;)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            HASHMOD(tab, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            for (b = tab->table[n]; b; b = b->next)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                s1 = hashname(b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                s2 = name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                while ((c = *s1++) == *s2++)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (!c) return((flags & HASH_VALUE) ? b->value : (char*)b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!(tab = tab->scope) || (flags & HASH_NOSCOPE))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    tab->root->accesses++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    top = tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    last = &tab->root->last;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (name)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        last->table = tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (flags & (HASH_BUCKET|HASH_INSTALL))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            last->bucket = (Hash_bucket_t*)name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            name = hashname(last->bucket);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else last->bucket = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        last->name = name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (flags & HASH_BUCKET) n = last->bucket->hash;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else if (tab->flags & HASH_HASHED)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = (unsigned int)integralof(name);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!(flags & HASH_HASHED)) n >>= 3;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else if (flags & HASH_HASHED) n = *((unsigned int*)value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else HASH(tab->root, name, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        last->hash = i = HASHVAL(n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        for (;;)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            HASHMOD(tab, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            for (prev = 0, b = tab->table[n]; b; prev = b, b = b->next)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (i == HASHVAL(b->hash) && ((b->hash & (HASH_DELETED|HASH_OPAQUED)) != HASH_DELETED || (flags & (HASH_CREATE|HASH_DELETE|HASH_INSTALL|HASH_RENAME))))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (!tab->root->local->compare)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        register char*      s1 = hashname(b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        register const char*    s2 = name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        if (tab->root->namesize)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            register char*  s3 = s1 + tab->root->namesize;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            while (*s1++ == *s2++)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                                if (s1 >= s3) goto found;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        else while (*s1 == *s2++)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            if (!*s1++) goto found;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else if (tab->root->namesize)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        if (!(*tab->root->local->compare)(hashname(b), name, tab->root->namesize)) goto found;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else if (!(*tab->root->local->compare)(hashname(b), name)) goto found;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->root->collisions++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!tab->scope || (flags & (HASH_CREATE|HASH_INSTALL|HASH_NOSCOPE)) == HASH_NOSCOPE) break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab = tab->scope;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab = last->table;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        name = last->name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        n = i = last->hash;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        prev = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        HASHMOD(tab, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (b = last->bucket)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin             * found the bucket
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin             */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        found:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (prev && !tab->frozen)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                 * migrate popular buckets to the front
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                 */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                prev->next = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                b->next = tab->table[n];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->table[n] = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            switch (flags & (HASH_CREATE|HASH_DELETE|HASH_INSTALL|HASH_RENAME))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            case HASH_CREATE:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            case HASH_CREATE|HASH_INSTALL:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            case HASH_INSTALL:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (tab != top && !(flags & HASH_SCOPE)) break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (flags & HASH_OPAQUE) b->hash |= HASH_OPAQUED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                goto exists;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            case HASH_DELETE:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                value = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (tab == top || (flags & HASH_SCOPE))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (flags & HASH_OPAQUE) b->hash &= ~HASH_OPAQUED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else if (!(tab->root->flags & HASH_BUCKET))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        if (tab->root->local->free && b->value)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            (*tab->root->local->free)(b->value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            b->value = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        else if (tab->flags & HASH_VALUE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            value = b->value;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            b->value = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    tab->buckets--;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (tab->frozen || (b->hash & HASH_OPAQUED)) b->hash |= HASH_DELETED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        tab->table[n] = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        name = (b->hash & HASH_FREENAME) ? (char*)b->name : (char*)0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        if (tab->root->local->free && (tab->root->flags & HASH_BUCKET)) (*tab->root->local->free)((char*)b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        else if (!(b->hash & HASH_KEEP))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, b, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            else free(b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        if (name)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, (char*)name, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            else free((char*)name);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                return((char*)value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            case HASH_RENAME:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (tab != top || tab->frozen || (b->hash & (HASH_KEEP|HASH_OPAQUED)) || hashlook(top, value, (flags&(HASH_HASHED|HASH_INTERNAL))|HASH_LOOKUP, NiL))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                name = (char*)b->name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (!(tab->flags & HASH_ALLOCATE)) b->name = (char*)value;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                else if (b->name && tab->root->namesize)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    memcpy(b->name, value, tab->root->namesize);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    name = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    int m;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    char*   t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (!(i = tab->bucketsize))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        i = (sizeof(Hash_bucket_t) + sizeof(char*) - 1) / sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    i *= sizeof(char*);
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin                    m = strlen(value);
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin                    if (b->name == ((char*)b + i) && strlen(b->name) <= m)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        strcpy(b->name, value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        name = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                         m++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                         if (!(t = tab->root->local->region ? (char*)(*tab->root->local->region)(tab->root->local->handle, NiL, m, 0) : (char*)malloc(m)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                            return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        b->name = strcpy(t, value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (name && (b->hash & HASH_FREENAME))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    b->hash &= ~HASH_FREENAME;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (tab->root->local->region) (*tab->root->local->region)(tab->root->local->handle, (char*)name, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    else free((char*)name);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->buckets--;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->table[n] = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                flags = HASH_CREATE|HASH_INSTALL;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                last->bucket = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                i = last->hash;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                goto create;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            default:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (!(b->hash & HASH_DELETED)) goto exists;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (!(flags & (HASH_CREATE|HASH_INSTALL))) return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     * create a new bucket
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin create:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (tab == top) prev = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (prev = b)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            name = (b->hash & HASH_HIDES) ? b->name : (char*)b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            i |= HASH_HIDES;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (!(flags & HASH_SCOPE)) tab = top;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     * check for table expansion
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (!tab->frozen && !(tab->flags & HASH_FIXED) && tab->buckets > tab->root->meanchain * tab->size)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        hashsize(tab, tab->size << 1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (flags & HASH_INSTALL)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        b = last->bucket;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        i |= HASH_KEEP;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        int m = tab->bucketsize * sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (flags & HASH_VALUE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->flags |= HASH_VALUE;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (m < sizeof(Hash_bucket_t))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->bucketsize = (sizeof(Hash_bucket_t) + sizeof(char*) - 1) / sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                m = tab->bucketsize * sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = m;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else if (!(n = HASH_SIZEOF(flags)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!(flags & HASH_FIXED)) n = m;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            else if ((n = (int)integralof(value)) < m) n = m;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else if (n < m) n = m;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (!prev && (tab->flags & HASH_ALLOCATE))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            m = tab->root->namesize ? tab->root->namesize : strlen(name) + 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (tab->root->local->region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n + m, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                memset(b, 0, n + m);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            else if (!(b = newof(0, Hash_bucket_t, 0, n + m)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            b->name = (char*)b + n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            memcpy(b->name, name, m);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (tab->root->local->region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (!(b = (Hash_bucket_t*)(*tab->root->local->region)(tab->root->local->handle, NiL, n, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                memset(b, 0, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            else if (!(b = newof(0, Hash_bucket_t, 0, n)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            b->name = (char*)name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    b->hash = n = i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    HASHMOD(tab, n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    b->next = tab->table[n];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    tab->table[n] = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    tab->buckets++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (flags & HASH_OPAQUE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab->buckets--;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        b->hash |= HASH_DELETED|HASH_OPAQUED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     * finally got the bucket
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin exists:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (b->hash & HASH_DELETED)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        b->hash &= ~HASH_DELETED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab->buckets++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    last->bucket = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    last->table = tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    switch (flags & (HASH_CREATE|HASH_VALUE))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    case HASH_CREATE|HASH_VALUE:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (tab->root->local->free && !(tab->root->flags & HASH_BUCKET) && b->value) (*tab->root->local->free)(b->value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (value && tab->root->local->alloc) value = (*tab->root->local->alloc)((unsigned int)integralof(value));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        b->value = (char*)value;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        return((char*)hashname(b));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    case HASH_VALUE:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        return(b->value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    default:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        return((char*)b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}