Return to pa_hash.C CVS log

Up to [parser3project] / parser3 / src / main

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

1.1     ! paf         1: /*
        !             2:   $Id: pa_Hash.C,v 1.4 2001/01/26 15:38:34 paf Exp $
        !             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: 
        !            13: #include "pa_pool.h"
        !            14: 
        !            15: /* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
        !            16: uint Hash::sizes[]={
        !            17:        5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 
        !            18:        16229, 32531, 65407, 130987, 262237, 524521, 1048793, 
        !            19:        2097397, 4194103, 8388857, 16777447, 33554201, 67108961, 
        !            20:        134217487, 268435697, 536870683, 1073741621, 2147483399};
        !            21: int Hash::sizes_count=
        !            22:        sizeof(sizes)/sizeof(uint);
        !            23: 
        !            24: void *Hash::operator new(size_t size, Pool *apool) {
        !            25:        return apool->malloc(size);
        !            26: }
        !            27: 
        !            28: Hash::Hash(Pool *apool) {
        !            29:        pool=apool;
        !            30:        
        !            31:        size=sizes[size_index=0];
        !            32:        threshold=size*100/THRESHOLD_PERCENT;
        !            33:        used=0;
        !            34:        pair_refs=static_cast<Pair **>(pool->calloc(sizeof(Pair *)*size));
        !            35: }
        !            36: 
        !            37: void Hash::expand() {
        !            38:        int new_size_index=size_index+1<sizes_count?size_index+1:sizes_count-1;
        !            39:        int new_size=sizes[new_size_index];
        !            40:        Pair **new_pair_refs=static_cast<Pair **>(pool->calloc(sizeof(Pair *)*new_size));
        !            41: 
        !            42:        // rehash
        !            43: 
        !            44:        size=new_size;  size_index=new_size_index;
        !            45:        pair_refs=new_pair_refs;
        !            46: }
        !            47: 
        !            48: uint Hash::generic_code(uint aresult, char *start, uint size) {
        !            49:        return 0;
        !            50:        uint result=aresult, g;
        !            51:        char *end=start+size;
        !            52: 
        !            53:        while (start<end) {
        !            54:                result=(result<<4)+*start++;
        !            55:                if ((g=(result&0xF0000000))) {
        !            56:                        result=result^(g>>24);
        !            57:                        result=result^g;
        !            58:                }
        !            59:        }
        !            60:        return result;
        !            61: }
        !            62: 
        !            63: void Hash::put(Key& akey, Value *avalue) {
        !            64:        if(full()) 
        !            65:                expand();
        !            66: 
        !            67:        uint index=akey.hash_code()%size;
        !            68:        Pair *pair=&pairs[index];
        !            69:        if(pair->used) {
        !            70:                Pair *prev_pair=pair;
        !            71:                for(; pair; pair=pair->link) {
        !            72:                        if(pair->key==akey) { // found a pair with the same key
        !            73:                                pair->value=avalue;
        !            74:                                return;
        !            75:                        }
        !            76:                        prev_pair=pair;
        !            77:                }
        !            78: 
        !            79:                // not found proper pair -- create&link_in new pair
        !            80:                Pair *new_pair=static_cast<Pair *>(pool->malloc(sizeof(Pair)));
        !            81:                new_pair->used=true;
        !            82:                new_pair->key=akey;
        !            83:                new_pair->value=avalue;
        !            84:                new_pair->link=0;
        !            85:                prev_pair->link=new_pair;       
        !            86:        }
        !            87:        pair->used=true;
        !            88:        pair->key=akey;
        !            89:        pair->value=avalue;
        !            90: }
        !            91: 
        !            92: Value* Hash::get(Key& key) {
        !            93:        uint code=akey.hash_code();
        !            94:        uint index=code%size;
        !            95:        for(Pair *pair=&pairs[index]; pair; pair=pair->link)
        !            96:                if(pair->code==code && pair->key==key)
        !            97:                        return pair->value;
        !            98:        
        !            99:        return 0;
        !           100: }