Return to pa_hash.h CVS log

Up to [parser3project] / parser3 / src / include

Annotation of parser3/src/include/pa_hash.h, revision 1.8

1.1       paf         1: /*
1.8     ! paf         2:   $Id: pa_hash.h,v 1.7 2001/01/29 11:53:42 paf Exp $
1.1       paf         3: */
                      4: 
                      5: /*
                      6: 
                      7: 
                      8: */
                      9: 
                     10: #ifndef PA_HASH_H
                     11: #define PA_HASH_H
                     12: 
                     13: #include <stddef.h>
                     14: 
                     15: #include "pa_types.h"
                     16: #include "pa_string.h"
                     17: 
                     18: class Pool;
                     19: 
                     20: class Hash {
                     21: public:
                     22: 
1.3       paf        23:        typedef String Key;
                     24:        typedef void Value;
                     25: 
1.8     ! paf        26: public:
        !            27: 
        !            28:        // useful generic hash function
        !            29:        static uint generic_code(uint aresult, char *start, uint size);
        !            30: 
        !            31:        // put a [value] under the [key]
        !            32:        /*SYNCHRONIZED*/ void put(Key& key, Value *value);
        !            33: 
        !            34:        // get associated [value] by the [key]
        !            35:        /*SYNCHRONIZED*/ Value* get(Key& key);
        !            36: 
1.1       paf        37: private:
                     38:        friend Pool;
                     39: 
1.6       paf        40:        // expand when these %% of size exausted
1.1       paf        41:        enum {
                     42:                THRESHOLD_PERCENT=75
                     43:        };
                     44: 
                     45:        // the pool I'm allocated on
                     46:        Pool *pool;
                     47: 
1.5       paf        48:        // the index of [size] in [sizes]
1.1       paf        49:        int size_index;
                     50: 
1.5       paf        51:        // possible [sizes]. prime numbers
1.1       paf        52:        static uint sizes[];
                     53:        static int sizes_count;
                     54: 
                     55:        // number of allocated pairs
                     56:        int size;
                     57: 
                     58:        // helper: expanding when used == threshold
                     59:        int threshold;
                     60: 
                     61:        // used pairs
                     62:        int used;
                     63: 
                     64:        // main storage
                     65:        class Pair {
1.2       paf        66:                friend Hash;
                     67: 
1.1       paf        68:                uint code;
                     69:                Key key;
                     70:                Value *value;
                     71:                Pair *link;
1.2       paf        72:                
                     73:                void *operator new(size_t size, Pool *apool);
                     74: 
                     75:                Pair(uint acode, Key& akey, Value *avalue, Pair *alink) :
1.1       paf        76:                        code(acode),
                     77:                        key(akey),
                     78:                        value(avalue),
1.2       paf        79:                        link(alink) {}
                     80:        } **refs;
1.1       paf        81: 
                     82:        // new&constructors made private to enforce factory manufacturing at pool
1.2       paf        83:        void *operator new(size_t size, Pool *apool);
1.1       paf        84: 
                     85:        Hash(Pool *apool);
                     86: 
1.5       paf        87:        // filled to threshold: needs expanding
                     88:        bool full() { return used==threshold; }
                     89: 
                     90:        // allocate larger buffer & rehash
1.1       paf        91:        void expand();
1.4       paf        92: 
                     93: private: //disabled
                     94: 
                     95:        Hash& operator = (Hash& src) { return *this; }
                     96:        Hash(Hash& src) {}
1.1       paf        97: };
                     98: 
                     99: #endif