Recursion in C for hashcode

Question

I'm trying to make a hashcode function.

However, I get a random number not equal to the example, and I can't determine why (5 is the max length, so no need for dynamic memory allocation)

Answer 1

I can't help but feel recursion is a weird way to code it (in C — in LISP, it would be fine). In this code, hash1() is a simple iterative version of the hash function; hash2() follows the recursive specification, using hash3() as a helper function (it needs the length):

#include <string.h>
#include <stdio.h>

static unsigned long hash1(const char *str)
{
    unsigned long h = 0;
    while (*str != '\0')
        h = h * 65599 + *str++;
    return h;
}

static unsigned long hash3(const char *str, size_t len)
{
    unsigned long h = 0;
    if (len > 0)
        h = hash3(str, len - 1) * 65599 + str[len-1];
    return h;
}

static unsigned long hash2(const char *str)
{
    size_t len = strlen(str);
    return hash3(str, len);
}

static int test_hash(const char *str)
{
    unsigned long h1 = hash1(str);
    unsigned long h2 = hash2(str);
    int rc = 0;
    const char *pass_fail = "PASS";
    if (h1 != h2)
    {
        rc = 1;
        pass_fail = "FAIL";
    }
    printf("h1 = %lu, h2 = %lu: %s (%s)\n", h1, h2, pass_fail, str);
    return rc;
}

int main(void)
{
    static const char *data[] =
    {
        "ice", "man", "cometh", "the iceman cometh",
    };
    int failures = 0;
    for (size_t i = 0; i < sizeof(data)/sizeof(data[0]); i++)
        failures += test_hash(data[i]);
    printf("%s\n", (failures == 0) ? "== PASS ==" : "!! FAIL !!");
    return !(failures == 0);
}

Sample output (on a 64-bit platform, GCC 4.9.1 on Mac OS X 10.9.5):

h1 = 451845518507, h2 = 451845518507: PASS (ice)
h1 = 469058302522, h2 = 469058302522: PASS (man)
h1 = 8177059914254772472, h2 = 8177059914254772472: PASS (cometh)
h1 = 2988038870251942490, h2 = 2988038870251942490: PASS (the iceman cometh)
== PASS ==

Note that the code for ice matches the example. When compiled as a 32-bit program, the output is:

h1 = 873952427, h2 = 873952427: PASS (ice)
h1 = 906867258, h2 = 906867258: PASS (man)
h1 = 138275064, h2 = 138275064: PASS (cometh)
h1 = 1819095642, h2 = 1819095642: PASS (the iceman cometh)
== PASS ==

Answer 2

From the strncpy documentation:

No null-character is implicitly appended at the end of destination if source is longer than num. Thus, in this case, destination shall not be considered a null terminated C string (reading it as such would overflow).

so you want to do:

strncpy(new, str, l - 1);
new[l - 1] = 0;

But you can also avoid creating new strings using a helper function:

unsigned long hash_helper(const char* str, int len){
    if (len == 0) return 0;
    return hash_helper(str, len - 1) * 65599 + str[len - 1]; 
}

unsigned long hash(const char* str){
    return hash_helper(str, strlen(str));
}