dict

commit 681e2339e846ba645e5ff6ade641adfb30c3734e
parent b5311852537e210aa4da7463f8d5dd972d4952b6
Author: olikru <olikru@tkruger.se>
Date:   Tue,  9 Jan 2024 14:32:23 +0100

major refactor

Diffstat:
M
README
 | 
3
++-
M
dict.c
 | 
128
++++++++++++++++++++++++++++++++++++++++++++++++-------------------------------
M
dict.h
 | 
58
++++++++++++++++++++++++++++++++++++++++++++++------------
M
test_dict.c
 | 
96
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--

4 files changed, 220 insertions(+), 65 deletions(-)
diff --git a/README b/README
@@ -1,4 +1,5 @@
 dict
 ====
 
-Small dictionary type for sd_t's.
+Small dictionary type for sd_t's. Implementation specifically not made
+for being able to remove elements from the list.
diff --git a/dict.c b/dict.c
@@ -1,54 +1,31 @@
 #include "dict.h"
 
-static inline void stack_ptr_init_size(stack_ptr *d, const size_t alloc) {
-  d->nmemb = 0;
-  d->alloc = alloc;
-
-  d->data = calloc(d->alloc, sizeof(*(d->data)));
-}
-
-static inline void stack_ptr_clear(stack_ptr *d) {
-  d->nmemb = 0;
-  free(d->data);
-  d->data = NULL;
-}
-
-static inline void stack_ptr_push(stack_ptr *d, void *x) {
-  if (d->alloc <= d->nmemb) {
-    d->alloc <<= 1;
-    d->data = realloc(d->data, d->alloc * sizeof(*(d->data)));
-  }
-
-  d->data[d->nmemb] = x;
-  d->nmemb++;
-}
-
 void dict_init_size(dict_t *d, const size_t alloc) {
   d->nalloc = alloc;
   d->nelts = 0;
-  d->keys = calloc(d->nalloc, sizeof(*d->keys));
-  d->values = calloc(d->nalloc, sizeof(*d->values));
-
-  size_t i;
-  for (i = 0; i < d->nalloc; i++) {
-    stack_sd_init_size(&d->keys[i], DICT_DEFAULT_STACK_SIZE);
-    stack_ptr_init_size(&d->values[i], DICT_DEFAULT_STACK_SIZE);
-  }
+  d->keys = calloc(d->nalloc, sizeof(sd_t *));
+  d->values = calloc(d->nalloc, sizeof(*(d->values)));
+  d->nvalues = calloc(d->nalloc, sizeof(*(d->nvalues)));
+  d->value_alloc = calloc(d->nalloc, sizeof(*(d->value_alloc)));
 }
 
 void dict_init(dict_t *d) { dict_init_size(d, DICT_DEFAULT_SIZE); }
 
 void dict_clear(dict_t *d) {
-  size_t i;
+  size_t i,j;
   for (i = 0; i < d->nalloc; i++) {
-    stack_sd_clear(&d->keys[i]);
-    stack_ptr_clear(&d->values[i]);
+    for(j = 0; j < d->nvalues[i]; j++)
+      sd_clear(&(d->keys[i][j]));
+    free(d->keys[i]);
+    free(d->values[i]);
   }
 
   d->nalloc = 0;
   d->nelts = 0;
   free(d->keys);
   free(d->values);
+  free(d->nvalues);
+  free(d->value_alloc);
   d->keys = NULL;
   d->values = NULL;
 }
