path: root/include/base/macro/map.h

#pragma once

/*
 * Based on khash.h
 * Modified to make control more granular and similar to QSORT
 */

static const double HASHFILL = 0.77;

#define ROUNDUP32(x)                                                            \
  (--(x), (x) |= (x) >> 1, (x) |= (x) >> 2, (x) |= (x) >> 4, (x) |= (x) >> 8,   \
   (x) |= (x) >> 16, ++(x))

#define map·isempty(flag, i)  ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2)
#define map·isdelete(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1)
#define map·iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3)
#define map·setnodelete(flag, i)                                                \
  (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1)))
#define map·setnoteither(flag, i)                                               \
  (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1)))
#define map·setnotboth(flag, i)                                                 \
  (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1)))
#define map·setdelete(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1))

#define map·flagsize(m) ((m) < 16 ? 1 : (m) >> 4)
#define map·fill(m, x) (!map·iseither((m)->flag, (x)))

/* map types */
#define MAP_STRUCT_BODY(key_t, val_t)                                          \
  int32 cap, len, occ, fill;                                                   \
  int32  *flag;                                                                \
  key_t *key;                                                                  \
  val_t *val

#define MAP_MAKE(type, h, alloc)                                               \
  type *map = alloc((h), 1, sizeof(*map));                                     \
  return map

#define MAP_FREE(map, mem, heap)                                               \
  (mem).free((heap), (map)->key);                                              \
  (mem).free((heap), (map)->flag);                                             \
  (mem).free((heap), (map)->val);                                              \
  (mem).free((heap), (map));

#define MAP_RESET(map)                                                         \
  if((map) && (map)->flag){                                                    \
    memset((map)->flag, 0xAA, map·flagsize((map)->cap)*sizeof(int32));         \
    (map)->len = (map)->occ = 0;                                               \
  }

#define MAP_GET(i, map, key, hashfunc, equalfunc)                              \
  int32 k, last, mask, step;                                                   \
  if((map)->cap){                                                              \
    k    = 0;                                                                  \
    i    = 0;                                                                  \
    last = 0;                                                                  \
    mask = 0;                                                                  \
    step = 0;                                                                  \
    mask = (map)->cap - 1;                                                     \
    k    = hashfunc((key));                                                    \
    i    = k & mask;                                                           \
    last = i;                                                                  \
    while(!map·isempty((map)->flag, i) &&                                      \
          (map·isdelete((map)->flag, i) || !equalfunc((map)->key[i], (key)))){ \
      i = (i + (++step)) & mask;                                               \
      if(i == last){                                                           \
        i = (map)->cap;                                                        \
        break;                                                                 \
      }                                                                        \
    }                                                                          \
    if(i < (map)->cap && map·iseither((map)->flag, i))                         \
        i = (map)->cap;                                                        \
  }else                                                                        \
    i = 0;

