Boost logo

Boost Users :

Subject: [Boost-users] Generalised compile-time hash function
From: Nikhilesh S (s.nikhilesh_at_[hidden])
Date: 2009-03-11 04:28:45


Hey guys!

I'm not very familiar with boost.mpl, or boost.preprocessor, so I wanted
to ask.

I've written a compile-time hash function. Here's an example that uses
it:-

#include <iostream>

using namespace std;

//Compile-time hasher.
#define HASH(partial,c) (((partial) << 1) ^ (c))
#define HASH_1(p1) HASH(0,(p1))
#define HASH_2(p1,p2) HASH(HASH_1(p1),(p2))
#define HASH_3(p1,p2,p3) HASH(HASH_2(p1,p2),(p3))
#define HASH_4(p1,p2,p3,p4) HASH(HASH_3(p1,p2,p3),(p4))
#define HASH_5(p1,p2,p3,p4,p5) HASH(HASH_4(p1,p2,p3,p4),(p5))
#define HASH_6(p1,p2,p3,p4,p5,p6) HASH(HASH_5(p1,p2,p3,p4,p5),(p6))
#define HASH_7(p1,p2,p3,p4,p5,p6,p7) HASH(HASH_6(p1,p2,p3,p4,p5,p6),(p7))
#define HASH_8(p1,p2,p3,p4,p5,p6,p7,p8) HASH(HASH_7(p1,p2,p3,p4,p5,p6,p7),(p8))
#define HASH_9(p1,p2,p3,p4,p5,p6,p7,p8,p9) HASH(HASH_8(p1,p2,p3,p4,p5,p6,p7,p8),(p9))
#define HASH_10(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10) HASH(HASH_9(p1,p2,p3,p4,p5,p6,p7,p8,p9),(p10))
#define HASH_11(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11) HASH(HASH_10(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10),(p11))
#define HASH_12(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12) HASH(HASH_11(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11),(p12))
#define HASH_13(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13) HASH(HASH_12(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12),(p13))
#define HASH_14(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14) HASH(HASH_13(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13),(p14))
#define HASH_15(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15) HASH(HASH_14(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14),(p15))
#define HASH_16(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16) HASH(HASH_15(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15),(p16))

/* .. omitted the rest, but it's there till around HASH_30 .. */

//Runtime hasher.
unsigned int hash(char const *p)
{
     unsigned partial = 0;
     while (*p)
     {
         partial <<= 1;
         partial ^= *p;
         ++p;
     }
     return partial;
}

//Test it in a main()
int main()
{
     char str[31] = "thisisatest";

     //Yay! Switch on strings!
     switch (hash(str))
     {
         case HASH_11('t','h','i','s','i','s','a','t','e','s','t'):
             cout << "You said, 'this is a test'!";
             break;
         case HASH_16('y','e','t','a','n','o','t','h','e','r','s','t','r','i','n','g'):
             cout << "You said, 'yet another string'!";
             break;
     }

     return 0;
}

So, I was wondering how I could use boost.preprocessor to be able to
write a more generic hash function, something like
HASH_GENERIC(mystring), or at least HASH_GENERIC(8,mystring).

BTW, here's a vim script that changes any thing like '@something@' on
the curent line into "HASH_9('s','o','m','e','t','h','i','n','g')", when
you type ',h':-

map ,h :s/@\(.\+\)@/\='HASH_'.strlen(submatch(1))."('".join(split(submatch(1), '\zs'), "','")."')"/<CR>

;-)

--
Nikhilesh S
http://nikki.drupalsite.org

Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net