include/libn/macro/map.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

#pragma once

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

static const double __ac_HASH_UPPER = 0.77;

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

#define __ac_isempty(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 2)
#define __ac_isdel(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 1)
#define __ac_iseither(flag, i) ((flag[i >> 4] >> ((i & 0xfU) << 1)) & 3)
#define __ac_set_isdel_false(flag, i)                                          \
  (flag[i >> 4] &= ~(1ul << ((i & 0xfU) << 1)))
#define __ac_set_isempty_false(flag, i)                                        \
  (flag[i >> 4] &= ~(2ul << ((i & 0xfU) << 1)))
#define __ac_set_isboth_false(flag, i)                                         \
  (flag[i >> 4] &= ~(3ul << ((i & 0xfU) << 1)))
#define __ac_set_isdel_true(flag, i) (flag[i >> 4] |= 1ul << ((i & 0xfU) << 1))

#define __ac_fsize(m) ((m) < 16 ? 1 : (m) >> 4)

#define MAP_STRUCT_BODY(key_t, val_t)                                          \
  int32 n_buckets, size, n_occupied, upper_bound;                              \
  int32 *flags;                                                                \
  key_t *keys;                                                                 \
  val_t *vals;

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

#define MAP_FREE(map, free, h)                                                 \
  free(h, map->keys);                                                          \
  free(h, map->flags);                                                         \
  free(h, map->vals);                                                          \
  free(h, map);

#define MAP_RESET(map)                                                         \
  if (map && map->flags) {                                                     \
    memset(map->flags, 0xaa, __ac_fsize(map->n_buckets) * sizeof(int32));      \
    map->size = map->n_occupied = 0;                                           \
  }

