symtab.c (part of calculator)

// avp 2016 (part of Symtab)

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

#ifdef __cplusplus
typedef double (*function)(...);
#else
typedef double (*function)();
#endif

typedef struct u_item *Symtab;
static Symtab *calc_fun = 0; // default functions hashtable

// hashtables item
struct u_item {
  struct u_item *next;
  union {
    function f;
    double v;
  };
  int len;
  char name[1];
};

#define INIT_HTAB_SIZE 5
#define HTAB_REHASH 2


static struct u_item **
make_htab (int sz)
{
  struct u_item **p = (typeof(p))calloc(sizeof(*p), sz + 2);

  if (p)
    p[0] = (typeof(*p))(long)sz;

  return p + 2;
}

static inline uint32_t
hash32 (const char *s, int len)
{
  uint32_t h = 0;

  /* Bernstein */
  while (len--)
    h = h * 33 + (uint8_t)(*s++);

  /* Murmur OAAT
  while (len--) {
    h ^= (uint8_t)(*s++);
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  */

  /* FNV
  h ^= 2166136261U;
  while (len--) {
    h ^= (uint8_t)(*s++);
    h *= 16777619;
  }
  */

  return h;
}

static void
rehash (struct u_item **htab[])
{
  struct u_item **t = *htab, **newtab;
  long hsize = (long)t[-2], n = (long)t[-1];

  if (n > 0) {
    if ((newtab = (typeof(newtab))calloc(sizeof(*newtab), n + 2))) {
      newtab[0] = newtab[1]= (typeof(*newtab))n;
      *htab = newtab + 2;
      //      t += 2;
      long i;
      for (i = 0; i < hsize; i++)
    while (t[i]) {
      struct u_item *p = t[i];
      t[i] = p->next;
      int j = hash32(p->name, p->len) % n;
      p->next = (*htab)[j];
      (*htab)[j] = p;
    }
      free(t - 2);
    }
  }
}

static int
check_htab (struct u_item **htab[])
{
  if (htab) {
    if (!*htab)
      if (!(*htab = make_htab(INIT_HTAB_SIZE)))
    return 0;
    if ((long)(*htab)[-1] / (long)(*htab)[-2] >= HTAB_REHASH)
      rehash(htab);

    return 1;
  }
  return 0;
}

static struct u_item *
get_htab (struct u_item **htab[], const char *s, int len)
{
  struct u_item *p = 0;

  if (len > 0 && check_htab(htab)) {
    long hsize = (long)(*htab)[-2];

    for (p = (*htab)[hash32(s, len) % hsize]; p; p = p->next)
      if (len == p->len && memcmp(p->name, s, len) == 0)
    break;
  }
  return p;
}

static struct u_item *
put_htab (struct u_item **htab[], const char *s, int len)
{
  struct u_item *p = 0;

  if (len > 0 && check_htab(htab)) {
    long hsize = (long)(*htab)[-2], j = hash32(s, len) % hsize;

    for (p = (*htab)[j]; p; p = p->next)
      if (p->len == len && memcmp(p->name, s, len) == 0)
    break;
    if (!p && (p = (typeof(p))calloc(1, sizeof(*p) + len))) {
      (*(long *)(*htab - 1))++;
      p->next = (*htab)[j];
      (*htab)[j] = p;
      memcpy(p->name, s, p->len = len);
    }
  }

  return p;
}

static int
del_htab (struct u_item **htab[], const char *s, int len)
{
  struct u_item *p = 0, **pp = 0;

  if (len > 0 && check_htab(htab)) {
    long hsize = (long)(*htab)[-2], j = hash32(s, len) % hsize;

    for (p = (*htab)[j], pp = *htab + j; p; pp = &p->next, p = p->next)
      if (len == p->len && memcmp(p->name, s, len) == 0) {
    *pp = p->next;
    (*(long *)(*htab - 1))++;
    free(p);
    return 1;
      }
  }

  return 0;
}