Return to pa_hash.h CVS log

Up to [parser3project] / parser3 / src / include

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

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.29    ! paf         8:        $Id: pa_hash.h,v 1.28 2001/03/19 15:29:38 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: 
        !            26:        The only object that can be thread safe, wich is specified in constructor,
        !            27:        default 'not safe'.
        !            28: */
1.23      paf        29: class Hash : public Pooled {
1.1       paf        30: public:
                     31: 
1.29    ! paf        32:        typedef String Key; ///< hash Key type. longing for templates
        !            33:        typedef void Value; ///< hash Value type. longing for templates
1.3       paf        34: 
1.29    ! paf        35:        /// foreach iterator function type
1.26      paf        36:        typedef void (*Foreach_func)(const Key& key, Value *value, void *info);
1.25      paf        37: 
1.8       paf        38: public:
                     39: 
1.24      paf        40:        Hash(Pool& apool,bool athread_safe=false) : Pooled(apool) { 
                     41:                construct(apool, athread_safe); 
                     42:        }
1.10      paf        43: 
1.29    ! paf        44:        /// useful generic hash function
1.19      paf        45:        static uint generic_code(uint aresult, const char *start, uint allocated);
1.8       paf        46: 
1.29    ! paf        47:        /// put a [value] under the [key], return existed or not
1.18      paf        48:        /*SYNCHRONIZED*/ bool put(const Key& key, Value *value);
1.8       paf        49: 
1.29    ! paf        50:        /// get associated [value] by the [key]
1.15      paf        51:        /*SYNCHRONIZED*/ Value *get(const Key& key) const;
1.17      paf        52: 
1.29    ! paf        53:        /// put a [value] under the [key] if that [key] existed, return existed or not
1.18      paf        54:        /*SYNCHRONIZED*/ bool put_replace(const Key& key, Value *value);
                     55: 
1.29    ! paf        56:        /// put a [value] under the [key] if that [key] NOT existed, return existed or not
1.18      paf        57:        /*SYNCHRONIZED*/ bool put_dont_replace(const Key& key, Value *value);
                     58: 
1.29    ! paf        59:        /// put all 'src' values if NO with same key existed
1.18      paf        60:        /*SYNCHRONIZED*/ void merge_dont_replace(const Hash& src);
1.11      paf        61: 
1.13      paf        62:        void put(const Key& key, int     value) { put(key, reinterpret_cast<Value *>(value)); }
                     63:        void put(const Key& key, String *value) { put(key, static_cast<Value *>(value)); }
1.11      paf        64: 
1.29    ! paf        65:        //@{
        !            66:        /// handy get, longing for Hash<int>, Hash<String *>
1.13      paf        67:        int get_int(const Key& key) { return reinterpret_cast<int>(get(key)); }
1.20      paf        68:        const String *get_string(const Key& key) { return static_cast<String *>(get(key)); }
1.29    ! paf        69:        //@}
1.10      paf        70: 
1.29    ! paf        71:        /// number of elements in hash
1.19      paf        72:        int size() { return used; }
1.25      paf        73: 
1.29    ! paf        74:        /// iterate over all not zero elements
1.26      paf        75:        void foreach(Foreach_func func, void *info=0);
1.27      paf        76: 
1.29    ! paf        77:        /// remove all elements
1.27      paf        78:        void clear();
1.19      paf        79: 
1.15      paf        80: protected:
                     81: 
                     82:        void construct(Pool& apool, bool athread_safe);
                     83: 
1.1       paf        84: private:
                     85: 
1.19      paf        86:        // expand when these %% of allocated exausted
1.1       paf        87:        enum {
                     88:                THRESHOLD_PERCENT=75
                     89:        };
                     90: 
1.9       paf        91:        // am I thread-safe?
                     92:        bool thread_safe;
                     93: 
1.19      paf        94:        // the index of [allocated] in [allocates]
                     95:        int allocates_index;
1.1       paf        96: 
1.19      paf        97:        // possible [allocates]. prime numbers
                     98:        static uint allocates[];
                     99:        static int allocates_count;
1.1       paf       100: 
                    101:        // number of allocated pairs
1.19      paf       102:        int allocated;
1.1       paf       103: 
                    104:        // helper: expanding when used == threshold
                    105:        int threshold;
                    106: 
                    107:        // used pairs
                    108:        int used;
                    109: 
                    110:        // main storage
                    111:        class Pair {
1.2       paf       112:                friend Hash;
                    113: 
1.1       paf       114:                uint code;
1.15      paf       115:                const Key key;
1.1       paf       116:                Value *value;
                    117:                Pair *link;
1.2       paf       118:                
1.19      paf       119:                void *operator new(size_t allocated, Pool& apool);
1.2       paf       120: 
1.13      paf       121:                Pair(uint acode, const Key& akey, Value *avalue, Pair *alink) :
1.1       paf       122:                        code(acode),
                    123:                        key(akey),
                    124:                        value(avalue),
1.2       paf       125:                        link(alink) {}
                    126:        } **refs;
1.1       paf       127: 
1.5       paf       128:        // filled to threshold: needs expanding
                    129:        bool full() { return used==threshold; }
                    130: 
                    131:        // allocate larger buffer & rehash
1.1       paf       132:        void expand();
1.4       paf       133: 
                    134: private: //disabled
                    135: 
1.11      paf       136:        //Hash(Hash&) {}
1.12      paf       137:        Hash& operator = (const Hash&) { return *this; }
1.1       paf       138: };
                    139: 
                    140: #endif