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

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.8     ! moko       11: #define IDENT_PA_INLINE_HASH_H "$Id: pa_inline_hash.h,v 1.7 2026/04/30 16:06:48 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
1.7       moko       16: #define PA_PROBE_LIMIT 8     // Prevents long probe chains from degrading the inline table
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.8     ! moko       23:        InlineHashString() : foverflow(0) {
        !            24:                memset(fkeys, 0, sizeof(fkeys));
1.4       moko       25:        }
1.1       moko       26: 
1.4       moko       27:        ~InlineHashString() {
1.2       moko       28: #ifdef USE_DESTRUCTORS
1.4       moko       29:                if(foverflow) delete foverflow;
1.2       moko       30: #endif
1.4       moko       31:        }
1.2       moko       32: 
1.1       moko       33:        V get(const String& name) const {
                     34:                const String::Body& nb = name;
1.4       moko       35:                const uint hash = nb.get_hash_code();
                     36:                int i = hash % PA_INLINE_HASH_N;
1.5       moko       37: 
                     38:                // Optimized first, >50% hits
                     39:                if(!fkeys[i]) return 0;  // NULL implies foverflow==NULL
                     40:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) return fvalues[i];
                     41:                // Сollision
1.6       moko       42:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       43:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       44:                        if(!fkeys[i]) return 0;
                     45:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) return fvalues[i];
1.1       moko       46:                }
                     47:                return foverflow ? foverflow->get(name) : 0;
                     48:        }
                     49: 
                     50:        bool put(const String& name, V value) {
                     51:                const String::Body& nb = name;
1.4       moko       52:                const uint hash = nb.get_hash_code();
                     53:                int i = hash % PA_INLINE_HASH_N;
1.5       moko       54: 
                     55:                // Optimized first
                     56:                if(!fkeys[i]) { fkeys[i] = &nb; fvalues[i] = value; return false; }
                     57:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
                     58:                // Сollision
1.6       moko       59:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       60:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       61:                        if(!fkeys[i]) { fkeys[i] = &nb; fvalues[i] = value; return false; }
                     62:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
1.1       moko       63:                }
                     64:                if(!foverflow)
                     65:                        foverflow = new HashString<V>();
                     66:                return foverflow->put(name, value);
                     67:        }
                     68: 
                     69:        bool put_replaced(const String& name, V value) {
                     70:                const String::Body& nb = name;
1.4       moko       71:                const uint hash = nb.get_hash_code();
                     72:                int i = hash % PA_INLINE_HASH_N;
1.5       moko       73: 
                     74:                // Optimized first
                     75:                if(!fkeys[i]) return false;
                     76:                if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
                     77:                // Сollision
1.6       moko       78:                for(int n = 0; n < PA_PROBE_LIMIT-1; n++) {
1.4       moko       79:                        if(++i >= PA_INLINE_HASH_N) i = 0;
1.5       moko       80:                        if(!fkeys[i]) return false;
                     81:                        if(fkeys[i]->get_hash_code() == hash && *fkeys[i] == nb) { fvalues[i] = value; return true; }
1.1       moko       82:                }
                     83:                return foverflow ? foverflow->put_replaced(name, value) : false;
                     84:        }
                     85: 
                     86:        template<typename I> void for_each(void callback(const String::Body&, V, I), I info) const {
1.4       moko       87:                for(int i = 0; i < PA_INLINE_HASH_N; i++) {
                     88:                        if(fkeys[i])
                     89:                                callback(*fkeys[i], fvalues[i], info);
                     90:                }
1.1       moko       91:                if(foverflow)
                     92:                        foverflow->for_each(callback, info);
                     93:        }
                     94: 
                     95: private:
                     96:        HashString<V>* foverflow;
1.4       moko       97:        const String::Body* fkeys[PA_INLINE_HASH_N];  // NULL=empty, initialized in constructor
                     98:        V fvalues[PA_INLINE_HASH_N];
                     99: 
1.1       moko      100: };
                    101: 
                    102: #endif // PA_INLINE_HASH_H