#define MAP_GET(i, map, key, hashfunc, equalfunc )                             \
  int32 k, last, mask, step;                                                   \
  if (map->n_buckets) {                                                        \
    k    = 0;                                                                  \
    i    = 0;                                                                  \
    last = 0;                                                                  \
    mask = 0;                                                                  \
    step = 0;                                                                  \
    mask = map->n_buckets - 1;                                                 \
    k    = hashfunc(key);                                                      \
    i    = k & mask;                                                           \
    last = i;                                                                  \
    while (!__ac_isempty(map->flags, i) &&                                     \
           (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) {     \
      i = (i + (++step)) & mask;                                               \
      if (i == last)                                                           \
        i = map->n_buckets;                                                    \
    }                                                                          \
    if (__ac_iseither(map->flags, i))                                          \
        i = map->n_buckets;                                                    \
  } else                                                                       \
    i = 0;

#define MAP_GROW(map, key_t, val_t, new_n_buckets, hashfunc, alloc, free, h)   \
  int32 *new_flags = nil;                                                      \
  int32 j = 1;                                                                 \
  {                                                                            \
    _roundup32(new_n_buckets);                                                 \
    if (new_n_buckets < 4)                                                     \
      new_n_buckets = 4;                                                       \
    if (map->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5))           \
      j = 0;                                                                   \
    else {                                                                     \
      new_flags =                                                              \
          alloc(h, __ac_fsize(new_n_buckets), sizeof(int32));                  \
      if (!new_flags) return -1;                                               \
      memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32));      \
      if (map->n_buckets < new_n_buckets) { /* expand */                       \
        key_t *new_keys =                                                      \
            alloc(h, new_n_buckets, sizeof(key_t));                            \
        if (!new_keys) {                                                       \
          free(h, new_flags);                                                  \
          return -1;                                                           \
        }                                                                      \
        free(h, map->keys);                                                    \
        map->keys = new_keys;                                                  \
        val_t *new_vals =                                                      \
            alloc(h, new_n_buckets, sizeof(val_t));                            \
        if (!new_vals) {                                                       \
          free(h, new_flags);                                                  \
          return -1;                                                           \
        }                                                                      \
        free(h, map->vals);                                                    \
        map->vals = new_vals;                                                  \
      }                                                                        \
    }                                                                          \
  }                                                                            \
  if (j) { /* rehashing is needed */                                           \
    for (j = 0; j != map->n_buckets; ++j) {                                    \
      if (__ac_iseither(map->flags, j) == 0) {                                 \
        key_t key = map->keys[j];                                              \
        val_t val;                                                             \
        int32 new_mask;                                                        \
        new_mask = new_n_buckets - 1;                                          \
        val = map->vals[j];                                                    \
        __ac_set_isdel_true(map->flags, j);                                    \
        while (1) {                                                            \
          int32 k, i, step = 0;                                                \
          k = hashfunc(key);                                                   \
          i = k & new_mask;                                                    \
          while (!__ac_isempty(new_flags, i))                                  \
            i = (i + (++step)) & new_mask;                                     \
          __ac_set_isempty_false(new_flags, i);                                \
          if (i < map->n_buckets && __ac_iseither(map->flags, i) == 0) {       \
            {                                                                  \
              key_t tmp = map->keys[i];                                        \
              map->keys[i] = key;                                              \
              key = tmp;                                                       \
            }                                                                  \
            {                                                                  \
              val_t tmp = map->vals[i];                                        \
              map->vals[i] = val;                                              \
              val = tmp;                                                       \
            }                                                                  \
            __ac_set_isdel_true(map->flags, i);                                \
          } else {                                                             \
            map->keys[i] = key;                                                \
            map->vals[i] = val;                                                \
            break;                                                             \
          }                                                                    \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if (map->n_buckets > new_n_buckets) { /* shrink the hash table */          \
      key_t *new_keys = alloc(h, new_n_buckets, sizeof(key_t));                \
      free(h, map->keys);                                                      \
      map->keys = new_keys;                                                    \
                                                                               \
      val_t *new_vals = alloc(h, new_n_buckets, sizeof(val_t));                \
      free(h, map->vals);                                                      \
      map->vals = new_vals;                                                    \
    }                                                                          \
    free(h, map->flags); /* free the working space */                          \
    map->flags = new_flags;                                                    \
    map->n_buckets = new_n_buckets;                                            \
    map->n_occupied = map->size;                                               \
    map->upper_bound = (int32)(map->n_buckets * __ac_HASH_UPPER + 0.5);        \
  }                                                                            \
  return 0;

#define MAP_PUT(map, key, val, hashfunc, equalfunc, resizefunc, err)           \
  {                                                                            \
    int32 x = 0;                                                               \
    if (map->n_occupied >= map->upper_bound) {                                 \
      if (map->n_buckets > (map->size << 1)) {                                 \
        if (resizefunc(map, map->n_buckets - 1) < 0) {                         \
          *err = -1;                                                           \
          return map->n_buckets;                                               \
        }                                                                      \
      } else if (resizefunc(map, map->n_buckets + 1) < 0) {                    \
        *err = -1;                                                             \
        return map->n_buckets;                                                 \
      }                                                                        \
    }                                                                          \
                                                                               \
    {                                                                          \
      int32 k, i, site, last, mask = map->n_buckets - 1, step = 0;             \
      x = site = map->n_buckets;                                               \
      k = hashfunc(key);                                                       \
      i = k & mask;                                                            \
      if (__ac_isempty(map->flags, i))                                         \
        x = i; /* for speed up */                                              \
      else {                                                                   \
        last = i;                                                              \
        while (!__ac_isempty(map->flags, i) &&                                 \
               (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \
          if (__ac_isdel(map->flags, i))                                       \
            site = i;                                                          \
          i = (i + (++step)) & mask;                                           \
          if (i == last) {                                                     \
            x = site;                                                          \
            break;                                                             \
          }                                                                    \
        }                                                                      \
        if (x == map->n_buckets) {                                             \
          if (__ac_isempty(map->flags, i) && site != map->n_buckets)           \
            x = site;                                                          \
          else                                                                 \
            x = i;                                                             \
        }                                                                      \
      }                                                                        \
    }                                                                          \
    if (__ac_isempty(map->flags, x)) { /* not present at all */                \
      map->keys[x] = key;                                                      \
      __ac_set_isboth_false(map->flags, x);                                    \
      ++map->size;                                                             \
      ++map->n_occupied;                                                       \
      *err = 1;                                                                \
    } else if (__ac_isdel(map->flags, x)) { /* deleted */                      \
      map->keys[x] = key;                                                      \
      __ac_set_isboth_false(map->flags, x);                                    \
      ++map->size;                                                             \
    } else                                                                     \
      *err = 0;                                                                \
    return x;                                                                  \
  }

#define MAP_DEL(map, x)                                                        \
  {                                                                            \
    if (x != map->n_buckets && !__ac_iseither(map->flags, x)) {                \
      __ac_set_isdel_true(map->flags, x);                                      \
      --map->size;                                                             \
    }                                                                          \
  }