summaryrefslogtreecommitdiff
path: root/src/lib/libast/hash
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libast/hash')
-rw-r--r--src/lib/libast/hash/hashalloc.c200
-rw-r--r--src/lib/libast/hash/hashdump.c173
-rw-r--r--src/lib/libast/hash/hashfree.c144
-rw-r--r--src/lib/libast/hash/hashlast.c43
-rw-r--r--src/lib/libast/hash/hashlib.h104
-rw-r--r--src/lib/libast/hash/hashlook.c367
-rw-r--r--src/lib/libast/hash/hashscan.c139
-rw-r--r--src/lib/libast/hash/hashsize.c84
-rw-r--r--src/lib/libast/hash/hashview.c88
-rw-r--r--src/lib/libast/hash/hashwalk.c51
-rw-r--r--src/lib/libast/hash/memhash.c45
-rw-r--r--src/lib/libast/hash/memsum.c53
-rw-r--r--src/lib/libast/hash/strhash.c45
-rw-r--r--src/lib/libast/hash/strkey.c49
-rw-r--r--src/lib/libast/hash/strsum.c53
15 files changed, 1638 insertions, 0 deletions
diff --git a/src/lib/libast/hash/hashalloc.c b/src/lib/libast/hash/hashalloc.c
new file mode 100644
index 0000000..8c923f3
--- /dev/null
+++ b/src/lib/libast/hash/hashalloc.c
@@ -0,0 +1,200 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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
+ */
+
+static const char id_hash[] = "\n@(#)$Id: hash (AT&T Research) 1996-08-11 $\0\n";
+
+#include "hashlib.h"
+
+Hash_info_t hash_info = { 0 };
+
+/*
+ * create a new hash table
+ */
+
+Hash_table_t*
+hashalloc(Hash_table_t* ref, ...)
+{
+ register Hash_table_t* tab;
+ register Hash_table_t* ret = 0;
+ register int internal;
+ int n;
+ va_list ap;
+ va_list va[4];
+ va_list* vp = va;
+ Hash_region_f region = 0;
+ void* handle;
+
+ va_start(ap, ref);
+
+ /*
+ * check for HASH_region which must be first
+ */
+
+ n = va_arg(ap, int);
+ if (!ref && n == HASH_region)
+ {
+ region = va_arg(ap, Hash_region_f);
+ handle = va_arg(ap, void*);
+ n = va_arg(ap, int);
+ if (!(tab = (Hash_table_t*)(*region)(handle, NiL, sizeof(Hash_table_t), 0)))
+ goto out;
+ memset(tab, 0, sizeof(Hash_table_t));
+ }
+ else if (!(tab = newof(0, Hash_table_t, 1, 0)))
+ goto out;
+ tab->bucketsize = (sizeof(Hash_header_t) + sizeof(char*) - 1) / sizeof(char*);
+ if (ref)
+ {
+ tab->flags = ref->flags & ~HASH_RESET;
+ tab->root = ref->root;
+ internal = HASH_INTERNAL;
+ }
+ else
+ {
+ if (region)
+ {
+ if (!(tab->root = (Hash_root_t*)(*region)(handle, NiL, sizeof(Hash_root_t), 0)))
+ goto out;
+ memset(tab->root, 0, sizeof(Hash_root_t));
+ }
+ else if (!(tab->root = newof(0, Hash_root_t, 1, 0)))
+ goto out;
+ if (!(tab->root->local = newof(0, Hash_local_t, 1, 0)))
+ goto out;
+ if (tab->root->local->region = region)
+ tab->root->local->handle = handle;
+ tab->root->meanchain = HASHMEANCHAIN;
+ internal = 0;
+ }
+ tab->size = HASHMINSIZE;
+ for (;;)
+ {
+ switch (n)
+ {
+ case HASH_alloc:
+ if (ref) goto out;
+ tab->root->local->alloc = va_arg(ap, Hash_alloc_f);
+ break;
+ case HASH_bucketsize:
+ n = (va_arg(ap, int) + sizeof(char*) - 1) / sizeof(char*);
+ if (n > UCHAR_MAX) goto out;
+ if (n > tab->bucketsize) tab->bucketsize = n;
+ break;
+ case HASH_clear:
+ tab->flags &= ~(va_arg(ap, int) & ~internal);
+ break;
+ case HASH_compare:
+ if (ref) goto out;
+ tab->root->local->compare = va_arg(ap, Hash_compare_f);
+ break;
+ case HASH_free:
+ if (ref) goto out;
+ tab->root->local->free = va_arg(ap, Hash_free_f);
+ break;
+ case HASH_hash:
+ if (ref) goto out;
+ tab->root->local->hash = va_arg(ap, Hash_hash_f);
+ break;
+ case HASH_meanchain:
+ if (ref) goto out;
+ tab->root->meanchain = va_arg(ap, int);
+ break;
+ case HASH_name:
+ tab->name = va_arg(ap, char*);
+ break;
+ case HASH_namesize:
+ if (ref) goto out;
+ tab->root->namesize = va_arg(ap, int);
+ break;
+ case HASH_region:
+ goto out;
+ case HASH_set:
+ tab->flags |= (va_arg(ap, int) & ~internal);
+ break;
+ case HASH_size:
+ tab->size = va_arg(ap, int);
+ if (tab->size & (tab->size - 1)) tab->flags |= HASH_FIXED;
+ break;
+ case HASH_table:
+ tab->table = va_arg(ap, Hash_bucket_t**);
+ tab->flags |= HASH_STATIC;
+ break;
+ case HASH_va_list:
+ if (vp < &va[elementsof(va)])
+ {
+ va_copy(*vp, ap);
+ vp++;
+ }
+ va_copy(ap, va_listval(va_arg(ap, va_listarg)));
+ break;
+ case 0:
+ if (vp > va)
+ {
+ vp--;
+ va_copy(ap, *vp);
+ break;
+ }
+ if (tab->flags & HASH_SCOPE)
+ {
+ if (!(tab->scope = ref)) goto out;
+ ref->frozen++;
+ }
+ if (!tab->table)
+ {
+ if (region)
+ {
+ if (!(tab->table = (Hash_bucket_t**)(*region)(handle, NiL, sizeof(Hash_bucket_t*) * tab->size, 0)))
+ goto out;
+ memset(tab->table, 0, sizeof(Hash_bucket_t*) * tab->size);
+ }
+ else if (!(tab->table = newof(0, Hash_bucket_t*, tab->size, 0))) goto out;
+ }
+ if (!ref)
+ {
+ tab->root->flags = tab->flags & HASH_INTERNAL;
+ tab->root->next = hash_info.list;
+ hash_info.list = tab->root;
+ }
+ if (!region)
+ {
+ tab->next = tab->root->references;
+ tab->root->references = tab;
+ }
+ ret = tab;
+ goto out;
+ default:
+ goto out;
+ }
+ n = va_arg(ap, int);
+ }
+ out:
+ va_end(ap);
+ if (!ret) hashfree(tab);
+ return(ret);
+}
diff --git a/src/lib/libast/hash/hashdump.c b/src/lib/libast/hash/hashdump.c
new file mode 100644
index 0000000..3c2829a
--- /dev/null
+++ b/src/lib/libast/hash/hashdump.c
@@ -0,0 +1,173 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * dump HASH_* flags
+ */
+
+static void
+dumpflags(register int flags)
+{
+ if (flags & HASH_ALLOCATE) sfprintf(sfstderr, "allocate ");
+ if (flags & HASH_BUCKET) sfprintf(sfstderr, "bucket ");
+ if (flags & HASH_FIXED) sfprintf(sfstderr, "fixed ");
+ if (flags & HASH_HASHED) sfprintf(sfstderr, "hashed ");
+ if (flags & HASH_RESIZE) sfprintf(sfstderr, "resize ");
+ if (flags & HASH_STATIC) sfprintf(sfstderr, "static ");
+ if (flags & HASH_VALUE) sfprintf(sfstderr, "value ");
+}
+
+/*
+ * dump hash table bucket info
+ */
+
+static void
+dumpbucket(register Hash_table_t* tab, int flags)
+{
+ register Hash_bucket_t** sp;
+ register Hash_bucket_t* b;
+ Hash_bucket_t** sx;
+ int n;
+ unsigned char* s;
+
+ NoP(flags);
+ sx = tab->table + tab->size;
+ for (sp = tab->table; sp < sx; sp++)
+ {
+ n = 0;
+ for (b = *sp; b; b = b->next)
+ if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
+ n++;
+ if (n)
+ {
+ sfprintf(sfstderr, "%5d %2d :", sp - tab->table, n);
+ for (b = *sp; b; b = b->next)
+ if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
+ {
+ if (n = tab->root->namesize)
+ {
+ sfprintf(sfstderr, " 0x");
+ s = (unsigned char*)hashname(b);
+ while (n-- > 0)
+ sfprintf(sfstderr, "%02x", *s++);
+ }
+ else sfprintf(sfstderr, " %s", hashname(b));
+ if (b->hash & HASH_FLAGS)
+ {
+ sfprintf(sfstderr, "|");
+ if (b->hash & HASH_HIDES) sfprintf(sfstderr, "hides|");
+ if (b->hash & HASH_HIDDEN) sfprintf(sfstderr, "hidden|");
+ if (b->hash & HASH_KEEP) sfprintf(sfstderr, "keep|");
+ if (b->hash & HASH_OPAQUED) sfprintf(sfstderr, "opaque|");
+ }
+ if (tab->flags & HASH_VALUE) sfprintf(sfstderr, "=0x%08lx", (long)b->value);
+ }
+ sfprintf(sfstderr, "\n");
+ }
+ }
+ sfprintf(sfstderr, "\n");
+}
+
+/*
+ * dump info on a single table
+ */
+
+static void
+dumptable(register Hash_table_t* tab, register int flags)
+{
+ Hash_table_t* scope;
+ int level;
+
+ sfprintf(sfstderr, " name: %s", tab->name ? tab->name : "*no name*");
+ if (scope = tab->scope)
+ {
+ level = 1;
+ while (scope = scope->scope) level++;
+ sfprintf(sfstderr, " level %d scope on 0x%08lx", level, (unsigned long)tab->scope);
+ }
+ sfprintf(sfstderr, "\n");
+ sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)tab);
+ sfprintf(sfstderr, " flags: ");
+ if (tab->frozen) sfprintf(sfstderr, "frozen=%d ", tab->frozen);
+ dumpflags(tab->flags);
+ sfprintf(sfstderr, "\n");
+ sfprintf(sfstderr, " size: %d\n", tab->size);
+ sfprintf(sfstderr, " buckets: %d\n", tab->buckets);
+ sfprintf(sfstderr, " bucketsize: %d\n", tab->bucketsize * sizeof(char*));
+ sfprintf(sfstderr, "\n");
+ if ((flags | tab->flags) & HASH_BUCKET) dumpbucket(tab, flags);
+}
+
+/*
+ * dump hash table root info
+ */
+
+static void
+dumproot(register Hash_root_t* root, register int flags)
+{
+ register Hash_table_t* tab;
+
+ sfprintf(sfstderr, " root\n");
+ sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)root);
+ sfprintf(sfstderr, " flags: ");
+ dumpflags(root->flags);
+ if (root->namesize) sfprintf(sfstderr, "namesize=%d ", root->namesize);
+ if (root->local->alloc) sfprintf(sfstderr, "alloc=0x%08lx ", (unsigned long)root->local->alloc);
+ if (root->local->compare) sfprintf(sfstderr, "compare=0x%08lx ", (unsigned long)root->local->compare);
+ if (root->local->free) sfprintf(sfstderr, "free=0x%08lx ", (unsigned long)root->local->free);
+ if (root->local->hash) sfprintf(sfstderr, "hash=0x%08lx ", (unsigned long)root->local->hash);
+ if (root->local->region) sfprintf(sfstderr, "region=0x%08lx handle=0x%08lx ", (unsigned long)root->local->region, (unsigned long)root->local->handle);
+ sfprintf(sfstderr, "\n");
+ sfprintf(sfstderr, " meanchain: %d\n", root->meanchain);
+ sfprintf(sfstderr, " accesses: %d\n", root->accesses);
+ sfprintf(sfstderr, " collisions: %d\n", root->collisions);
+ sfprintf(sfstderr, "\n");
+ for (tab = root->references; tab; tab = tab->next)
+ dumptable(tab, flags);
+}
+
+/*
+ * dump hash table accounting info
+ * if tab is 0 then dump all tables in hash_info.list
+ * flags are HASH_* flags that specifiy optional dump info
+ */
+
+void
+hashdump(register Hash_table_t* tab, int flags)
+{
+ register Hash_root_t* root;
+
+ sfprintf(sfstderr, "\nhash table information:\n\n");
+ if (tab) dumproot(tab->root, flags);
+ else for (root = hash_info.list; root; root = root->next)
+ dumproot(root, flags);
+ sfsync(sfstderr);
+}
diff --git a/src/lib/libast/hash/hashfree.c b/src/lib/libast/hash/hashfree.c
new file mode 100644
index 0000000..b6998a3
--- /dev/null
+++ b/src/lib/libast/hash/hashfree.c
@@ -0,0 +1,144 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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"
+
+/*
+ * free (remove) a hash table
+ * can be called for partially constructed tables
+ * scope covered table pointer is returned
+ * root info freed when last reference freed
+ */
+
+Hash_table_t*
+hashfree(register Hash_table_t* tab)
+{
+ register Hash_bucket_t** sp;
+ register Hash_bucket_t* b;
+ register Hash_bucket_t* p;
+ Hash_bucket_t** sx;
+ Hash_root_t* rp;
+ Hash_table_t* tp;
+ Hash_free_f freevalue;
+ Hash_free_f freebucket;
+ Hash_region_f region;
+ void* handle;
+
+ if (!tab) return(0);
+ if (tab->table)
+ {
+ freebucket = 0;
+ freevalue = 0;
+ if (tab->root->local->free)
+ {
+ if (tab->root->flags & HASH_BUCKET) freebucket = tab->root->local->free;
+ else freevalue = tab->root->local->free;
+ }
+ if (region = tab->root->local->region)
+ handle = tab->root->local->handle;
+ sx = &tab->table[tab->size];
+ sp = &tab->table[0];
+ while (sp < sx)
+ {
+ b = *sp++;
+ while (b)
+ {
+ p = b;
+ b = b->next;
+ if (freebucket) (*freebucket)((char*)p);
+ else if (freevalue && p->value) (*freevalue)(p->value);
+ if (p->hash & HASH_FREENAME)
+ {
+ p->hash &= ~HASH_FREENAME;
+ if (region) (*region)(handle, p->name, 0, 0);
+ else free(p->name);
+ }
+ if (!(p->hash & HASH_KEEP))
+ {
+ if (region) (*region)(handle, p, 0, 0);
+ else free(p);
+ }
+ else if (p->hash & HASH_HIDES)
+ {
+ p->hash &= ~HASH_HIDES;
+ p->name = ((Hash_bucket_t*)p->name)->name;
+ }
+ }
+ }
+ if ((tab->flags & (HASH_RESIZE|HASH_STATIC)) != HASH_STATIC)
+ {
+ if (region) (*region)(handle, tab->table, 0, 0);
+ else free(tab->table);
+ }
+ }
+ else region = 0;
+ if (tab->root)
+ {
+ if (!region)
+ {
+ /*
+ * remove from the table lists
+ */
+
+ if ((tp = tab->root->references) != tab)
+ {
+ for (; tp; tp = tp->next)
+ if (tp->next == tab)
+ {
+ tp->next = tab->next;
+ break;
+ }
+ }
+ else if (!(tab->root->references = tp->next))
+ {
+ if ((rp = hash_info.list) != tab->root)
+ {
+ for (; rp; rp = rp->next)
+ if (rp->next == tab->root)
+ {
+ rp->next = tab->root->next;
+ break;
+ }
+ }
+ else hash_info.list = rp->next;
+ }
+ }
+ if (!(tab->root->references))
+ {
+ if (tab->root->local)
+ free(tab->root->local);
+ if (region) (*region)(handle, tab->root, 0, 0);
+ else free(tab->root);
+ }
+ }
+ if (tp = tab->scope) tp->frozen--;
+ if (region) (*region)(handle, tab, 0, 0);
+ else free(tab);
+ return(tp);
+}
diff --git a/src/lib/libast/hash/hashlast.c b/src/lib/libast/hash/hashlast.c
new file mode 100644
index 0000000..0083477
--- /dev/null
+++ b/src/lib/libast/hash/hashlast.c
@@ -0,0 +1,43 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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
+
+/* OBSOLETE 19960229 -- use tab->root->last.{table|bucket} */
+
+/*
+ * Glenn Fowler
+ * AT&T Research
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * return last lookup bucket for table
+ */
+
+Hash_bucket_t*
+hashlast(Hash_table_t* tab)
+{
+ return(tab->root->last.bucket);
+}
diff --git a/src/lib/libast/hash/hashlib.h b/src/lib/libast/hash/hashlib.h
new file mode 100644
index 0000000..2d225b9
--- /dev/null
+++ b/src/lib/libast/hash/hashlib.h
@@ -0,0 +1,104 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 private definitions
+ */
+
+#ifndef _HASHLIB_H
+#define _HASHLIB_H
+
+#include <ast.h>
+
+#define hash_info _hash_info_
+
+typedef void* (*Hash_alloc_f)(size_t);
+typedef int (*Hash_compare_f)(const char*, const char*, ...);
+typedef unsigned int (*Hash_hash_f)(const char*, ...);
+typedef void (*Hash_free_f)(void*);
+typedef void* (*Hash_region_f)(void*, void*, size_t, int);
+
+typedef struct /* root local pointers */
+{
+ Hash_hash_f hash; /* name hash routine */
+ Hash_compare_f compare; /* name comparision routine */
+ Hash_alloc_f alloc; /* value allocation routine */
+ Hash_free_f free; /* value free routine */
+ Hash_region_f region; /* region alloc/free routine */
+ void* handle; /* region handle arg */
+} Hash_local_t;
+
+#define _HASH_POSITION_PRIVATE_ \
+ Hash_table_t* tab; /* table pointer */ \
+ int flags; /* scan flags */ \
+ Hash_bucket_t** slot; /* table slot */ \
+ Hash_bucket_t** limit; /* slot limit */
+
+#define _HASH_LAST_PRIVATE_ \
+ const char* name; /* last lookup name */ \
+ unsigned int hash; /* last lookup hash */
+
+#define _HASH_ROOT_PRIVATE_ \
+ int namesize; /* fixed name size: 0 => string */ \
+ int meanchain; /* resize mean chain length */ \
+ Hash_local_t* local; /* root local pointers */ \
+ Hash_root_t* next; /* next in list of all roots */ \
+ Hash_table_t* references; /* referencing table list */
+
+#define _HASH_TABLE_PRIVATE_ \
+ unsigned char frozen; /* table freeze nesting */ \
+ unsigned char bucketsize; /* min bucket size in char*'s */ \
+ Hash_bucket_t** table; /* hash slot table */ \
+ Hash_table_t* next; /* root reference list link */
+
+#include <hash.h>
+
+#define HASHMINSIZE (1<<4) /* min table slots (power of 2) */
+#define HASHMEANCHAIN 2 /* def resize mean chain len */
+
+#define HASHMOD(t,h) (h &= (t->size - 1))
+#define HASHVAL(x) ((x)&~HASH_FLAGS)
+
+#define HASH(r,n,h) if (r->local->hash) h = r->namesize ? (*r->local->hash)(n, r->namesize) : (*r->local->hash)(n);\
+ else\
+ {\
+ register const char* _hash_s1 = n;\
+ h = 0;\
+ if (r->namesize)\
+ {\
+ register const char* _hash_s2 = _hash_s1 + r->namesize;\
+ while (_hash_s1 < _hash_s2) HASHPART(h, *_hash_s1++);\
+ }\
+ else while (*_hash_s1) HASHPART(h, *_hash_s1++);\
+ }
+
+typedef struct /* library private info */
+{
+ Hash_root_t* list; /* root table list */
+} Hash_info_t;
+
+extern Hash_info_t hash_info;
+
+#endif
diff --git a/src/lib/libast/hash/hashlook.c b/src/lib/libast/hash/hashlook.c
new file mode 100644
index 0000000..4b0ae81
--- /dev/null
+++ b/src/lib/libast/hash/hashlook.c
@@ -0,0 +1,367 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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);
+ }
+}
diff --git a/src/lib/libast/hash/hashscan.c b/src/lib/libast/hash/hashscan.c
new file mode 100644
index 0000000..5162c08
--- /dev/null
+++ b/src/lib/libast/hash/hashscan.c
@@ -0,0 +1,139 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 sequential scan
+ *
+ * Hash_position_t* pos;
+ * Hash_bucket_t* b;
+ * pos = hashscan(tab, flags);
+ * while (b = hashnext(&pos)) ...;
+ * hashdone(pos);
+ */
+
+/*
+ * return pos for scan on table
+ */
+
+Hash_position_t*
+hashscan(register Hash_table_t* tab, register int flags)
+{
+ register Hash_position_t* pos;
+
+ static Hash_bucket_t empty;
+
+ if (!(pos = newof(0, Hash_position_t, 1, 0))) return(0);
+ pos->tab = tab->root->last.table = tab;
+ pos->bucket = &empty;
+ pos->slot = tab->table - 1;
+ pos->limit = tab->table + tab->size;
+ if (tab->scope && !(flags & HASH_NOSCOPE))
+ {
+ pos->flags = HASH_SCOPE;
+ do
+ {
+ register Hash_bucket_t* b;
+
+ if (tab->frozen)
+ {
+ register Hash_bucket_t** sp = tab->table;
+ register Hash_bucket_t** sx = tab->table + tab->size;
+
+ while (sp < sx)
+ for (b = *sp++; b; b = b->next)
+ b->hash &= ~HASH_HIDDEN;
+ }
+ } while (tab = tab->scope);
+ tab = pos->tab;
+ }
+ else pos->flags = 0;
+ tab->frozen++;
+ return(pos);
+}
+
+/*
+ * return next scan element
+ */
+
+Hash_bucket_t*
+hashnext(register Hash_position_t* pos)
+{
+ register Hash_bucket_t* b;
+
+ if (!pos) return(0);
+ b = pos->bucket;
+ for (;;)
+ {
+ if (!(b = b->next))
+ {
+ do
+ {
+ if (++pos->slot >= pos->limit)
+ {
+ pos->tab->frozen--;
+ if (!pos->flags || !pos->tab->scope) return(0);
+ pos->tab = pos->tab->scope;
+ pos->tab->root->last.table = pos->tab;
+ pos->limit = (pos->slot = pos->tab->table) + pos->tab->size;
+ pos->tab->frozen++;
+ }
+ } while (!(b = *pos->slot));
+ }
+ if (!(b->hash & HASH_DELETED) && (!(pos->tab->flags & HASH_VALUE) || b->value) && (!pos->flags || !(b->hash & (HASH_HIDDEN|HASH_HIDES)))) break;
+ if (b->hash & HASH_HIDES)
+ {
+ register Hash_bucket_t* h = (Hash_bucket_t*)b->name;
+
+ if (!(h->hash & HASH_HIDDEN))
+ {
+ h->hash |= HASH_HIDDEN;
+ if (!(b->hash & HASH_DELETED)) break;
+ }
+ }
+ else b->hash &= ~HASH_HIDDEN;
+ }
+ return(pos->tab->root->last.bucket = pos->bucket = b);
+}
+
+/*
+ * terminate scan
+ */
+
+void
+hashdone(register Hash_position_t* pos)
+{
+ if (pos)
+ {
+ if (pos->tab->frozen)
+ pos->tab->frozen--;
+ free(pos);
+ }
+}
diff --git a/src/lib/libast/hash/hashsize.c b/src/lib/libast/hash/hashsize.c
new file mode 100644
index 0000000..0c458ba
--- /dev/null
+++ b/src/lib/libast/hash/hashsize.c
@@ -0,0 +1,84 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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"
+
+/*
+ * change table size and rehash
+ * size must be a power of 2
+ */
+
+void
+hashsize(register Hash_table_t* tab, int size)
+{
+ register Hash_bucket_t** old_s;
+ register Hash_bucket_t** new_s;
+ register Hash_bucket_t* old_b;
+ register Hash_bucket_t* new_b;
+ Hash_bucket_t** old_sx;
+ unsigned int index;
+ Hash_region_f region;
+ void* handle;
+
+ if (size > 0 && size != tab->size && !(size & (size - 1)))
+ {
+ if (region = tab->root->local->region)
+ {
+ handle = tab->root->local->handle;
+ new_s = (Hash_bucket_t**)(*region)(handle, NiL, sizeof(Hash_bucket_t*) * size, 0);
+ }
+ else new_s = newof(0, Hash_bucket_t*, size, 0);
+ if (!new_s) tab->flags |= HASH_FIXED;
+ else
+ {
+ old_sx = (old_s = tab->table) + tab->size;
+ tab->size = size;
+ while (old_s < old_sx)
+ {
+ old_b = *old_s++;
+ while (old_b)
+ {
+ new_b = old_b;
+ old_b = old_b->next;
+ index = new_b->hash;
+ HASHMOD(tab, index);
+ new_b->next = new_s[index];
+ new_s[index] = new_b;
+ }
+ }
+ if ((tab->flags & (HASH_RESIZE|HASH_STATIC)) != HASH_STATIC)
+ {
+ if (region) (*region)(handle, tab->table, 0, 0);
+ else free(tab->table);
+ }
+ tab->table = new_s;
+ tab->flags |= HASH_RESIZE;
+ }
+ }
+}
diff --git a/src/lib/libast/hash/hashview.c b/src/lib/libast/hash/hashview.c
new file mode 100644
index 0000000..585f1a1
--- /dev/null
+++ b/src/lib/libast/hash/hashview.c
@@ -0,0 +1,88 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * push/pop/query hash table scope
+ *
+ * bot==0 pop top scope
+ * bot==top query
+ * bot!=0 push top on bot
+ *
+ * scope table pointer returned
+ */
+
+Hash_table_t*
+hashview(Hash_table_t* top, Hash_table_t* bot)
+{
+ register Hash_bucket_t* b;
+ register Hash_bucket_t* p;
+ register Hash_bucket_t** sp;
+ register Hash_bucket_t** sx;
+
+ if (!top || top->frozen)
+ bot = 0;
+ else if (top == bot)
+ bot = top->scope;
+ else if (bot)
+ {
+ if (top->scope)
+ bot = 0;
+ else
+ {
+ sx = &top->table[top->size];
+ sp = &top->table[0];
+ while (sp < sx)
+ for (b = *sp++; b; b = b->next)
+ if (p = (Hash_bucket_t*)hashlook(bot, b->name, HASH_LOOKUP, NiL))
+ {
+ b->name = (p->hash & HASH_HIDES) ? p->name : (char*)b;
+ b->hash |= HASH_HIDES;
+ }
+ top->scope = bot;
+ bot->frozen++;
+ }
+ }
+ else if (bot = top->scope)
+ {
+ sx = &top->table[top->size];
+ sp = &top->table[0];
+ while (sp < sx)
+ for (b = *sp++; b; b = b->next)
+ if (b->hash & HASH_HIDES)
+ {
+ b->hash &= ~HASH_HIDES;
+ b->name = ((Hash_bucket_t*)b->name)->name;
+ }
+ top->scope = 0;
+ bot->frozen--;
+ }
+ return(bot);
+}
diff --git a/src/lib/libast/hash/hashwalk.c b/src/lib/libast/hash/hashwalk.c
new file mode 100644
index 0000000..d3e4610
--- /dev/null
+++ b/src/lib/libast/hash/hashwalk.c
@@ -0,0 +1,51 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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"
+
+/*
+ * apply walker to each active bucket in the table
+ */
+
+int
+hashwalk(Hash_table_t* tab, int flags, register int (*walker)(const char*, char*, void*), void* handle)
+{
+ register Hash_bucket_t* b;
+ register int v;
+ Hash_position_t* pos;
+
+ if (!(pos = hashscan(tab, flags)))
+ return(-1);
+ v = 0;
+ while (b = hashnext(pos))
+ if ((v = (*walker)(hashname(b), (tab->flags & HASH_VALUE) ? b->value : (char*)b, handle)) < 0)
+ break;
+ hashdone(pos);
+ return(v);
+}
diff --git a/src/lib/libast/hash/memhash.c b/src/lib/libast/hash/memhash.c
new file mode 100644
index 0000000..24f6465
--- /dev/null
+++ b/src/lib/libast/hash/memhash.c
@@ -0,0 +1,45 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * return the hash of buffer s of length n
+ */
+
+unsigned int
+memhash(const void* as, int n)
+{
+ register const unsigned char* s = (const unsigned char*)as;
+ register const unsigned char* e = s + n;
+ register unsigned int c = 0;
+
+ while (s < e) HASHPART(c, *s++);
+ return(c);
+}
diff --git a/src/lib/libast/hash/memsum.c b/src/lib/libast/hash/memsum.c
new file mode 100644
index 0000000..c426215
--- /dev/null
+++ b/src/lib/libast/hash/memsum.c
@@ -0,0 +1,53 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * return a running 32 bit checksum of buffer b of length n
+ *
+ * c is the return value from a previous
+ * memsum() or strsum() call, 0 on the first call
+ *
+ * the result is the same on all implementations
+ */
+
+unsigned long
+memsum(const void* ap, int n, register unsigned long c)
+{
+ register const unsigned char* p = (const unsigned char*)ap;
+ register const unsigned char* e = p + n;
+
+ while (p < e) HASHPART(c, *p++);
+#if LONG_MAX > 2147483647
+ return(c & 0xffffffff);
+#else
+ return(c);
+#endif
+}
diff --git a/src/lib/libast/hash/strhash.c b/src/lib/libast/hash/strhash.c
new file mode 100644
index 0000000..e9f4976
--- /dev/null
+++ b/src/lib/libast/hash/strhash.c
@@ -0,0 +1,45 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * return the hash of the null terminated string s
+ */
+
+unsigned int
+strhash(const char* as)
+{
+ register const unsigned char* s = (const unsigned char*)as;
+ register unsigned int i = 0;
+ register unsigned int c;
+
+ while (c = *s++) HASHPART(i, c);
+ return(i);
+}
diff --git a/src/lib/libast/hash/strkey.c b/src/lib/libast/hash/strkey.c
new file mode 100644
index 0000000..3ff7ead
--- /dev/null
+++ b/src/lib/libast/hash/strkey.c
@@ -0,0 +1,49 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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
+ */
+
+#include <ast.h>
+#include <hashkey.h>
+
+long
+strkey(register const char* s)
+{
+ register long x = 0;
+ register int n = 0;
+ register int c;
+
+ while (n++ < HASHKEYMAX)
+ {
+ c = *s;
+ if (c >= 'a' && c <= 'z')
+ x = HASHKEYPART(x, c);
+ else if (c >= '0' && c <= '9')
+ x = HASHKEYPART(x, HASHKEYN(c));
+ else break;
+ s++;
+ }
+ return x;
+}
diff --git a/src/lib/libast/hash/strsum.c b/src/lib/libast/hash/strsum.c
new file mode 100644
index 0000000..92b413d
--- /dev/null
+++ b/src/lib/libast/hash/strsum.c
@@ -0,0 +1,53 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* 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 Bell Laboratories
+ *
+ * hash table library
+ */
+
+#include "hashlib.h"
+
+/*
+ * return a running 32 bit checksum of string s
+ *
+ * c is the return value from a previous
+ * memsum() or strsum() call, 0 on the first call
+ *
+ * the result is the same on all implementations
+ */
+
+unsigned long
+strsum(const char* as, register unsigned long c)
+{
+ register const unsigned char* s = (const unsigned char*)as;
+ register int n;
+
+ while (n = *s++) HASHPART(c, n);
+#if LONG_MAX > 2147483647
+ return(c & 0xffffffff);
+#else
+ return(c);
+#endif
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-20 14:34:09 +0000