feat: added set data structure to libn macro

1 files changed, 180 insertions, 0 deletions

diff --git a/include/libn/macro/map.h b/include/libn/macro/map.h
index bbd4a91..4724d1e 100644
--- a/include/libn/macro/map.h
+++ b/include/libn/macro/map.h
@@ -224,3 +224,183 @@ static const double __ac_HASH_UPPER = 0.77;
       --map->size;                                                             \
     }                                                                          \
   }
+
+/* set macro */
+
+#define SET_STRUCT_BODY(key_t)                                                 \
+  int32 n_buckets, size, n_occupied, upper_bound;                              \
+  int32 *flags;                                                                \
+  key_t *keys;                                                                 \
+
+#define SET_MAKE(type, h, alloc)                                               \
+  type *set;                                                                   \
+  set = alloc((h), 1, sizeof(*set));                                           \
+  return set
+
+#define SET_FREE(set, free, h)                                                 \
+  free(h, set->keys);                                                          \
+  free(h, set->flags);                                                         \
+  free(h, set);
+
+#define SET_RESET(set)                                                         \
+  if (set && set->flags) {                                                     \
+    memset(set->flags, 0xaa, __ac_fsize(set->n_buckets) * sizeof(int32));      \
+    set->size = set->n_occupied = 0;                                           \
+  }
+
+#define SET_GET(i, set, key, hashfunc, equalfunc )                             \
+  int32 k, last, mask, step;                                                   \
+  if (set->n_buckets) {                                                        \
+    k    = 0;                                                                  \
+    i    = 0;                                                                  \
+    last = 0;                                                                  \
+    mask = 0;                                                                  \
+    step = 0;                                                                  \
+    mask = set->n_buckets - 1;                                                 \
+    k    = hashfunc(key);                                                      \
+    i    = k & mask;                                                           \
+    last = i;                                                                  \
+    while (!__ac_isempty(set->flags, i) &&                                     \
+           (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) {     \
+      i = (i + (++step)) & mask;                                               \
+      if (i == last) {                                                         \
+        i = set->n_buckets;                                                    \
+        break;                                                                 \
+      }                                                                        \
+    }                                                                          \
+    if (i < set->n_buckets && __ac_iseither(set->flags, i))                    \
+        i = set->n_buckets;                                                    \
+  } else                                                                       \
+    i = 0;
+
+#define SET_GROW(set, key_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 (set->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 (set->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;                                                           \
+        }                                                                      \
+        memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets);           \
+        free(h, set->keys);                                                    \
+        set->keys = new_keys;                                                  \
+      }                                                                        \
+    }                                                                          \
+  }                                                                            \
+  if (j) { /* rehashing is needed */                                           \
+    for (j = 0; j != set->n_buckets; ++j) {                                    \
+      if (__ac_iseither(set->flags, j) == 0) {                                 \
+        key_t key = set->keys[j];                                              \
+        int32 new_mask;                                                        \
+        new_mask = new_n_buckets - 1;                                          \
+        __ac_set_isdel_true(set->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 < set->n_buckets && __ac_iseither(set->flags, i) == 0) {       \
+            {                                                                  \
+              key_t tmp = set->keys[i];                                        \
+              set->keys[i] = key;                                              \
+              key = tmp;                                                       \
+            }                                                                  \
+            __ac_set_isdel_true(set->flags, i);                                \
+          } else {                                                             \
+            set->keys[i] = key;                                                \
+            break;                                                             \
+          }                                                                    \
+        }                                                                      \
+      }                                                                        \
+    }                                                                          \
+    if (set->n_buckets > new_n_buckets) { /* shrink the hash table */          \
+      key_t *new_keys = alloc(h, new_n_buckets, sizeof(key_t));                \
+      memcpy(new_keys, set->keys, sizeof(key_t) * set->n_buckets);             \
+      free(h, set->keys);                                                      \
+      set->keys = new_keys;                                                    \
+    }                                                                          \
+    free(h, set->flags); /* free the working space */                          \
+    set->flags      = new_flags;                                               \
+    set->n_buckets  = new_n_buckets;                                           \
+    set->n_occupied = set->size;                                               \
+    set->upper_bound = (int32)(set->n_buckets * __ac_HASH_UPPER + 0.5);        \
+  }                                                                            \
+  return 0;
+
+#define SET_PUT(set, key, hashfunc, equalfunc, resizefunc, err)                \
+  {                                                                            \
+    int32 x = 0;                                                               \
+    if (set->n_occupied >= set->upper_bound) {                                 \
+      if (set->n_buckets > (set->size << 1)) {                                 \
+        if (resizefunc(set, set->n_buckets - 1) < 0) {                         \
+          *err = -1;                                                           \
+          return set->n_buckets;                                               \
+        }                                                                      \
+      } else if (resizefunc(set, set->n_buckets + 1) < 0) {                    \
+        *err = -1;                                                             \
+        return set->n_buckets;                                                 \
+      }                                                                        \
+    }                                                                          \
+                                                                               \
+    {                                                                          \
+      int32 k, i, site, last, mask = set->n_buckets - 1, step = 0;             \
+      x = site = set->n_buckets;                                               \
+      k = hashfunc(key);                                                       \
+      i = k & mask;                                                            \
+      if (__ac_isempty(set->flags, i))                                         \
+        x = i; /* for speed up */                                              \
+      else {                                                                   \
+        last = i;                                                              \
+        while (!__ac_isempty(set->flags, i) &&                                 \
+               (__ac_isdel(set->flags, i) || !equalfunc(set->keys[i], key))) { \
+          if (__ac_isdel(set->flags, i))                                       \
+            site = i;                                                          \
+          i = (i + (++step)) & mask;                                           \
+          if (i == last) {                                                     \
+            x = site;                                                          \
+            break;                                                             \
+          }                                                                    \
+        }                                                                      \
+        if (x == set->n_buckets) {                                             \
+          if (__ac_isempty(set->flags, i) && site != set->n_buckets)           \
+            x = site;                                                          \
+          else                                                                 \
+            x = i;                                                             \
+        }                                                                      \
+      }                                                                        \
+    }                                                                          \
+    if (__ac_isempty(set->flags, x)) { /* not present at all */                \
+      set->keys[x] = key;                                                      \
+      __ac_set_isboth_false(set->flags, x);                                    \
+      ++set->size;                                                             \
+      ++set->n_occupied;                                                       \
+      *err = 1;                                                                \
+    } else if (__ac_isdel(set->flags, x)) { /* deleted */                      \
+      set->keys[x] = key;                                                      \
+      __ac_set_isboth_false(set->flags, x);                                    \
+      ++set->size;                                                             \
+    } else                                                                     \
+      *err = 0;                                                                \
+    return x;                                                                  \
+  }
+
+#define SET_DEL(set, x)                                                        \
+  {                                                                            \
+    if (x != set->n_buckets && !__ac_iseither(set->flags, x)) {                \
+      __ac_set_isdel_true(set->flags, x);                                      \
+      --set->size;                                                             \
+    }                                                                          \
+  }