Unicode-capable symbol table (N-way search tree with hash buckets)

Question

As in my previous question, this module is coupled with its own testing framework.

As a symbol-table for a Unicode-capable programming language interpreter, I decided to combine the 3 types of associative array that I had implemented before. Xpost's postscript nametype objects are implemented with a ternary search tree (.c .h), and its dicttype objects are implemented with a hash table (.c .h). Inca3's symbol table used a trie tree to hold variable-length keys (.c).

As a trie, it collapses similar prefixes from the keys. For "abc", "aaa", "abb", and "add", we get the structure:

a - a - a
  - b - b
      - c
  - d - d

Every key has the same prefix "a" so it is represented exactly once.

The Inca3 trie allows only alphabetic characters in symbols, so each node could contain an array of 52 pointers. But to adapt this code for Unicode code points, millions of pointers in each node seems grossly impractical. So the child nodes from each node are organized into a hash table keyed to the single character where they diverge from the tree.

In the example above, ('a', 'b', 'd') and ('b', 'c') are collected in hash tables. There are also degenerate hash tables at each of the leaf nodes which are all null.

So, each node contains a value or null. Each node also contains a pointer to a table of child nodes which is accessed via a hash lookup on a single char (code-point) of the key string. If the key string is not exhausted, lookup continues on the child nodes of the matched node.

I suppose I don't have any specific questions or areas of concern beyond: is it readable? does it look professional?

minunit.h:

/* file: minunit.h
   cf.http://www.jera.com/techinfo/jtns/jtn002.html */
 #define mu_assert(message, test) do { if (!(test)) return message; } while (0)
 #define mu_run_test(test) do { char *message = test(); tests_run++; \
                                 if (message) return message; } while (0)

#define test_case(c) do { if(c)return #c; } while(0)

 extern int tests_run;

st.c:

#include <stdint.h>
#include <stdlib.h>

typedef struct st {
    int key;
    int val;
    int n;
    struct st **tab /*[n]*/ ;
} *ST;

ST findsymb(ST st, int **spp, int *n, int mode);

ST makesymbtab(int n){
    ST z = malloc(sizeof *z);
    if (z){
        z->key = 0;
        z->val = 0;
        z->n = n;
        z->tab = calloc(n, sizeof *z->tab);
    }
    return z;
}

int hash(int x){
    return x^(x<<5)^(x<<14);
    return 0;
}

#define RETURN_TAB_I_IF_EQ_K_OR_NULL \
    if (st->tab[i] == NULL || st->tab[i]->key == k) \
        return &st->tab[i];

ST *hashlookup(ST st, int k){
    int i;
    int h;
    unsigned int sz = st->n;

    h = hash(k) % sz;
    i = h;
    RETURN_TAB_I_IF_EQ_K_OR_NULL
    for (++i; i < sz; i++)
        RETURN_TAB_I_IF_EQ_K_OR_NULL
    for (i=0; i < h; i++)
        RETURN_TAB_I_IF_EQ_K_OR_NULL
    return NULL;
}

void rehash(ST st){
    int n = st->n * 7 + 11;
    int i;
    ST z=makesymbtab(n);
    ST *t = NULL;
    for (i=0; i<st->n; i++){
        if (st->tab[i]){
            t = hashlookup(z, st->tab[i]->key);
            *t = st->tab[i];
        }
    }

    t = st->tab;
    st->tab = z->tab;
    st->n = n;
    free(t);
    free(z);
}

ST findsymb(ST st, int **spp, int *n, int mode){
    ST last = st;
#define sp (*spp)
    int *lasp = sp;
    ST *t = NULL;
    int nn = *n;
    int lasn = nn;

    while(nn--){
        t = hashlookup(st, *sp);
        if (!t) { // received NULL: table full
            rehash(st);
            t = hashlookup(st, *sp);
        }
        // t is now a pointer to a slot
        if (*t) { // slot not empty
            st = *t;
            sp++;
            if ((*t)->key==*sp){ // match
                last = st;
                lasp = sp;
                lasn = nn;
            }
        }
        else switch(mode){ // slot empty
        case 0: // prefix search : return last match
            sp = lasp;
            *n = lasn;
            return last;
        case 1: // defining search
            *t = calloc(1, sizeof(struct st));
            (*t)->tab = calloc((*t)->n = 11, sizeof(struct st));
            st = *t;
            st->key=*sp++;
            break;
        }
    }

    *n = nn+1;
    return last;
}
#undef sp

#ifdef TESTMODULE
#include "minunit.h"
int tests_run = 0;

