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