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