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.6

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.6     ! moko       11: #define IDENT_PA_INLINE_HASH_H "$Id: pa_inline_hash.h,v 1.5 2026/04/30 01:40:39 moko Exp $"
1.1       moko       12: 
                     13: #include "pa_hash.h"
                     14: 
1.6     ! moko       15: #define PA_INLINE_HASH_N 13  // Low overflow rate, high first-hit ratio
        !            16: #define PA_PROBE_LIMIT 8     // Probe chains beyond this are very rare
1.1       moko       17: 
1.4       moko       18: // Linear-probing inline hash with PA_INLINE_HASH_N slots before overflow to HashString<V>.
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;
1.5       moko       36: 
                     37:                // Optimized first, >50% hits
                     38:                if(!fkeys[i]) return 0;  // NULL implies foverflow==NULL
                     39:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) return fvalues[i];
                     40:                // Сollision
1.6     ! moko       41:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       42:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       43:                        if(!fkeys[i]) return 0;
                     44:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) return fvalues[i];
1.1       moko       45:                }
                     46:                return foverflow ? foverflow->get(name) : 0;
                     47:        }
                     48: 
                     49:        bool put(const String& name, V value) {
                     50:                const String::Body& nb = name;
1.4       moko       51:                const uint hash = nb.get_hash_code();
                     52:                int i = hash % PA_INLINE_HASH_N;
1.5       moko       53: 
                     54:                // Optimized first
                     55:                if(!fkeys[i]) { fkeys[i] = &nb; fvalues[i] = value; return false; }
                     56:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
                     57:                // Сollision
1.6     ! moko       58:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       59:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       60:                        if(!fkeys[i]) { fkeys[i] = &nb; fvalues[i] = value; return false; }
                     61:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
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;
1.5       moko       72: 
                     73:                // Optimized first
                     74:                if(!fkeys[i]) return false;
                     75:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
                     76:                // Сollision
1.6     ! moko       77:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       78:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       79:                        if(!fkeys[i]) return false;
                     80:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
1.1       moko       81:                }
                     82:                return foverflow ? foverflow->put_replaced(name, value) : false;
                     83:        }
                     84: 
                     85:        template<typename I> void for_each(void callback(const String::Body&, V, I), I info) const {
1.4       moko       86:                for(int i = 0; i < PA_INLINE_HASH_N; i++) {
                     87:                        if(fkeys[i])
                     88:                                callback(*fkeys[i], fvalues[i], info);
                     89:                }
1.1       moko       90:                if(foverflow)
                     91:                        foverflow->for_each(callback, info);
                     92:        }
                     93: 
                     94: private:
                     95:        HashString<V>* foverflow;
1.4       moko       96:        const String::Body* fkeys[PA_INLINE_HASH_N];  // NULL=empty, initialized in constructor
                     97:        V fvalues[PA_INLINE_HASH_N];
                     98: 
1.1       moko       99: };
                    100: 
                    101: #endif // PA_INLINE_HASH_H