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 Research 26 * 27 * hash table library 28 */ 29 30 #include "hashlib.h" 31 32 /* 33 * hash table sequential scan 34 * 35 * Hash_position_t* pos; 36 * Hash_bucket_t* b; 37 * pos = hashscan(tab, flags); 38 * while (b = hashnext(&pos)) ...; 39 * hashdone(pos); 40 */ 41 42 /* 43 * return pos for scan on table 44 */ 45 46 Hash_position_t* 47 hashscan(register Hash_table_t* tab, register int flags) 48 { 49 register Hash_position_t* pos; 50 51 static Hash_bucket_t empty; 52 53 if (!(pos = newof(0, Hash_position_t, 1, 0))) return(0); 54 pos->tab = tab->root->last.table = tab; 55 pos->bucket = ∅ 56 pos->slot = tab->table - 1; 57 pos->limit = tab->table + tab->size; 58 if (tab->scope && !(flags & HASH_NOSCOPE)) 59 { 60 pos->flags = HASH_SCOPE; 61 do 62 { 63 register Hash_bucket_t* b; 64 65 if (tab->frozen) 66 { 67 register Hash_bucket_t** sp = tab->table; 68 register Hash_bucket_t** sx = tab->table + tab->size; 69 70 while (sp < sx) 71 for (b = *sp++; b; b = b->next) 72 b->hash &= ~HASH_HIDDEN; 73 } 74 } while (tab = tab->scope); 75 tab = pos->tab; 76 } 77 else pos->flags = 0; 78 tab->frozen++; 79 return(pos); 80 } 81 82 /* 83 * return next scan element 84 */ 85 86 Hash_bucket_t* 87 hashnext(register Hash_position_t* pos) 88 { 89 register Hash_bucket_t* b; 90 91 if (!pos) return(pos->tab->root->last.bucket = 0); 92 b = pos->bucket; 93 for (;;) 94 { 95 if (!(b = b->next)) 96 { 97 do 98 { 99 if (++pos->slot >= pos->limit) 100 { 101 pos->tab->frozen--; 102 if (!pos->flags || !pos->tab->scope) return(0); 103 pos->tab = pos->tab->scope; 104 pos->tab->root->last.table = pos->tab; 105 pos->limit = (pos->slot = pos->tab->table) + pos->tab->size; 106 pos->tab->frozen++; 107 } 108 } while (!(b = *pos->slot)); 109 } 110 if (!(b->hash & HASH_DELETED) && (!(pos->tab->flags & HASH_VALUE) || b->value) && (!pos->flags || !(b->hash & (HASH_HIDDEN|HASH_HIDES)))) break; 111 if (b->hash & HASH_HIDES) 112 { 113 register Hash_bucket_t* h = (Hash_bucket_t*)b->name; 114 115 if (!(h->hash & HASH_HIDDEN)) 116 { 117 h->hash |= HASH_HIDDEN; 118 if (!(b->hash & HASH_DELETED)) break; 119 } 120 } 121 else b->hash &= ~HASH_HIDDEN; 122 } 123 return(pos->tab->root->last.bucket = pos->bucket = b); 124 } 125 126 /* 127 * terminate scan 128 */ 129 130 void 131 hashdone(register Hash_position_t* pos) 132 { 133 if (pos) 134 { 135 if (pos->tab->frozen) 136 pos->tab->frozen--; 137 free(pos); 138 } 139 } 140