1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24 * Glenn Fowler
25 * AT&T Bell Laboratories
26 *
27 * hash table library
28 */
29
30 #include "hashlib.h"
31
32 /*
33 * dump HASH_* flags
34 */
35
36 static void
dumpflags(register int flags)37 dumpflags(register int flags)
38 {
39 if (flags & HASH_ALLOCATE) sfprintf(sfstderr, "allocate ");
40 if (flags & HASH_BUCKET) sfprintf(sfstderr, "bucket ");
41 if (flags & HASH_FIXED) sfprintf(sfstderr, "fixed ");
42 if (flags & HASH_HASHED) sfprintf(sfstderr, "hashed ");
43 if (flags & HASH_RESIZE) sfprintf(sfstderr, "resize ");
44 if (flags & HASH_STATIC) sfprintf(sfstderr, "static ");
45 if (flags & HASH_VALUE) sfprintf(sfstderr, "value ");
46 }
47
48 /*
49 * dump hash table bucket info
50 */
51
52 static void
dumpbucket(register Hash_table_t * tab,int flags)53 dumpbucket(register Hash_table_t* tab, int flags)
54 {
55 register Hash_bucket_t** sp;
56 register Hash_bucket_t* b;
57 Hash_bucket_t** sx;
58 int n;
59 unsigned char* s;
60
61 NoP(flags);
62 sx = tab->table + tab->size;
63 for (sp = tab->table; sp < sx; sp++)
64 {
65 n = 0;
66 for (b = *sp; b; b = b->next)
67 if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
68 n++;
69 if (n)
70 {
71 sfprintf(sfstderr, "%5d %2d :", sp - tab->table, n);
72 for (b = *sp; b; b = b->next)
73 if (!(b->hash & HASH_DELETED) && (!(tab->flags & HASH_VALUE) || b->value))
74 {
75 if (n = tab->root->namesize)
76 {
77 sfprintf(sfstderr, " 0x");
78 s = (unsigned char*)hashname(b);
79 while (n-- > 0)
80 sfprintf(sfstderr, "%02x", *s++);
81 }
82 else sfprintf(sfstderr, " %s", hashname(b));
83 if (b->hash & HASH_FLAGS)
84 {
85 sfprintf(sfstderr, "|");
86 if (b->hash & HASH_HIDES) sfprintf(sfstderr, "hides|");
87 if (b->hash & HASH_HIDDEN) sfprintf(sfstderr, "hidden|");
88 if (b->hash & HASH_KEEP) sfprintf(sfstderr, "keep|");
89 if (b->hash & HASH_OPAQUED) sfprintf(sfstderr, "opaque|");
90 }
91 if (tab->flags & HASH_VALUE) sfprintf(sfstderr, "=0x%08lx", (long)b->value);
92 }
93 sfprintf(sfstderr, "\n");
94 }
95 }
96 sfprintf(sfstderr, "\n");
97 }
98
99 /*
100 * dump info on a single table
101 */
102
103 static void
dumptable(register Hash_table_t * tab,register int flags)104 dumptable(register Hash_table_t* tab, register int flags)
105 {
106 Hash_table_t* scope;
107 int level;
108
109 sfprintf(sfstderr, " name: %s", tab->name ? tab->name : "*no name*");
110 if (scope = tab->scope)
111 {
112 level = 1;
113 while (scope = scope->scope) level++;
114 sfprintf(sfstderr, " level %d scope on 0x%08lx", level, (unsigned long)tab->scope);
115 }
116 sfprintf(sfstderr, "\n");
117 sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)tab);
118 sfprintf(sfstderr, " flags: ");
119 if (tab->frozen) sfprintf(sfstderr, "frozen=%d ", tab->frozen);
120 dumpflags(tab->flags);
121 sfprintf(sfstderr, "\n");
122 sfprintf(sfstderr, " size: %d\n", tab->size);
123 sfprintf(sfstderr, " buckets: %d\n", tab->buckets);
124 sfprintf(sfstderr, " bucketsize: %d\n", tab->bucketsize * sizeof(char*));
125 sfprintf(sfstderr, "\n");
126 if ((flags | tab->flags) & HASH_BUCKET) dumpbucket(tab, flags);
127 }
128
129 /*
130 * dump hash table root info
131 */
132
133 static void
dumproot(register Hash_root_t * root,register int flags)134 dumproot(register Hash_root_t* root, register int flags)
135 {
136 register Hash_table_t* tab;
137
138 sfprintf(sfstderr, " root\n");
139 sfprintf(sfstderr, " address: 0x%08lx\n", (unsigned long)root);
140 sfprintf(sfstderr, " flags: ");
141 dumpflags(root->flags);
142 if (root->namesize) sfprintf(sfstderr, "namesize=%d ", root->namesize);
143 if (root->local->alloc) sfprintf(sfstderr, "alloc=0x%08lx ", (unsigned long)root->local->alloc);
144 if (root->local->compare) sfprintf(sfstderr, "compare=0x%08lx ", (unsigned long)root->local->compare);
145 if (root->local->free) sfprintf(sfstderr, "free=0x%08lx ", (unsigned long)root->local->free);
146 if (root->local->hash) sfprintf(sfstderr, "hash=0x%08lx ", (unsigned long)root->local->hash);
147 if (root->local->region) sfprintf(sfstderr, "region=0x%08lx handle=0x%08lx ", (unsigned long)root->local->region, (unsigned long)root->local->handle);
148 sfprintf(sfstderr, "\n");
149 sfprintf(sfstderr, " meanchain: %d\n", root->meanchain);
150 sfprintf(sfstderr, " accesses: %d\n", root->accesses);
151 sfprintf(sfstderr, " collisions: %d\n", root->collisions);
152 sfprintf(sfstderr, "\n");
153 for (tab = root->references; tab; tab = tab->next)
154 dumptable(tab, flags);
155 }
156
157 /*
158 * dump hash table accounting info
159 * if tab is 0 then dump all tables in hash_info.list
160 * flags are HASH_* flags that specifiy optional dump info
161 */
162
163 void
hashdump(register Hash_table_t * tab,int flags)164 hashdump(register Hash_table_t* tab, int flags)
165 {
166 register Hash_root_t* root;
167
168 sfprintf(sfstderr, "\nhash table information:\n\n");
169 if (tab) dumproot(tab->root, flags);
170 else for (root = hash_info.list; root; root = root->next)
171 dumproot(root, flags);
172 sfsync(sfstderr);
173 }
174