"Fossies" - the Fresh Open Source Software Archive

Member "ftwin-master/src/lookup3.h" (15 Feb 2015, 3481 Bytes) of package /linux/privat/ftwin-master.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 #ifndef LOOKUP3_H
    2 #define LOOKUP3_H
    3 
    4 #include <stdlib.h>     /* for size_t */
    5 #include <stdint.h>     /* defines uint32_t etc */
    6 
    7 /*
    8 --------------------------------------------------------------------
    9  This works on all machines.  To be useful, it requires
   10  -- that the key be an array of uint32_t's, and
   11  -- that the length be the number of uint32_t's in the key
   12 
   13  The function hashword() is identical to hashlittle() on little-endian
   14  machines, and identical to hashbig() on big-endian machines,
   15  except that the length has to be measured in uint32_ts rather than in
   16  bytes.  hashlittle() is more complicated than hashword() only because
   17  hashlittle() has to dance around fitting the key bytes into registers.
   18 --------------------------------------------------------------------
   19 */
   20 uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval);
   21 
   22 /*
   23 --------------------------------------------------------------------
   24 hashword2() -- same as hashword(), but take two seeds and return two
   25 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
   26 both be initialized with seeds.  If you pass in (*pb)==0, the output 
   27 (*pc) will be the same as the return value from hashword().
   28 --------------------------------------------------------------------
   29 */
   30 void hashword2(const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb);
   31 
   32 /*
   33 -------------------------------------------------------------------------------
   34 hashlittle() -- hash a variable-length key into a 32-bit value
   35   k       : the key (the unaligned variable-length array of bytes)
   36   length  : the length of the key, counting by bytes
   37   initval : can be any 4-byte value
   38 Returns a 32-bit value.  Every bit of the key affects every bit of
   39 the return value.  Two keys differing by one or two bits will have
   40 totally different hash values.
   41 
   42 The best hash table sizes are powers of 2.  There is no need to do
   43 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
   44 use a bitmask.  For example, if you need only 10 bits, do
   45   h = (h & hashmask(10));
   46 In which case, the hash table should have hashsize(10) elements.
   47 
   48 If you are hashing n strings (uint8_t **)k, do it like this:
   49   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
   50 
   51 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
   52 code any way you wish, private, educational, or commercial.  It's free.
   53 
   54 Use for hash table lookup, or anything where one collision in 2^^32 is
   55 acceptable.  Do NOT use for cryptographic purposes.
   56 -------------------------------------------------------------------------------
   57 */
   58 uint32_t hashlittle(const void *key, size_t length, uint32_t initval);
   59 
   60 /*
   61  * hashlittle2: return 2 32-bit hash values
   62  *
   63  * This is identical to hashlittle(), except it returns two 32-bit hash
   64  * values instead of just one.  This is good enough for hash table
   65  * lookup with 2^^64 buckets, or if you want a second hash if you're not
   66  * happy with the first, or if you want a probably-unique 64-bit ID for
   67  * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
   68  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
   69  */
   70 void hashlittle2(const void *key, size_t length, uint32_t *pc, uint32_t *pb);
   71 
   72 /*
   73  * hashbig():
   74  * This is the same as hashword() on big-endian machines.  It is different
   75  * from hashlittle() on all machines.  hashbig() takes advantage of
   76  * big-endian byte ordering. 
   77  */
   78 uint32_t hashbig(const void *key, size_t length, uint32_t initval);
   79 
   80 #endif /* LOOKUP3_H */