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