@@ -56,27 +33,78 @@ void dict_clear(dict_t *d) {
 void *dict_lookup(dict_t *d, sd_t k) {
   uint64_t h = sd_hash(&k);
   size_t i = h % d->nalloc;
-  int stack_idx = stack_sd_lookup(&d->keys[i], k);
+  size_t j;
 
-  if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
-    return NULL;
+  // linear search for key in d->keys[i]
+  for (j = 0; j < d->nvalues[i]; j++) {
+    if(sd_cmp(&(d->keys[i][j]), &k) == 0)
+      return d->values[i][j];
   }
 
-  return (d->values[i]).data[stack_idx];
+  return NULL;
 }
 
-#include <stdio.h>
+static inline void dict_basic_insert(dict_t *d, const sd_t * const key, void * const val, const size_t i) {
+  if (d->value_alloc[i] == 0) {
+    // create new stacks
+    d->value_alloc[i] = DICT_SMALLEST_STACK_SIZE;
+    d->values[i] = calloc(DICT_SMALLEST_STACK_SIZE, sizeof(*(d->values[i])));
+    d->keys[i] = calloc(DICT_SMALLEST_STACK_SIZE, sizeof(*(d->keys[i])));
+  } else if(d->value_alloc[i] == d->nvalues[i]) {
+    // double size
+    d->value_alloc[i] <<= 1;
+    d->values[i] = realloc(d->values[i], d->value_alloc[i] * sizeof(*(d->values[i])));
+    d->keys[i] = realloc(d->keys[i], d->value_alloc[i] * sizeof(*(d->keys[i])));
+  }
 
-void dict_insert(dict_t *d, sd_t k, void *value) {
-  uint64_t h = sd_hash(&k);
-  size_t i = h % d->nalloc;
-  int stack_idx = stack_sd_lookup(&d->keys[i], k);
-
-  if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
-    stack_sd_push(&(d->keys[i]), k);
-    stack_ptr_push(&(d->values[i]), value);
-    d->nelts++;
-  } else {
-    (d->values[i]).data[stack_idx] = value;
+  size_t j = d->nvalues[i];
+  d->keys[i][j] = *key;
+  d->values[i][j] = val;
+  d->nvalues[i]++;
+  d->nelts++;
+}
+
+static inline void dict_copy_insert(dict_t *d, const sd_t key, void * const val, const size_t i) {
+  // copy the key
+  sd_t key_copy;
+  sd_init(&key_copy, key.size);
+  memcpy(key_copy.data, key.data, key.size);
+
+  dict_basic_insert(d, &key_copy, val, i);
+}
+
+static inline void dict_resize(dict_t *d, const size_t nalloc) {
+  dict_t e;
+  dict_init_size(&e, nalloc);
+  size_t i,j, new_index;
+
+  // insert the elements into e
+  for (i = 0; i < d->nalloc; i++) {
+    for(j = 0; j < d->nvalues[i]; j++) {
+      new_index = sd_hash(&(d->keys[i][j])) % e.nalloc;
+      dict_basic_insert(&e, &(d->keys[i][j]), d->values[i][j], new_index);
+    }
+
+    // free the old stack with index i
+    free(d->keys[i]);
+    free(d->values[i]);
   }
+
+  // free the list of stacks
+  free(d->keys);
+  free(d->values);
+
+  // change d to point where d pointed
+  *d = e;
+}
+
+void dict_insert(dict_t *d, sd_t k, void *value) {
+  size_t i;
+
+  while(DICT_FACTOR * d->nelts > d->nalloc)
+    dict_resize(d, d->nalloc * DICT_FACTOR);
+
+  i = sd_hash(&k) % d->nalloc;
+
+  dict_copy_insert(d, k, value, i);
 }
diff --git a/dict.h b/dict.h
@@ -4,30 +4,64 @@
 #include "stack_sd.h"
 
 #define DICT_DEFAULT_SIZE 255
-#define DICT_DEFAULT_STACK_SIZE 2
-#define STACK_PTR_EMPTY_POP (NULL)
+#define DICT_SMALLEST_STACK_SIZE 2
 #define DICT_LOOKUP_NOT_FOUND (STACK_SD_LOOKUP_NOT_FOUND) // == -1
-
-typedef struct {
-  size_t nmemb;
-  size_t alloc;
-
-  void **data;
-} stack_ptr;
+#define DICT_FACTOR 2
 
 typedef struct {
   size_t nelts;
   size_t nalloc;
 
-  stack_sd_t *keys;
-  stack_ptr *values;
+  size_t* nvalues;
+  size_t* value_alloc;
+  sd_t **keys;
+  void ***values;
 } dict_t;
 
+/**
+ * Initialises a dictionary with a given size (allocated). The
+ * initialized dict_t will be "empty". This allocates memory that will
+ * need to be cleared (use dict_clear).
+ *
+ * @param d pointer to the dict_t to initialise
+ * @param alloc the size to allocate to it
+ */
 void dict_init_size(dict_t *d, const size_t alloc);
+
+/**
+ * Initialises a dictionary with the standard allocation size (which is
+ * DICT_DEFAULT_SIZE == 255).
+ *
+ * @param d pointer to the dict_t to initialise
+ */
 void dict_init(dict_t *d);
+
+/**
+ * Clears an initialised dictionary.
+ *
+ * @param d pointer to the dict_t to clear
+ */
 void dict_clear(dict_t *d);
+
+/**
+ * Lookup an element in the dictionary, by its key. Returns the void
+ * pointer which is stored as its value, if the dictionary contains the
+ * key. Otherwise, NULL is returned.
+ *
+ * @param d pointer to the dict_t to lookup in
+ * @param k the key to lookup with
+ */
 void *dict_lookup(dict_t *d, sd_t k);
+
+/**
+ * Insert an element (a key <-> value pair) into the dictionary. If the
+ * key is already in the dictionary the value is replaced with the
+ * provided value.
+ *
+ * @param d pointer to the dict_t to insert into
+ * @param k the key of the element to insert
+ * @param v the (void*) value to insert
+ */
 void dict_insert(dict_t *t, sd_t k, void *v);
-void print_dict(dict_t *d);
 
 #endif
diff --git a/test_dict.c b/test_dict.c
@@ -1,8 +1,100 @@
 #include <stdlib.h>
 #include <stdio.h>
 #include <assert.h>
-#include "fheap.h"
+#include "dict.h"
+
+static void test_dict_init() {
+  size_t i;
+  dict_t d;
+  dict_init_size(&d, 20);
+
+  assert(d.nalloc == 20);
+  assert(d.nelts == 0);
+  assert(d.keys != NULL);
+  assert(d.values != NULL);
+  assert(d.nvalues != NULL);
+  assert(d.value_alloc != NULL);
+
+  for (i = 0; i < d.nalloc; i++) {
+    assert(d.nvalues[i] == 0);
+    assert(d.value_alloc[i] == 0);
+    assert(d.keys[i] == NULL);
+    assert(d.values[i] == NULL);
+  }
+
+  dict_clear(&d);
+
+  dict_init(&d);
+
+  assert(d.nalloc == DICT_DEFAULT_SIZE);
+  assert(d.nelts == 0);
+  assert(d.keys != NULL);
+  assert(d.values != NULL);
+  assert(d.nvalues != NULL);
+  assert(d.value_alloc != NULL);
+
+  for (i = 0; i < d.nalloc; i++) {
+    assert(d.nvalues[i] == 0);
+    assert(d.value_alloc[i] == 0);
+    assert(d.keys[i] == NULL);
+    assert(d.values[i] == NULL);
+  }
+
+  dict_clear(&d);
+}
+
+static void test_dict_insert() {
+  dict_t d;
+  dict_init_size(&d, 4);
+
+  sd_t elts[7];
+  uint64_t values[7] = {1,2,3,4,5,6,7};
+  size_t i;
+  for(i = 0; i < 7; i++) {
+    sd_init_u64(&elts[i], 2*i+1);
+    dict_insert(&d, elts[i], &values[i]);
+  }
+
+  assert(d.nelts == 7);
+  assert(d.nalloc >= 7);
+
+  for(i = 0; i < 7; i++)
+    sd_clear(&elts[i]);
+  dict_clear(&d);
+}
+
+static void test_dict_lookup() {
+  dict_t d;
+  dict_init_size(&d, 4);
+
+  sd_t elts[7];
+  uint64_t values[7] = {1,2,3,4,5,6,7};
+  size_t i;
+  for(i = 0; i < 7; i++) {
+    sd_init_u64(&elts[i], 2*i+1);
+    dict_insert(&d, elts[i], &values[i]);
+  }
+
+  sd_t pelt[2];
+  sd_init_u64(&pelt[0], 5);
+  sd_init_u64(&pelt[1], 37);
+
+  for(i = 0; i < 7; i++)
+    assert(* (uint64_t*) dict_lookup(&d, elts[i]) == i+1);
+
+  assert(* (uint64_t*)  dict_lookup(&d, pelt[0]) == 3);
+  assert(dict_lookup(&d, pelt[1]) == NULL);
+
+  for(i = 0; i < 7; i++)
+    sd_clear(&elts[i]);
+  dict_clear(&d);
+}
+
 
 int main() {
-  printf("test unimplemented\n");
+  test_dict_init();
+  test_dict_insert();
+  test_dict_lookup();
+
+  printf("test ok\n");
 }