Annotation of parser3/src/main/pa_hash.C, revision 1.17
1.1 paf 1: /*
1.17 ! paf 2: $Id: pa_hash.C,v 1.16 2001/02/23 14:18:27 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 */
21: uint Hash::sizes[]={
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};
26: int Hash::sizes_count=
27: sizeof(sizes)/sizeof(uint);
28:
29:
1.13 paf 30: void Hash::construct(Pool& apool, bool athread_safe) {
31: thread_safe=athread_safe;
1.1 paf 32:
33: size=sizes[size_index=0];
1.2 paf 34: threshold=size*THRESHOLD_PERCENT/100;
1.1 paf 35: used=0;
1.14 paf 36: refs=static_cast<Pair **>(calloc(sizeof(Pair *)*size));
1.1 paf 37: }
38:
39: void Hash::expand() {
1.2 paf 40: int old_size=size;
41: Pair **old_refs=refs;
1.4 paf 42:
1.2 paf 43: // allocated bigger refs array
44: size_index=size_index+1<sizes_count?size_index+1:sizes_count-1;
45: size=sizes[size_index];
1.14 paf 46: refs=static_cast<Pair **>(calloc(sizeof(Pair *)*size));
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:
54: uint new_index=pair->code%size;
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.9 paf 63: uint Hash::generic_code(uint aresult, const char *start, uint size) {
1.1 paf 64: uint result=aresult, g;
1.9 paf 65: const char *end=start+size;
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();
82: uint index=code%size;
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.1 paf 100: uint index=code%size;
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();
110: uint index=code%size;
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();
! 127: uint index=code%size;
! 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);
! 143: for(int i=0; i<src.size; i++)
! 144: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
! 145: put_dont_replace(pair->key, pair->value);
! 146: // MAY:optimize this.size==src.size case
! 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