#define MAP_GROW(map, key_t, val_t, newcap, hashfunc, mem, heap)               \
  int32 *new_flags = nil;                                                      \
  int32 j = 1;                                                                 \
  {                                                                            \
    ROUNDUP32(newcap);                                                         \
    if(newcap < 4)                                                             \
      newcap = 4;                                                              \
    if((map)->len >= (int32)(newcap * HASHFILL + 0.5))                         \
      j = 0;                                                                   \
    else{                                                                      \
      new_flags = (mem).alloc((heap), map·flagsize(newcap), sizeof(int32));    \
      if(!new_flags) return -1;                                                \
      memset(new_flags, 0xaa, map·flagsize(newcap) * sizeof(int32));           \
      if((map)->cap < newcap){ /* expand */                                    \
        key_t *new_keys = (mem).alloc((heap), newcap, sizeof(key_t));          \
        if(!new_keys){                                                         \
          (mem).free((heap), new_flags);                                       \
          return -1;                                                           \
        }                                                                      \
        memcpy(new_keys, (map)->key, sizeof(key_t) * (map)->cap);              \
        (mem).free((heap), (map)->key);                                        \
        (map)->key = new_keys;                                                 \
        val_t *new_vals = (mem).alloc((heap), newcap, sizeof(val_t));          \
        if(!new_vals){                                                         \
          (mem).free((heap), new_flags);                                       \
          return -1;                                                           \
        }                                                                      \
        memcpy(new_vals, (map)->val, sizeof(val_t) * (map)->cap);              \
        (mem).free((heap), (map)->val);                                        \
        (map)->val = new_vals;                                                 \
      }                                                                        \
    }                                                                          \
  }                                                                            \
  if(j){ /* rehashing is needed */                                             \
    for(j = 0; j != (map)->cap; ++j){                                          \
      if(map·iseither((map)->flag, j) == 0){                                   \
        key_t key = (map)->key[j];                                             \
        val_t val;                                                             \
        int32 new_mask;                                                        \
        new_mask = newcap - 1;                                                 \
        val = (map)->val[j];                                                   \
        map·setdelete((map)->flag, j);                                         \
        while(1){                                                              \
          int32 k, i, step = 0;                                                \
          k = hashfunc(key);                                                   \
          i = k & new_mask;                                                    \
          while (!map·isempty(new_flags, i))                                   \
            i = (i + (++step)) & new_mask;                                     \
          map·setnoteither(new_flags, i);                                      \
          if(i < (map)->cap && map·iseither((map)->flag, i) == 0) {            \
            {                                                                  \
              key_t tmp = (map)->key[i];                                       \
              (map)->key[i] = key;                                             \
              key = tmp;                                                       \
            }                                                                  \
            {                                                                  \
              val_t tmp = (map)->val[i];                                       \
              (map)->val[i] = val;                                             \
              val = tmp;                                                       \
            }                                                                  \
            map·setdelete((map)->flag, i);                                     \
          }else{                                                               \
            (map)->key[i] = key;                                               \
            (map)->val[i] = val;                                               \
            break;                                                             \
          }                                                                    \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if((map)->cap > newcap){ /* shrink the hash table */                       \
      key_t *new_keys = (mem).alloc((heap), newcap, sizeof(key_t));            \
      memcpy(new_keys, (map)->key, sizeof(key_t) * (map)->cap);                \
      (mem).free((heap), (map)->key);                                          \
      (map)->key = new_keys;                                                   \
                                                                               \
      val_t *new_vals = (mem).alloc((heap), newcap, sizeof(val_t));            \
      memcpy(new_vals, (map)->val, sizeof(val_t) * (map)->cap);                \
      (mem).free((heap), (map)->val);                                          \
      (map)->val = new_vals;                                                   \
    }                                                                          \
    (mem).free((heap), (map)->flag); /* free the working space */              \
    (map)->flag      = new_flags;                                              \
    (map)->cap  = newcap;                                                      \
    (map)->occ = (map)->len;                                                   \
    (map)->fill = (int32)((map)->cap * HASHFILL + 0.5);                        \
  }                                                                            \
  return 0;

#define MAP_PUT(map, key, hashfunc, equalfunc, resizefunc, err)                \
    int32 x = 0;                                                               \
    if(map->occ >= map->fill){                                                 \
      if(map->cap > (map->len << 1)){                                          \
        if(resizefunc(map, map->cap - 1) < 0){                                 \
          *err = -1;                                                           \
          return map->cap;                                                     \
        }                                                                      \
      }else if(resizefunc(map, map->cap + 1) < 0){                             \
        *err = -1;                                                             \
        return map->cap;                                                       \
      }                                                                        \
    }                                                                          \
                                                                               \
    {                                                                          \
      int32 k, i, site, last, mask = map->cap - 1, step = 0;                   \
      x = site = map->cap;                                                     \
      k = hashfunc((key));                                                     \
      i = k & mask;                                                            \
      if(map·isempty(map->flag, i))                                            \
        x = i; /* for speed up */                                              \
      else{                                                                    \
        last = i;                                                              \
        while(!map·isempty(map->flag, i) &&                                    \
              (map·isdelete(map->flag, i) || !equalfunc(map->key[i], (key)))){ \
          if(map·isdelete(map->flag, i))                                       \
            site = i;                                                          \
          i = (i + (++step)) & mask;                                           \
          if(i == last){                                                       \
            x = site;                                                          \
            break;                                                             \
          }                                                                    \
        }                                                                      \
        if(x == map->cap){                                                     \
          if(map·isempty(map->flag, i) && site != map->cap)                    \
            x = site;                                                          \
          else                                                                 \
            x = i;                                                             \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if(map·isempty(map->flag, x)){ /* not present at all */                    \
      map->key[x] = (key);                                                     \
      map·setnotboth(map->flag, x);                                            \
      ++map->len;                                                              \
      ++map->occ;                                                              \
      *err = 1;                                                                \
    }else if(map·isdelete(map->flag, x)){ /* deleted */                        \
      map->key[x] = (key);                                                     \
      map·setnotboth(map->flag, x);                                            \
      ++map->len;                                                              \
    }else                                                                      \
      *err = 0;                                                                \
    return x;

#define MAP_DEL(map, x)                                                        \
    if(x != map->cap && !map·iseither(map->flag, x)){                          \
      map·setdelete(map->flag, x);                                             \
      --map->len;                                                              \
    }

/* set macro */

#define SET_STRUCT_BODY(key_t)                                                 \
  int32 cap, len, occ, fill;                                                   \
  int32 *flag;                                                                 \
  key_t *key                                                                   \

#define SET_MAKE(type, h, alloc)                                               \
  type *set = alloc((h), 1, sizeof(*set));                                     \
  return set

#define SET_FREE(set, mem, heap)                                               \
  (mem).free((heap), (set)->key);                                              \
  (mem).free((heap), (set)->flag);                                             \
  (mem).free((heap), (set))

#define SET_RESET(set)                                                         \
  if ((set) && (set)->flag) {                                                  \
    memset((set)->flag, 0xAA, map·flagsize((set)->cap) * sizeof(int32));       \
    (set)->len = (set)->occ = 0;                                               \
  }

#define SET_GET(i, set, key, hashfunc, equalfunc )                             \
  int32 k, last, mask, step;                                                   \
  if((set)->cap){                                                              \
    k    = 0;                                                                  \
    i    = 0;                                                                  \
    last = 0;                                                                  \
    mask = 0;                                                                  \
    step = 0;                                                                  \
    mask = (set)->cap - 1;                                                     \
    k    = hashfunc((key));                                                    \
    i    = k & mask;                                                           \
    last = i;                                                                  \
    while(!map·isempty((set)->flag, i) &&                                      \
          (map·isdelete((set)->flag, i) || !equalfunc((set)->key[i], (key)))){ \
      i = (i + (++step)) & mask;                                               \
      if(i == last){                                                           \
        i = (set)->cap;                                                        \
        break;                                                                 \
      }                                                                        \
    }                                                                          \
    if(i < (set)->cap && map·iseither((set)->flag, i))                         \
        i = (set)->cap;                                                        \
  }else                                                                        \
    i = 0;

#define SET_GROW(set, key_t, newcap, hashfunc, mem, heap)                      \
  int32 *new_flags = nil;                                                      \
  int32 j = 1;                                                                 \
  {                                                                            \
    ROUNDUP32(newcap);                                                         \
    if(newcap < 4)                                                             \
      newcap = 4;                                                              \
    if((set)->len >= (int32)(newcap * HASHFILL + 0.5))                         \
      j = 0;                                                                   \
    else{                                                                      \
      new_flags = mem.alloc((heap), map·flagsize(newcap), sizeof(int32));      \
      if(!new_flags) return -1;                                                \
      memset(new_flags, 0xaa, map·flagsize(newcap) * sizeof(int32));           \
      if((set)->cap < newcap) { /* expand */                                   \
        key_t *new_keys = mem.alloc((heap), newcap, sizeof(key_t));            \
        if(!new_keys){                                                         \
          mem.free((heap), new_flags);                                         \
          return -1;                                                           \
        }                                                                      \
        memcpy(new_keys, (set)->key, sizeof(key_t) * (set)->cap);              \
        mem.free((heap), (set)->key);                                          \
        (set)->key = new_keys;                                                 \
      }                                                                        \
    }                                                                          \
  }                                                                            \
  if(j){ /* rehashing is needed */                                             \
    for(j = 0; j != (set)->cap; ++j) {                                         \
      if(map·iseither((set)->flag, j) == 0) {                                  \
        key_t key = (set)->key[j];                                             \
        int32 new_mask;                                                        \
        new_mask = newcap - 1;                                                 \
        map·setdelete((set)->flag, j);                                         \
        while(1){                                                              \
          int32 k, i, step = 0;                                                \
          k = hashfunc(key);                                                   \
          i = k & new_mask;                                                    \
          while(!map·isempty(new_flags, i))                                    \
            i = (i + (++step)) & new_mask;                                     \
          map·setnoteither(new_flags, i);                                      \
          if(i < (set)->cap && map·iseither((set)->flag, i) == 0) {            \
            {                                                                  \
              key_t tmp = (set)->key[i];                                       \
              (set)->key[i] = key;                                             \
              key = tmp;                                                       \
            }                                                                  \
            map·setdelete((set)->flag, i);                                     \
          }else{                                                               \
            (set)->key[i] = key;                                               \
            break;                                                             \
          }                                                                    \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if((set)->cap > newcap) { /* shrink the hash table */                      \
      key_t *new_keys = mem.alloc((heap), newcap, sizeof(key_t));              \
      memcpy(new_keys, (set)->key, sizeof(key_t) * (set)->cap);                \
      mem.free((heap), (set)->key);                                            \
      (set)->key = new_keys;                                                   \
    }                                                                          \
    mem.free((heap), (set)->flag); /* free the working space */                \
    (set)->flag      = new_flags;                                              \
    (set)->cap  = newcap;                                                      \
    (set)->occ = (set)->len;                                                   \
    (set)->fill = (int32)((set)->cap * HASHFILL + 0.5);                        \
  }                                                                            \
  return 0;

#define SET_PUT(set, key, hashfunc, equalfunc, resizefunc, err)                \
    int32 x = 0;                                                               \
    if((set)->occ >= (set)->fill){                                             \
      if((set)->cap > ((set)->len << 1)){                                      \
        if(resizefunc((set), (set)->cap - 1) < 0){                             \
          *err = -1;                                                           \
          return (set)->cap;                                                   \
        }                                                                      \
      }else if(resizefunc((set), (set)->cap + 1) < 0){                         \
        *err = -1;                                                             \
        return (set)->cap;                                                     \
      }                                                                        \
    }                                                                          \
                                                                               \
    {                                                                          \
      int32 k, i, site, last, mask = (set)->cap - 1, step = 0;                 \
      x = site = (set)->cap;                                                   \
      k = hashfunc((key));                                                     \
      i = k & mask;                                                            \
      if(map·isempty((set)->flag, i))                                          \
        x = i; /* for speed up */                                              \
      else{                                                                    \
        last = i;                                                              \
        while(!map·isempty((set)->flag, i) &&                                  \
           (map·isdelete((set)->flag, i) || !equalfunc((set)->key[i], (key)))){\
          if(map·isdelete((set)->flag, i))                                     \
            site = i;                                                          \
          i = (i + (++step)) & mask;                                           \
          if(i == last) {                                                      \
            x = site;                                                          \
            break;                                                             \
          }                                                                    \
        }                                                                      \
        if(x == (set)->cap){                                                   \
          if(map·isempty((set)->flag, i) && site != (set)->cap)                \
            x = site;                                                          \
          else                                                                 \
            x = i;                                                             \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if(map·isempty((set)->flag, x)) { /* not present at all */                 \
      (set)->key[x] = (key);                                                   \
      map·setnotboth((set)->flag, x);                                          \
      ++(set)->len;                                                            \
      ++(set)->occ;                                                            \
      *err = 1;                                                                \
    }else if(map·isdelete((set)->flag, x)){ /* deleted */                      \
      (set)->key[x] = (key);                                                   \
      map·setnotboth((set)->flag, x);                                          \
      ++(set)->len;                                                            \
    }else                                                                      \
      *err = 0;                                                                \
    return x

#define SET_DEL(set, x)                                                        \
    if(x != (set)->cap && !map·iseither((set)->flag, x)) {                     \
      map·setdelete((set)->flag, x);                                           \
      --(set)->len;                                                            \
    }