Return to pa_hash.h CVS log

Up to [parser3project] / parser3 / src / include

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

1.28      paf         1: /** @file
1.29      paf         2:        Parser: hash class decl.
                      3: 
1.21      paf         4:        Copyright (c) 2001 ArtLebedev Group (http://www.artlebedev.com)
1.29      paf         5: 
1.22      paf         6:        Author: Alexander Petrosyan <paf@design.ru> (http://design.ru/paf)
1.1       paf         7: 
1.35    ! paf         8:        $Id: pa_hash.h,v 1.34 2001/04/04 10:50:34 paf Exp $
1.1       paf         9: */
                     10: 
                     11: #ifndef PA_HASH_H
                     12: #define PA_HASH_H
                     13: 
                     14: #include <stddef.h>
                     15: 
1.14      paf        16: #include "pa_pool.h"
1.1       paf        17: #include "pa_types.h"
                     18: #include "pa_string.h"
                     19: 
1.29      paf        20: 
                     21: /** 
                     22:        Pooled hash.
                     23: 
                     24:        Automatically rehashed when almost full.
                     25: */
1.23      paf        26: class Hash : public Pooled {
1.1       paf        27: public:
                     28: 
1.29      paf        29:        typedef String Key; ///< hash Key type. longing for templates
1.30      paf        30:        typedef void Val; ///< hash Val type. longing for templates
1.3       paf        31: 
1.31      paf        32:        /// for_each iterator function type
                     33:        typedef void (*For_each_func)(const Key& key, Val *value, void *info);
1.25      paf        34: 
1.8       paf        35: public:
                     36: 
1.35    ! paf        37:        Hash(Pool& apool) : Pooled(apool) { 
        !            38:                construct(apool); 
1.24      paf        39:        }
1.10      paf        40: 
1.29      paf        41:        /// useful generic hash function
1.19      paf        42:        static uint generic_code(uint aresult, const char *start, uint allocated);
1.8       paf        43: 
1.29      paf        44:        /// put a [value] under the [key], return existed or not
1.30      paf        45:        /*SYNCHRONIZED*/ bool put(const Key& key, Val *value);
1.33      paf        46: /*
                     47:        /// dirty hack to allow constant items storage. I long for Hash<const Val*>
                     48:        /*SYNCHRONIZED* / bool put(const Key& key, const Val *value) {
                     49:                return put(key, const_cast<Val *>(value)); 
                     50:        }
                     51: */
1.29      paf        52:        /// get associated [value] by the [key]
1.30      paf        53:        /*SYNCHRONIZED*/ Val *get(const Key& key) const;
1.17      paf        54: 
1.29      paf        55:        /// put a [value] under the [key] if that [key] existed, return existed or not
1.30      paf        56:        /*SYNCHRONIZED*/ bool put_replace(const Key& key, Val *value);
1.18      paf        57: 
1.29      paf        58:        /// put a [value] under the [key] if that [key] NOT existed, return existed or not
1.30      paf        59:        /*SYNCHRONIZED*/ bool put_dont_replace(const Key& key, Val *value);
1.18      paf        60: 
1.29      paf        61:        /// put all 'src' values if NO with same key existed
1.18      paf        62:        /*SYNCHRONIZED*/ void merge_dont_replace(const Hash& src);
1.11      paf        63: 
1.30      paf        64:        void put(const Key& key, int     value) { put(key, reinterpret_cast<Val *>(value)); }
                     65:        void put(const Key& key, String *value) { put(key, static_cast<Val *>(value)); }
1.11      paf        66: 
1.29      paf        67:        //@{
                     68:        /// handy get, longing for Hash<int>, Hash<String *>
1.32      paf        69:        int get_int(const Key& key) const { return reinterpret_cast<int>(get(key)); }
                     70:        const String *get_string(const Key& key) const { return static_cast<String *>(get(key)); }
1.29      paf        71:        //@}
1.10      paf        72: 
1.29      paf        73:        /// number of elements in hash
1.19      paf        74:        int size() { return used; }
1.25      paf        75: 
1.29      paf        76:        /// iterate over all not zero elements
1.31      paf        77:        void for_each(For_each_func func, void *info=0);
1.27      paf        78: 
1.29      paf        79:        /// remove all elements
1.27      paf        80:        void clear();
1.19      paf        81: 
1.15      paf        82: protected:
                     83: 
1.35    ! paf        84:        void construct(Pool& apool);
1.15      paf        85: 
1.1       paf        86: private:
                     87: 
1.19      paf        88:        // expand when these %% of allocated exausted
1.1       paf        89:        enum {
                     90:                THRESHOLD_PERCENT=75
                     91:        };
1.9       paf        92: 
1.19      paf        93:        // the index of [allocated] in [allocates]
                     94:        int allocates_index;
1.1       paf        95: 
1.19      paf        96:        // possible [allocates]. prime numbers
                     97:        static uint allocates[];
                     98:        static int allocates_count;
1.1       paf        99: 
                    100:        // number of allocated pairs
1.19      paf       101:        int allocated;
1.1       paf       102: 
                    103:        // helper: expanding when used == threshold
                    104:        int threshold;
                    105: 
                    106:        // used pairs
                    107:        int used;
                    108: 
                    109:        // main storage
                    110:        class Pair {
1.2       paf       111:                friend Hash;
                    112: 
1.1       paf       113:                uint code;
1.15      paf       114:                const Key key;
1.30      paf       115:                Val *value;
1.1       paf       116:                Pair *link;
1.2       paf       117:                
1.19      paf       118:                void *operator new(size_t allocated, Pool& apool);
1.2       paf       119: 
1.30      paf       120:                Pair(uint acode, const Key& akey, Val *avalue, Pair *alink) :
1.1       paf       121:                        code(acode),
                    122:                        key(akey),
                    123:                        value(avalue),
1.2       paf       124:                        link(alink) {}
                    125:        } **refs;
1.1       paf       126: 
1.5       paf       127:        // filled to threshold: needs expanding
                    128:        bool full() { return used==threshold; }
                    129: 
                    130:        // allocate larger buffer & rehash
1.1       paf       131:        void expand();
1.4       paf       132: 
                    133: private: //disabled
                    134: 
1.11      paf       135:        //Hash(Hash&) {}
1.12      paf       136:        Hash& operator = (const Hash&) { return *this; }
1.1       paf       137: };
                    138: 
                    139: #endif