Annotation of parser3/src/main/pa_hash.C, revision 1.45
1.25 paf 1: /** @file
1.26 paf 2: Parser: hash class.
3:
1.19 paf 4: Copyright (c) 2001 ArtLebedev Group (http://www.artlebedev.com)
1.40 parser 5: Author: Alexander Petrosyan <paf@design.ru> (http://design.ru/paf)
1.26 paf 6:
1.45 ! paf 7: $Id: pa_hash.C,v 1.44 2001/11/01 10:59:26 paf Exp $
1.1 paf 8: */
9:
10: /*
11: The prime numbers used from zend_hash.c,
12: the part of Zend scripting engine library,
13: Copyrighted (C) 1999-2000 Zend Technologies Ltd.
14: http://www.zend.com/license/0_92.txt
15: For more information about Zend please visit http://www.zend.com/
16: */
1.23 paf 17:
1.11 paf 18: #include "pa_hash.h"
1.45 ! paf 19: #include "pa_exception.h"
1.2 paf 20:
1.8 paf 21: void *Hash::Pair::operator new(size_t size, Pool& apool) {
1.43 paf 22: return apool.malloc(size, 6);
1.2 paf 23: }
24:
1.1 paf 25: /* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
1.18 paf 26: uint Hash::allocates[]={
1.1 paf 27: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
28: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
29: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
30: 134217487, 268435697, 536870683, 1073741621, 2147483399};
1.18 paf 31: int Hash::allocates_count=
32: sizeof(allocates)/sizeof(uint);
1.1 paf 33:
34:
1.39 parser 35: void Hash::construct_new() {
1.18 paf 36: allocated=allocates[allocates_index=0];
37: threshold=allocated*THRESHOLD_PERCENT/100;
1.41 parser 38: count=used=0;
1.18 paf 39: refs=static_cast<Pair **>(calloc(sizeof(Pair *)*allocated));
1.39 parser 40: }
41:
42: void Hash::construct_copy(const Hash& source) {
43: allocates_index=source.allocates_index;
44: allocated=source.allocated;
45: threshold=source.threshold;
46: used=source.used;
1.41 parser 47: count=source.count;
1.39 parser 48: size_t size=sizeof(Pair *)*allocated;
1.43 paf 49: refs=static_cast<Pair **>(malloc(size, 7)); memcpy(refs, source.refs, size);
1.1 paf 50: }
51:
52: void Hash::expand() {
1.18 paf 53: int old_size=allocated;
1.2 paf 54: Pair **old_refs=refs;
1.4 paf 55:
1.2 paf 56: // allocated bigger refs array
1.18 paf 57: allocates_index=allocates_index+1<allocates_count?allocates_index+1:allocates_count-1;
58: allocated=allocates[allocates_index];
1.33 paf 59: threshold=allocated*THRESHOLD_PERCENT/100;
1.18 paf 60: refs=static_cast<Pair **>(calloc(sizeof(Pair *)*allocated));
1.1 paf 61:
62: // rehash
1.2 paf 63: Pair **old_ref=old_refs;
64: for(int old_index=0; old_index<old_size; old_index++)
65: for(Pair *pair=*old_ref++; pair; ) {
66: Pair *linked_pair=pair->link;
67:
1.18 paf 68: uint new_index=pair->code%allocated;
1.2 paf 69: Pair **new_ref=&refs[new_index];
70: pair->link=*new_ref;
71: *new_ref=pair;
1.1 paf 72:
1.2 paf 73: pair=linked_pair;
74: }
1.1 paf 75: }
76:
1.18 paf 77: uint Hash::generic_code(uint aresult, const char *start, uint allocated) {
1.1 paf 78: uint result=aresult, g;
1.18 paf 79: const char *end=start+allocated;
1.1 paf 80:
81: while (start<end) {
82: result=(result<<4)+*start++;
83: if ((g=(result&0xF0000000))) {
84: result=result^(g>>24);
85: result=result^g;
86: }
87: }
88: return result;
89: }
90:
1.31 paf 91: bool Hash::put(const Key& key, Val *value) {
1.1 paf 92: if(full())
93: expand();
94:
1.2 paf 95: uint code=key.hash_code();
1.18 paf 96: uint index=code%allocated;
1.2 paf 97: Pair **ref=&refs[index];
98: for(Pair *pair=*ref; pair; pair=pair->link)
99: if(pair->code==code && pair->key==key) {
100: // found a pair with the same key
101: pair->value=value;
1.17 paf 102: return true;
1.1 paf 103: }
1.2 paf 104:
1.7 paf 105: // proper pair not found -- create&link_in new pair
1.17 paf 106: if(!*ref) // root cell were used?
107: used++; // not, we'll use it and record the fact
1.15 paf 108: *ref=NEW Pair(code, key, value, *ref);
1.41 parser 109: count++;
1.17 paf 110: return false;
1.1 paf 111: }
112:
1.44 paf 113: void Hash::remove(const Key& key) {
114: uint code=key.hash_code();
115: uint index=code%allocated;
116: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
117: if((*ref)->code==code && (*ref)->key==key) {
118: // found a pair with the same key
119: *ref=(*ref)->link;
120: --count;
121: return;
122: }
123: }
124:
1.31 paf 125: Hash::Val *Hash::get(const Key& key) const {
1.2 paf 126: uint code=key.hash_code();
1.18 paf 127: uint index=code%allocated;
1.2 paf 128: for(Pair *pair=refs[index]; pair; pair=pair->link)
1.1 paf 129: if(pair->code==code && pair->key==key)
130: return pair->value;
131:
132: return 0;
133: }
1.16 paf 134:
1.31 paf 135: bool Hash::put_replace(const Key& key, Val *value) {
1.16 paf 136: uint code=key.hash_code();
1.18 paf 137: uint index=code%allocated;
1.16 paf 138: for(Pair *pair=refs[index]; pair; pair=pair->link)
139: if(pair->code==code && pair->key==key) {
140: // found a pair with the same key, replacing
141: pair->value=value;
142: return true;
143: }
144:
145: // proper pair not found
146: return false;
147: }
148:
1.31 paf 149: bool Hash::put_dont_replace(const Key& key, Val *value) {
1.17 paf 150: if(full())
151: expand();
152:
153: uint code=key.hash_code();
1.18 paf 154: uint index=code%allocated;
1.17 paf 155: Pair **ref=&refs[index];
156: for(Pair *pair=*ref; pair; pair=pair->link)
157: if(pair->code==code && pair->key==key) {
158: // found a pair with the same key, NOT replacing
159: return true;
160: }
161:
162: // proper pair not found -- create&link_in new pair
163: if(!*ref) // root cell were used?
164: used++; // not, we'll use it and record the fact
1.41 parser 165: *ref=NEW Pair(code, key, value, *ref);
166: count++;
1.17 paf 167: return false;
168: }
169:
1.31 paf 170: void Hash::merge_dont_replace(const Hash& src) {
1.18 paf 171: for(int i=0; i<src.allocated; i++)
1.17 paf 172: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
173: put_dont_replace(pair->key, pair->value);
1.18 paf 174: // MAY:optimize this.allocated==src.allocated case
1.21 paf 175: }
176:
1.32 paf 177: void Hash::for_each(For_each_func func, void *info) const {
1.42 paf 178: Pair **ref=refs;
179: for(int index=0; index<allocated; index++)
180: for(Pair *pair=*ref++; pair; pair=pair->link)
1.44 paf 181: (*func)(pair->key, pair->value, info);
1.42 paf 182: }
183:
184: void Hash::for_each(For_each_func_refed func, void *info) const {
1.21 paf 185: Pair **ref=refs;
186: for(int index=0; index<allocated; index++)
187: for(Pair *pair=*ref++; pair; pair=pair->link)
1.44 paf 188: (*func)(pair->key, pair->value, info);
1.34 paf 189: }
190:
1.38 parser 191: void* Hash::first_that(First_that_func func, void *info) const {
1.34 paf 192: Pair **ref=refs;
193: for(int index=0; index<allocated; index++)
194: for(Pair *pair=*ref++; pair; pair=pair->link)
1.44 paf 195: if(void *result=(*func)(pair->key, pair->value, info))
196: return result;
1.34 paf 197: return 0;
1.23 paf 198: }
199:
1.31 paf 200: void Hash::clear() {
1.23 paf 201: memset(refs, 0, sizeof(*refs)*allocated);
1.41 parser 202: count=used=0;
1.17 paf 203: }
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_hash.C CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / main