add vec

4 files changed, 156 insertions, 9 deletions

diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h
index 5c9b993..ccb40b9 100644
--- a/lib/cbit/htab.h
+++ b/lib/cbit/htab.h
@@ -12,8 +12,6 @@ struct htab_internal {
     char hi_storage[1]; // see vec.h
 };
 
-#define UNUSED_STATIC_INLINE __attribute__((unused)) static inline
-
 /* Declare the helper functions for a htab key type without static - put this
  * in the .h and IMPL_HTAB_KEY in a .c. */
 #define DECL_EXTERN_HTAB_KEY( \
@@ -188,7 +186,6 @@ struct htab_internal {
     }; \
     htab_ty { \
         union { \
-            char h[0]; \
             struct htab_internal hi; \
             struct { \
                 size_t length; \
@@ -273,11 +270,13 @@ struct htab_internal {
 } while (0)
 
 #define HTAB_FOREACH(ht, key_var, val_var, name) \
-    LET(struct htab_##name *__ht = (ht)) \
-        for (size_t __htfe_bucket = 0; __htfe_bucket < __ht->capacity; __htfe_bucket++) \
-            if(__htab_is_null_##name(&__ht->base[__htfe_bucket].key)) \
+    LET(struct htab_##name *__htfe_ht = (ht)) \
+        for (size_t __htfe_bucket = 0; \
+             __htfe_bucket < __htfe_ht->capacity; \
+             __htfe_bucket++) \
+            if(__htab_is_null_##name(&__htfe_ht->base[__htfe_bucket].key)) \
                 continue; \
             else \
-                LET_LOOP(key_var = &__ht->base[__htfe_bucket].key) \
-                LET_LOOP(val_var = &__ht->base[__htfe_bucket].value)
+                LET_LOOP(key_var = &__htfe_ht->base[__htfe_bucket].key) \
+                LET_LOOP(val_var = &__htfe_ht->base[__htfe_bucket].value)
 
diff --git a/lib/cbit/misc.h b/lib/cbit/misc.h
index 52835b1..7c558ce 100644
--- a/lib/cbit/misc.h
+++ b/lib/cbit/misc.h
@@ -1,5 +1,7 @@
 #pragma once
 
+#define UNUSED_STATIC_INLINE __attribute__((unused)) static inline
+
 #define LET_LOOP__(expr, ctr) \
     if (0) \
        __done_##ctr: continue; \
@@ -40,5 +42,7 @@
 #define LET_(expr, ctr) LET__(expr, ctr)
 #define LET(expr) LET_(expr, __COUNTER__)
 
-#define safe_mul(a, b) ((a) * (b)) /* XXX */
+/* XXX */
+#define safe_mul(a, b) ((a) * (b))
+#define safe_add(a, b) ((a) + (b))
 
diff --git a/lib/cbit/vec.c b/lib/cbit/vec.c
new file mode 100644
index 0000000..21038a2
--- /dev/null
+++ b/lib/cbit/vec.c
@@ -0,0 +1,23 @@
+#include "cbit/vec.h"
+#include <stdio.h>
+
+void vec_realloc_internal(struct vec_internal *vi, size_t new_capacity,
+                          size_t esize) {
+    size_t new_size = safe_mul(new_capacity, esize);
+    if (vi->els == vi->storage) {
+        void *new = malloc(new_size);
+        memcpy(new, vi->els, vi->capacity * esize);
+        vi->els = new;
+    } else {
+        vi->els = realloc(vi->els, new_size);
+    }
+    vi->capacity = new_capacity;
+}
+void vec_realloc_internal_as_necessary(struct vec_internal *vi,
+                                       size_t min_capacity,
+                                       size_t esize) {
+    if (min_capacity > vi->capacity)
+        vec_realloc_internal(vi, safe_mul(vi->capacity, 2), esize);
+    else if (min_capacity < vi->capacity / 3)
+        vec_realloc_internal(vi, vi->capacity / 3, esize);
+}
diff --git a/lib/cbit/vec.h b/lib/cbit/vec.h
new file mode 100644
index 0000000..87e4c28
--- /dev/null
+++ b/lib/cbit/vec.h
@@ -0,0 +1,121 @@
+#pragma once
+#include "misc.h"
+#include <stdlib.h>
+#include <string.h>
+
+struct vec_internal {
+   size_t length;
+   size_t capacity;
+   void *els;
+   char storage[1]; // must be at least one byte so vec_free works correctly
+};
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void vec_realloc_internal(struct vec_internal *vi, size_t new_capacity,
+                          size_t esize);
+void vec_realloc_internal_as_necessary(struct vec_internal *vi,
+                                       size_t min_capacity,
+                                       size_t esize);
+#ifdef __cplusplus
+}
+#endif
+
+#define DECL_VEC(ty, name) \
+   typedef ty __VEC_TY_##name; \
+   struct vec_##name { \
+      union { \
+         struct vec_internal vi; \
+         struct { \
+            size_t length; \
+            size_t capacity; \
+            VEC_TY(name) *els; \
+            VEC_TY(name) storage[1]; \
+         }; \
+      }; \
+   }; \
+   UNUSED_STATIC_INLINE \
+   void vec_free_storage(struct vec_##name *v) { \
+      if (v->els != v->storage) \
+         free(v->els); \
+   } \
+   UNUSED_STATIC_INLINE \
+   struct vec_##name vec_borrow(VEC_TY(name) *els, size_t length) { \
+      struct vec_##name v; \
+      v.length = v.capacity = length; \
+      v.els = els; \
+      return v; \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_realloc_##name(struct vec_##name *v, size_t new_capacity) { \
+      vec_realloc_internal(&v->vi, new_capacity, sizeof(v->els[0])); \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_resize_##name(struct vec_##name *v, size_t new_length) { \
+      if (new_length >= v->capacity || new_length < v->capacity / 3) \
+         vec_realloc_internal_as_necessary(&v->vi, new_length, sizeof(v->els[0])); \
+      v->length = new_length; \
+   } \
+   UNUSED_STATIC_INLINE \
+   VEC_TY(name) *vec_appendp_##name(struct vec_##name *v) { \
+      size_t i = v->length++; \
+      if (i == v->capacity) \
+         vec_realloc_internal_as_necessary(&v->vi, i + 1, sizeof(v->els[0])); \
+      return &v->els[i]; \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_append_##name(struct vec_##name *v, VEC_TY(name) val) { \
+      *vec_appendp_##name(v) = val; \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_concat_##name(struct vec_##name *v1, const struct vec_##name *v2) { \
+      size_t l1 = v1->length, l2 = v2->length; \
+      vec_resize_##name(v1, safe_add(l1, l2)); \
+      memcpy(&v1->els[l1], v2->els, l2 * sizeof(v1->els[0])); \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_add_space_##name(struct vec_##name *v, size_t idx, size_t num) { \
+      /* todo optimize */ \
+      size_t orig = v->length; \
+      vec_resize_##name(v, orig + num); \
+      memmove(&v->els[idx + num], &v->els[idx], \
+              (orig - idx) * sizeof(v->els[0])); \
+   } \
+   UNUSED_STATIC_INLINE \
+   void vec_remove_##name(struct vec_##name *v, size_t idx, size_t num) { \
+      /* todo optimize */ \
+      size_t orig = v->length; \
+      memmove(&v->els[idx], &v->els[idx + num], \
+              (orig - (idx + num)) * sizeof(v->els[0])); \
+      vec_resize_##name(v, orig - num); \
+   } \
+
+
+#define VEC_TY(name) __VEC_TY_##name
+
+#define VEC_STORAGE_CAPA(name, n) \
+   struct { \
+      struct vec_##name v; \
+      VEC_TY(name) rest[(n)-1]; \
+   }
+
+#define VEC_STORAGE(ty) \
+   VEC_STORAGE_CAPA(ty, 5)
+
+#define VEC_STORAGE_INIT(vs, name) do { \
+   struct vec_##name *v = &(vs)->v; \
+   v->length = 0; \
+   v->capacity = (sizeof((vs)->rest) / sizeof(VEC_TY(name))) + 1; \
+   v->els = v->storage; \
+} while (0)
+
+
+/* guaranteed to *not* cache vec->length - pretty simple */
+
+#define VEC_FOREACH(vec, idx_var, ptr_var, name) \
+   LET(struct vec_##name *__vfe_v = (vec)) \
+      for (size_t idx_var = 0; idx_var < __vfe_v->length; idx_var++) \
+         LET_LOOP(ptr_var = &__vfe_v->els[idx_var])
+