#include <stdio.h>

struct st st = { .key = 0, .val = 0, .n = 10, .tab=(struct st *[10]){0} };

static char *test_put_get(){
    int array[] = {48,49,50};
    int *symb;
    int n;
    ST t;

    symb = array;
    n = 3;
    t = findsymb(&st,&symb,&n,1);
    //printf("%p\n",(void*)t);
    t->val = 42;

    symb = array;
    n = 3;
    t = findsymb(&st,&symb,&n,0);
    //printf("%p\n",(void*)t);
    test_case(t->val != 42);
    test_case(n != 0);

    return 0;
}

static char *test_null_all_bits_zero(){
    char **calloc_ed_pointer = calloc(1,sizeof*calloc_ed_pointer);
    test_case(*calloc_ed_pointer!=NULL);
    free(calloc_ed_pointer);
    return 0;
}

static char *all_tests(){
    mu_run_test(test_null_all_bits_zero);
    mu_run_test(test_put_get);
    return 0;
}

int main() {

    char *result=all_tests();
    if (result != 0) {
        printf("%s\n",result);
    } else {
        printf("ALL TESTS PASSED\n");
    }
    printf("Tests run: %d\n", tests_run);
    return result != 0;

}
#endif //defined TESTMODULE

Related module: UTF-8 encoding/decoding

More about the test suite: https://stackoverflow.com/questions/32163935/compose-a-combined-test-suite-program-from-a-collection-of-unit-tests

Answer 1

Is it readable? Does it look professional?

Honest, personally I think it could be a lot better. What bothers me the most about your code is that you're too fond of single letter names. There are way too many xs, zs, ns and such flying around. Single letter names are admissible as loop counters, but not for much else. Take some time to think of a name that conveys the purpose of the variable. Another good rule of thumb is to give a name according to the scope, so the wider the scope/visibility of the variable, the more descriptive and unique the name should be.

Insisting on it, I see to reason to pick ambiguous abbreviations to save on keystrokes. Why ST? If I dive into the code without reading the documentation first, I'll have no idea what's that structure. I might get an idea judging by the fields that it is some sort of table, probably a hash table, but then I'd expect it to be named HT if it was a hash-tab... Moral of the story, don't impose this unnecessary intelectual burden on the reader. Just spell it out: SymbolTable. Remember the Zen of Python: Explicit is better than implicit.

This last point is subjective, but I find tightlypacked names harder to digest. I see that you already use snake_case, so I'd be consistent with that for the symbol table functions as well.

Better hashing:

Your hash function seems very rudimentary. Have you tested it for collisions? I suggest taking a look at other more sophisticated alternatives. You can start from here. The One-at-a-time hash function has been working well for me for a while now.

Other details:

• Stray return statement here:

  int hash(int x){
      return x^(x<<5)^(x<<14);
      return 0; // <----------- 
  }
  

  Probably an artefact from an earlier version of the code.

• Your spacing is not consistent. You have several instances where there's no space between the arithmetical operators. I recommend using spaces always. We use spaces to separate words because it makes reading easier, this also applies to code. I suggest looking at Clang-Format. It is an amazing tool that automates code formatting for you. Once you start using it you'll never want to code without it again.

• I really dislike this macro: RETURN_TAB_I_IF_EQ_K_OR_NULL. Seems like gratuitous code obfuscation to me. And the fact that it doesn't take a semicolon at the end, makes it even shadier. Can't tell without looking at the definition of the macro if the code is broken or that's they way it was meant to be.

• This #define sp (*spp) is another instance of macro abuse and obfuscation. But the bigger issue is naming. sp or spp tells the reader (including yourself six months from now) absolutely nothing.

• else switch(mode){ okay, now that's just being clever. We're not trying to invent new language keyword here. Just put the switch on the next line please, properly nested under the else. Adding { } to the else would make it even better.

• In rehash, what's 7, 11?

  int n = st->n * 7 + 11;
  

  A comment would help. Going further, they could be named constants, but for now a comment suffices, since they don't repeat outside.

Answer 2

Logic errors.

    // t is now a pointer to a slot
    if (*t) { // slot not empty
        st = *t;
        sp++;
        if ((*t)->key==*sp){ // match
            last = st;
            lasp = sp;
            lasn = nn;
        }
    }

The "empty" case below is correct, I believe, but this part doesn't make sense. What if it doesn't match? Why would it match if we just did sp++? Rather it should insist on a match or break from the loop and return the last saved partial result. And it should update the 'last saved result' variables if the value field is not-null. Need some rethinking here.