Return to pa_inline_hash.h CVS log

Up to [parser3project] / parser3 / src / include

Annotation of parser3/src/include/pa_inline_hash.h, revision 1.4

1.1       moko        1: /** @file
                      2:        Parser: inline-storage hash decls.
                      3: 
1.3       moko        4:        Copyright (c) 2001-2026 Art. Lebedev Studio (https://www.artlebedev.com)
1.1       moko        5:        Authors: Konstantin Morshnev <moko@design.ru>
                      6: */
                      7: 
                      8: #ifndef PA_INLINE_HASH_H
                      9: #define PA_INLINE_HASH_H
                     10: 
1.4     ! moko       11: #define IDENT_PA_INLINE_HASH_H "$Id: pa_inline_hash.h,v 1.7 2026/04/25 00:00:00 moko Exp $"
1.1       moko       12: 
                     13: #include "pa_hash.h"
                     14: 
1.4     ! moko       15: #define PA_INLINE_HASH_N 13
1.1       moko       16: 
1.4     ! moko       17: // Linear-probing inline hash with PA_INLINE_HASH_N slots before overflow to HashString<V>.
        !            18: // Inits 8*N bytes, while HASH allocates (and inits) at least 
1.1       moko       19: 
1.2       moko       20: template<typename V> class InlineHashString: public PA_Object {
1.1       moko       21: public:
                     22: 
1.4     ! moko       23:        InlineHashString() : fkeys{}, foverflow(0) {
        !            24:        }
1.1       moko       25: 
1.4     ! moko       26:        ~InlineHashString() {
1.2       moko       27: #ifdef USE_DESTRUCTORS
1.4     ! moko       28:                if(foverflow) delete foverflow;
1.2       moko       29: #endif
1.4     ! moko       30:        }
1.2       moko       31: 
1.1       moko       32:        V get(const String& name) const {
                     33:                const String::Body& nb = name;
1.4     ! moko       34:                const uint hash = nb.get_hash_code();
        !            35:                int i = hash % PA_INLINE_HASH_N;
        !            36:                for(int probe = 0; probe < PA_INLINE_HASH_N; probe++) {
        !            37:                        if(!fkeys[i]) {
        !            38:                                return foverflow ? foverflow->get(name) : 0;
        !            39:                        }
        !            40:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb)
        !            41:                                return fvalues[i];
        !            42:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.1       moko       43:                }
                     44:                return foverflow ? foverflow->get(name) : 0;
                     45:        }
                     46: 
                     47:        bool put(const String& name, V value) {
                     48:                const String::Body& nb = name;
1.4     ! moko       49:                const uint hash = nb.get_hash_code();
        !            50:                int i = hash % PA_INLINE_HASH_N;
        !            51:                for(int probe = 0; probe < PA_INLINE_HASH_N; probe++) {
        !            52:                        if(!fkeys[i]) {
        !            53:                                fkeys[i] = &nb;
        !            54:                                fvalues[i] = value;
        !            55:                                return false;
        !            56:                        }
        !            57:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) {
        !            58:                                fvalues[i] = value;
1.1       moko       59:                                return true;
                     60:                        }
1.4     ! moko       61:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.1       moko       62:                }
                     63:                if(!foverflow)
                     64:                        foverflow = new HashString<V>();
                     65:                return foverflow->put(name, value);
                     66:        }
                     67: 
                     68:        bool put_replaced(const String& name, V value) {
                     69:                const String::Body& nb = name;
1.4     ! moko       70:                const uint hash = nb.get_hash_code();
        !            71:                int i = hash % PA_INLINE_HASH_N;
        !            72:                for(int probe = 0; probe < PA_INLINE_HASH_N; probe++) {
        !            73:                        if(!fkeys[i])
        !            74:                                return foverflow ? foverflow->put_replaced(name, value) : false;
        !            75:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) {
        !            76:                                fvalues[i] = value;
1.1       moko       77:                                return true;
                     78:                        }
1.4     ! moko       79:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.1       moko       80:                }
                     81:                return foverflow ? foverflow->put_replaced(name, value) : false;
                     82:        }
                     83: 
                     84:        template<typename I> void for_each(void callback(const String::Body&, V, I), I info) const {
1.4     ! moko       85:                for(int i = 0; i < PA_INLINE_HASH_N; i++) {
        !            86:                        if(fkeys[i])
        !            87:                                callback(*fkeys[i], fvalues[i], info);
        !            88:                }
1.1       moko       89:                if(foverflow)
                     90:                        foverflow->for_each(callback, info);
                     91:        }
                     92: 
                     93: private:
                     94:        HashString<V>* foverflow;
1.4     ! moko       95:        const String::Body* fkeys[PA_INLINE_HASH_N];  // NULL=empty, initialized in constructor
        !            96:        V fvalues[PA_INLINE_HASH_N];
        !            97: 
1.1       moko       98: };
                     99: 
                    100: #endif // PA_INLINE_HASH_H