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