completing inserts

3 files changed, 102 insertions, 32 deletions

diff --git a/cheesemap.c b/cheesemap.c
index efa4751..e610a84 100644
--- a/cheesemap.c
+++ b/cheesemap.c
@@ -37,6 +37,14 @@ static inline void cm_sequence_next(struct sequence* sequence,
   sequence->pos &= bucket_mask;
 }
 
+/* ctrl ops */
+static inline bool cm_ctrl_is_special(uint8_t v) { return v & CM_CTRL_DELETED; }
+
+static inline bool cm_ctrl_is_empty(uint8_t v) {
+  assert(cm_ctrl_is_special(v) == true);
+  return (v & CM_CTRL_END) != 0;
+}
+
 /* group ops */
 static inline group_t cm_group_load(const uint8_t* ctrl);
 static inline bitmask_t cm_group_empty_or_deleted(group_t group);
@@ -59,16 +67,32 @@ static inline bitmask_t cm_group_empty_or_deleted(group_t group) {
 }
 
 /* static ctrl's */
-const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE] = {
-    CM_CTRL_EMPTY, CM_CTRL_EMPTY, CM_CTRL_EMPTY, CM_CTRL_EMPTY,
-    CM_CTRL_EMPTY, CM_CTRL_EMPTY, CM_CTRL_EMPTY, CM_CTRL_EMPTY,
-};
+const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE] = {[0 ... CM_GROUP_SIZE - 1] =
+                                                         CM_CTRL_EMPTY};
 
 /* hashmap implementation */
+static inline uint8_t* cm_raw_elem_at(const struct cheesemap_raw* map,
+                                      uintptr_t index, uintptr_t entry_size) {
+  assert(map != NULL);
+  assert(map->bucket_mask + 1 > index);
+
+  return map->ctrl - entry_size * index;
+}
+
 static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map,
                                      uintptr_t entry_size) {
   assert(map != NULL);
-  return map->ctrl - entry_size * (map->bucket_mask + 1);
+  return cm_raw_elem_at(map, map->bucket_mask + 1, entry_size);
+}
+
+static inline void cm_raw_ctrl_set(struct cheesemap_raw* map, uintptr_t index,
+                                   uint8_t ctrl) {
+  assert(map != NULL);
+
+  uintptr_t index2 =
+      ((index - CM_GROUP_SIZE) & map->bucket_mask) + CM_GROUP_SIZE;
+  map->ctrl[index] = ctrl;
+  map->ctrl[index2] = ctrl;
 }
 
 static bool cm_raw_find_insert_index_in_group(const struct cheesemap_raw* map,
@@ -97,33 +121,65 @@ static uintptr_t cm_raw_find_insert_index(const struct cheesemap_raw* map,
     group_t group = cm_group_load(ctrl);
 
     uintptr_t index;
-    if (cm_raw_find_insert_index_in_group(map, &group, &seq, &index)) return index;
+    if (cm_raw_find_insert_index_in_group(map, &group, &seq, &index))
+      return index;
     cm_sequence_next(&seq, map->bucket_mask);
   }
 }
 
-void cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
-                   cm_hash_t hash, const void* value) {
-  assert(map != NULL && fns != NULL);
+static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash,
+                             uintptr_t index, uintptr_t key_size,
+                             const uint8_t* key, uintptr_t value_size,
+                             const uint8_t* value) {
+  assert(map != NULL);
   assert(value != NULL);
+
+  uint8_t old_ctrl = map->ctrl[index];
+  map->growth_left -= cm_ctrl_is_empty(old_ctrl);
+  cm_raw_ctrl_set(map, index, cm_h2(hash));
+
+  uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size);
+  memcpy(elem, key, key_size);
+  elem += key_size;
+  memcpy(elem, value, value_size);
+
+  map->count += 1;
+}
+
+bool cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
+                   uintptr_t key_size, const uint8_t* key, uintptr_t value_size,
+                   const uint8_t* value) {
+  assert(map != NULL && fns != NULL);
+  assert(key != NULL && value != NULL);
+
+  cm_hash_t hash = fns->hash(key, fns->map_usr);
+  uintptr_t index = cm_raw_find_insert_index(map, hash);
+
+  uint8_t old_ctrl = map->ctrl[index];
+  if (map->growth_left == 0 && cm_ctrl_is_empty(old_ctrl)) {
+    // TODO: do resize
+  }
+
+  cm_raw_insert_at(map, hash, index, key_size, key, value_size, value);
+  return true;
 }
 
-void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size,
-                 const struct cheesemap_fns* fns) {
+void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size,
+                 uintptr_t value_size, const struct cheesemap_fns* fns) {
   assert(map != NULL);
   assert(fns != NULL);
 
   if (map->ctrl == CM_CTRL_STATIC_EMPTY || map->ctrl == NULL) return;
 
-  uint8_t* origin = cm_raw_origin(map, entry_size);
+  uint8_t* origin = cm_raw_origin(map, key_size + value_size);
   fns->free(origin, fns->mem_usr);
 
   *map = cm_raw_new();
 }
 
-void cm_new(struct cheesemap* map, uintptr_t entry_size, uint8_t* mem_usr,
-            cm_malloc_fn malloc, cm_free_fn free, uint8_t* map_usr,
-            cm_hash_fn hash, cm_compare_fn compare) {
+void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size,
+            uint8_t* mem_usr, cm_malloc_fn malloc, cm_free_fn free,
+            uint8_t* map_usr, cm_hash_fn hash, cm_compare_fn compare) {
   assert(map != NULL);
   assert(malloc != NULL && free != NULL);
   assert(hash != NULL && compare != NULL);
@@ -133,5 +189,5 @@ void cm_new(struct cheesemap* map, uintptr_t entry_size, uint8_t* mem_usr,
       malloc,  free,     //
       hash,    compare,  //
   };
-  *map = (struct cheesemap){entry_size, fns, cm_raw_new()};
+  *map = (struct cheesemap){key_size, value_size, fns, cm_raw_new()};
 }
