Return to pa_hash.C CVS log

Up to [parser3project] / parser3 / src / main

Annotation of parser3/src/main/pa_hash.C, revision 1.16

1.1       paf         1: /*
1.16    ! paf         2:   $Id: pa_hash.C,v 1.15 2001/02/22 11:08:25 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.10      paf        77: void 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;
                     88:                        return;
1.1       paf        89:                }
1.2       paf        90:        
1.7       paf        91:        // proper pair not found -- create&link_in new pair
1.15      paf        92:        *ref=NEW Pair(code, key, value, *ref);
1.1       paf        93: }
                     94: 
1.13      paf        95: Hash::Value *Hash::get(const Key& key) const {  SYNCHRONIZED(thread_safe);
1.2       paf        96:        uint code=key.hash_code();
1.1       paf        97:        uint index=code%size;
1.2       paf        98:        for(Pair *pair=refs[index]; pair; pair=pair->link)
1.1       paf        99:                if(pair->code==code && pair->key==key)
                    100:                        return pair->value;
                    101:        
                    102:        return 0;
                    103: }
1.16    ! paf       104: 
        !           105: bool Hash::replace(const Key& key, Value *value) {  SYNCHRONIZED(thread_safe);
        !           106:        uint code=key.hash_code();
        !           107:        uint index=code%size;
        !           108:        for(Pair *pair=refs[index]; pair; pair=pair->link)
        !           109:                if(pair->code==code && pair->key==key) {
        !           110:                        // found a pair with the same key, replacing
        !           111:                        pair->value=value;
        !           112:                        return true;
        !           113:                }
        !           114: 
        !           115:        // proper pair not found 
        !           116:        return false;
        !           117: }
        !           118: