Changeset 198


Ignore:
Timestamp:
03/25/14 18:49:56 (11 years ago)
Author:
Maciej Komosinski
Message:

Hashing function for strings

Location:
cpp/frams/util
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • cpp/frams/util/sstring.cpp

    r197 r198  
    107107txt=(char*)realloc(txt,needed+1);
    108108size=needed;
     109}
     110
     111//////////////////////////////////////////////////
     112// to be moved somewhere else?
     113// public domain source: http://isthe.com/chongo/src/fnv
     114typedef unsigned long Fnv32_t;
     115
     116#define FNV_32_PRIME ((Fnv32_t)0x01000193)
     117
     118Fnv32_t fnv_32_buf(void *buf, size_t len, Fnv32_t hval)
     119{
     120    unsigned char *bp = (unsigned char *)buf;   /* start of buffer */
     121    unsigned char *be = bp + len;               /* beyond end of buffer */
     122
     123    while (bp < be) {
     124
     125        /* multiply by the 32 bit FNV magic prime mod 2^32 */
     126#if defined(NO_FNV_GCC_OPTIMIZATION)
     127        hval *= FNV_32_PRIME;
     128#else
     129        hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
     130#endif
     131
     132        /* xor the bottom with the current octet */
     133        hval ^= (Fnv32_t)*bp++;
     134    }
     135
     136    /* return our new hash value */
     137    return hval;
     138}
     139//////////////////////////////////////////////////
     140
     141unsigned long SBuf::hash() const
     142{
     143return fnv_32_buf(txt,used,FNV_32_PRIME);
    109144}
    110145
  • cpp/frams/util/sstring.h

    r197 r198  
    4747SBuf();
    4848~SBuf();
     49unsigned long hash() const; // 32-bit FNV-1 hash -> http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash
    4950};
    5051
     
    174175int startsWith(const char *pattern) const;
    175176char charAt(int pos) const {return buf->txt[pos];}
     177unsigned long hash() const {return buf->hash();}
    176178
    177179static SString valueOf(int);
Note: See TracChangeset for help on using the changeset viewer.