1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 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 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 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 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 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 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