66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf/***********************************************************************
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* This software is part of the ast package *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Copyright (c) 1985-2011 AT&T Intellectual Property *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* and is licensed under the *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Common Public License, Version 1.0 *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* by AT&T Intellectual Property *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* A copy of the License is available at *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* http://www.opensource.org/licenses/cpl1.0.txt *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Information and Software Systems Research *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* AT&T Research *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Florham Park NJ *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Glenn Fowler <gsf@research.att.com> *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* David Korn <dgk@research.att.com> *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* Phong Vo <kpv@research.att.com> *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf* *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf***********************************************************************/
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf#pragma prototyped
c75976d12071ddd21443266260066ba036671682pawelw/*
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * Glenn Fowler
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * AT&T Bell Laboratories
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf *
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * hash table library
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf */
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf#include "hashlib.h"
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf/*
2038334ab26baaa43c9083f35def041511c3cc1fUnknown * dump HASH_* flags
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf */
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfstatic void
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfdumpflags(register int flags)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf{
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (flags & HASH_ALLOCATE) sfprintf(sfstderr, "allocate ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (flags & HASH_BUCKET) sfprintf(sfstderr, "bucket ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (flags & HASH_FIXED) sfprintf(sfstderr, "fixed ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (flags & HASH_HASHED) sfprintf(sfstderr, "hashed ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (flags & HASH_RESIZE) sfprintf(sfstderr, "resize ");
f76ee27a7c2e4dbe22aec6ce187c04e980f90349pawelw if (flags & HASH_STATIC) sfprintf(sfstderr, "static ");
f76ee27a7c2e4dbe22aec6ce187c04e980f90349pawelw if (flags & HASH_VALUE) sfprintf(sfstderr, "value ");
f76ee27a7c2e4dbe22aec6ce187c04e980f90349pawelw}
7a1efdfee8cbdecea34d3d866bbfb46e39b06e0apawelw
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf/*
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * dump hash table bucket info
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf */
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfstatic void
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfdumpbucket(register Hash_table_t* tab, int flags)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf{
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf register Hash_bucket_t** sp;
ae8faf9c0cd738ab78a672de5bf7e7f7d004ebb2ls register Hash_bucket_t* b;
2038334ab26baaa43c9083f35def041511c3cc1fUnknown Hash_bucket_t** sx;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf int n;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf unsigned char* s;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf NoP(flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sx = tab->table + tab->size;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf for (sp = tab->table; sp < sx; sp++)
37a077ef1920ee044b2887247b2a802e726d3368ls {
37a077ef1920ee044b2887247b2a802e726d3368ls n = 0;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf for (b = *sp; b; b = b->next)
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw n++;
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw if (n)
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw {
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw sfprintf(sfstderr, "%5d %2d :", sp - tab->table, n);
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw for (b = *sp; b; b = b->next)
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw {
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw if (n = tab->root->namesize)
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw {
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw sfprintf(sfstderr, " 0x");
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw s = (unsigned char*)hashname(b);
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw while (n-- > 0)
6f9b9bf43c10fb1741a40302efe9db1a139745c8pawelw sfprintf(sfstderr, "%02x", *s++);
c75976d12071ddd21443266260066ba036671682pawelw }
c75976d12071ddd21443266260066ba036671682pawelw else sfprintf(sfstderr, " %s", hashname(b));
c75976d12071ddd21443266260066ba036671682pawelw if (b->hash & HASH_FLAGS)
c75976d12071ddd21443266260066ba036671682pawelw {
c75976d12071ddd21443266260066ba036671682pawelw sfprintf(sfstderr, "|");
c75976d12071ddd21443266260066ba036671682pawelw if (b->hash & HASH_HIDES) sfprintf(sfstderr, "hides|");
c75976d12071ddd21443266260066ba036671682pawelw if (b->hash & HASH_HIDDEN) sfprintf(sfstderr, "hidden|");
c75976d12071ddd21443266260066ba036671682pawelw if (b->hash & HASH_KEEP) sfprintf(sfstderr, "keep|");
c75976d12071ddd21443266260066ba036671682pawelw if (b->hash & HASH_OPAQUED) sfprintf(sfstderr, "opaque|");
c75976d12071ddd21443266260066ba036671682pawelw }
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (tab->flags & HASH_VALUE) sfprintf(sfstderr, "=0x%08lx", (long)b->value);
2038334ab26baaa43c9083f35def041511c3cc1fUnknown }
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
7a70ede882eacbae00c8d5209afb443e7755684cpawelw }
7a70ede882eacbae00c8d5209afb443e7755684cpawelw }
2038334ab26baaa43c9083f35def041511c3cc1fUnknown sfprintf(sfstderr, "\n");
2038334ab26baaa43c9083f35def041511c3cc1fUnknown}
2038334ab26baaa43c9083f35def041511c3cc1fUnknown
2038334ab26baaa43c9083f35def041511c3cc1fUnknown/*
2038334ab26baaa43c9083f35def041511c3cc1fUnknown * dump info on a single table
2038334ab26baaa43c9083f35def041511c3cc1fUnknown */
2038334ab26baaa43c9083f35def041511c3cc1fUnknown
2038334ab26baaa43c9083f35def041511c3cc1fUnknownstatic void
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfdumptable(register Hash_table_t* tab, register int flags)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf{
2038334ab26baaa43c9083f35def041511c3cc1fUnknown Hash_table_t* scope;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf int level;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
2038334ab26baaa43c9083f35def041511c3cc1fUnknown sfprintf(sfstderr, " name: %s", tab->name ? tab->name : "*no name*");
2038334ab26baaa43c9083f35def041511c3cc1fUnknown if (scope = tab->scope)
2038334ab26baaa43c9083f35def041511c3cc1fUnknown {
2038334ab26baaa43c9083f35def041511c3cc1fUnknown level = 1;
8d483882aa3390058094b043f3d62187b5d1de03mlf while (scope = scope->scope) level++;
8d483882aa3390058094b043f3d62187b5d1de03mlf sfprintf(sfstderr, " level %d scope on 0x%08lx", level, (unsigned long)tab->scope);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf }
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)tab);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " flags: ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (tab->frozen) sfprintf(sfstderr, "frozen=%d ", tab->frozen);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf dumpflags(tab->flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " size: %d\n", tab->size);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " buckets: %d\n", tab->buckets);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " bucketsize: %d\n", tab->bucketsize * sizeof(char*));
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if ((flags | tab->flags) & HASH_BUCKET) dumpbucket(tab, flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf}
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf/*
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * dump hash table root info
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf */
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfstatic void
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlfdumproot(register Hash_root_t* root, register int flags)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf{
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf register Hash_table_t* tab;
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " root\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)root);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " flags: ");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf dumpflags(root->flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (root->namesize) sfprintf(sfstderr, "namesize=%d ", root->namesize);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (root->local->alloc) sfprintf(sfstderr, "alloc=0x%08lx ", (unsigned long)root->local->alloc);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (root->local->compare) sfprintf(sfstderr, "compare=0x%08lx ", (unsigned long)root->local->compare);
2038334ab26baaa43c9083f35def041511c3cc1fUnknown if (root->local->free) sfprintf(sfstderr, "free=0x%08lx ", (unsigned long)root->local->free);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (root->local->hash) sfprintf(sfstderr, "hash=0x%08lx ", (unsigned long)root->local->hash);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (root->local->region) sfprintf(sfstderr, "region=0x%08lx handle=0x%08lx ", (unsigned long)root->local->region, (unsigned long)root->local->handle);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " meanchain: %d\n", root->meanchain);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " accesses: %d\n", root->accesses);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, " collisions: %d\n", root->collisions);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfprintf(sfstderr, "\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf for (tab = root->references; tab; tab = tab->next)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf dumptable(tab, flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf}
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf/*
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * dump hash table accounting info
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * if tab is 0 then dump all tables in hash_info.list
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf * flags are HASH_* flags that specifiy optional dump info
4360436b3c604bc28d37be269ad152b4c38157c3pawelw */
4360436b3c604bc28d37be269ad152b4c38157c3pawelw
c75976d12071ddd21443266260066ba036671682pawelwvoid
c75976d12071ddd21443266260066ba036671682pawelwhashdump(register Hash_table_t* tab, int flags)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf{
2038334ab26baaa43c9083f35def041511c3cc1fUnknown register Hash_root_t* root;
2038334ab26baaa43c9083f35def041511c3cc1fUnknown
2038334ab26baaa43c9083f35def041511c3cc1fUnknown sfprintf(sfstderr, "\nhash table information:\n\n");
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf if (tab) dumproot(tab->root, flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf else for (root = hash_info.list; root; root = root->next)
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf dumproot(root, flags);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf sfsync(sfstderr);
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf}
66f9d5cb3cc0652e2d9d1366fb950efbe4ca2f24mlf