diff --git a/cheesemap.h b/cheesemap.h
index 520c3aa..a4b007b 100644
--- a/cheesemap.h
+++ b/cheesemap.h
@@ -5,6 +5,7 @@
 // options and includes
 //
 
+#include <limits.h>
 #include <stdbool.h>
 #include <stdint.h>
 #include <string.h>
@@ -58,11 +59,13 @@ struct cheesemap_fns {
 enum {
   CM_INITIAL_CAPACITY = CM_GROUP_SIZE,
   // -1 as i8, all bits set, top bit = 1
-  CM_CTRL_EMPTY = 0xFF,
+  CM_CTRL_EMPTY = 0xFF,  // 0b1111_1111
   // -128 as i8, top bit = 1
-  CM_CTRL_DELETED = 0x80,
+  CM_CTRL_DELETED = 0x80,  // 0b1000_0000
   // FULL entries have top bit = 0, lower 7 bits are H2 hash
-  CM_H2_MASK = 0x7F,
+  CM_H2_MASK = 0x7F,  // 0b0111_1111
+  // Mask to get bottom bit
+  CM_CTRL_END = 0x01,  // 0b0000_0001
   CM_FP_SIZE = 7
 };
 
@@ -71,7 +74,8 @@ static inline uintptr_t cm_h1(cm_hash_t hash) {
 }
 
 static inline uint8_t cm_h2(cm_hash_t hash) {
-  return (uint8_t)(hash & CM_H2_MASK);
+  uintptr_t top = hash >> (sizeof(cm_hash_t) * CHAR_BIT - CM_FP_SIZE);
+  return (uint8_t)(top & CM_H2_MASK);
 }
 
 extern const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE];
@@ -80,7 +84,7 @@ struct cheesemap_raw {
   // number of buckets as mask
   uintptr_t bucket_mask;
   // number of entries in the map
-  uintptr_t entry_count;
+  uintptr_t count;
   // number of entry left until resize
   uintptr_t growth_left;
   // pointer to the control bytes
@@ -90,29 +94,30 @@ struct cheesemap_raw {
 #define cm_raw_new() \
   ((struct cheesemap_raw){.ctrl = (uint8_t*)CM_CTRL_STATIC_EMPTY})
 
-void cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
-                   const void* key, const void* value);
-void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size,
-                 const struct cheesemap_fns* fns);
+bool cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
+                   uintptr_t key_size, const uint8_t* key, uintptr_t value_size,
+                   const uint8_t* value);
+void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size,
+                 uintptr_t value_size, const struct cheesemap_fns* fns);
 
 ////////////////////////////////
 // cheesemap implementation
 //
 
 struct cheesemap {
-  uintptr_t entry_size;
+  uintptr_t key_size, value_size;
   struct cheesemap_fns fns;
   struct cheesemap_raw raw;
 };
 
-void cm_new(struct cheesemap* map, uintptr_t entry_size, uint8_t* mem_usr,
-            cm_malloc_fn malloc, cm_free_fn free, uint8_t* map_usr,
-            cm_hash_fn hash, cm_compare_fn compare);
+void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size,
+            uint8_t* mem_usr, cm_malloc_fn malloc, cm_free_fn free,
+            uint8_t* map_usr, cm_hash_fn hash, cm_compare_fn compare);
 
 static inline void cm_drop(struct cheesemap* map) {
   assert(map != NULL);
 
-  cm_raw_drop(&map->raw, map->entry_size, &map->fns);
+  cm_raw_drop(&map->raw, map->key_size, map->value_size, &map->fns);
   memset(map, 0, sizeof(*map));
 }
 
diff --git a/makefile b/makefile
index 8e7686a..429dd50 100644
--- a/makefile
+++ b/makefile
@@ -1,4 +1,6 @@
 # Header in which assert(x) is defined
+CM_OPT_RELEASE ?= 0
+CM_OPT_CC_FLAGS ?=
 CM_OPT_ASSERT_PATH ?= <assert.h>
 
 CC ?= gcc
@@ -10,9 +12,16 @@ CM_OBJECT := $(CM_SOURCE:.c=.o)
 CM_DEPEND := $(CM_SOURCE:.c=.d)
 
 CM_CC_FLAGS := \
-	-Wall -Wextra -pedantic \
+	-Wall -Wextra \
 	-MMD -MP -I$(CM_DIR)
 
+ifeq ($(CM_OPT_RELEASE),1)
+	CM_CC_FLAGS += -O2 -fno-stack-protector
+else
+	CM_CC_FLAGS += -g3
+endif
+
+CM_CC_FLAGS += $(CM_OPT_CC_FLAGS)
 CM_CC_FLAGS += -DCM_OPT_ASSERT_PATH='$(CM_OPT_ASSERT_PATH)'
 
 .PHONY: all
@@ -25,4 +34,4 @@ $(CM_OBJECT): $(CM_SOURCE)
 clean::
 	$(RM) $(CM_OBJECT) $(CM_DEPEND)
 
--include $(CM_DEPEND)
\ No newline at end of file
+-include $(CM_DEPEND)