mindex.c

commit aa8f2b06aabaa472ea1a87df14ce2a06df335947
parent a96cd70139497ca4ee7603e6bb006a7619a7b5d7
Author: Yersa Nordman <yersa@finwo.nl>
Date:   Thu,  2 Mar 2023 22:24:36 +0100

Initial implementation & basic testing

Diffstat:
M
Makefile
 | 
3
+++
M
src/mindex.c
 | 
156
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
M
src/mindex.h
 | 
5
++++-
M
test.c
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 217 insertions(+), 8 deletions(-)
diff --git a/Makefile b/Makefile
@@ -2,6 +2,9 @@ SRC:=
 SRC+=$(wildcard src/*.c)
 SRC+=test.c
 
+INCLUDES?=
+INCLUDES+=-I src
+
 override CFLAGS?=-Wall -g -O2
 
 include lib/.dep/config.mk
diff --git a/src/mindex.c b/src/mindex.c
@@ -1,33 +1,175 @@
+#define _GNU_SOURCE
+
+#include <stdlib.h>
+#include <string.h>
+
 #include "mindex.h"
 
-struct mindex_t * mindex_init(int (*compare)(const void *a, const void *b, void *udata), void *udata) {
+#ifndef MINDEX_SPARE
+#define MINDEX_SPARE 16
+#endif
+
+struct mindex_t * mindex_init(int (*compare)(const void *a, const void *b, void *udata), void (*purge)(const void *item, void *udata), void *udata) {
   struct mindex_t *mindex = malloc(sizeof(struct mindex_t));
   mindex->compare = compare;
-  mindex->items   = NULL;
+  mindex->purge   = purge;
+  mindex->udata   = udata;
+  mindex->items   = malloc(MINDEX_SPARE * sizeof(void*));
   mindex->length  = 0;
-  return NULL;
+  mindex->spare   = MINDEX_SPARE;
+  return mindex;
 }
 
 void mindex_set(struct mindex_t *mindex, void *item) {
 
+  // Check if the item is already in the list
+  void *found = mindex_get(mindex, item);
+
+  // The exact pointer already there = done
+  if (found && (item == found)) {
+    return;
+  }
+
+  // Different pointer, so remove from the list
+  // Indicate to lib user that it needs to be purged from mem
+  if (found) {
+    mindex_delete(mindex, found);
+    mindex->purge(found, mindex->udata);
+  }
+
+  // Allocate more space if we ran out
+  if (!mindex->spare) {
+    mindex->items = realloc(mindex->items, (mindex->length + MINDEX_SPARE) * sizeof(void*));
+    mindex->spare = MINDEX_SPARE;
+  }
+
+  // Add the new item to the end of the list
+  mindex->items[mindex->length] = item;
+  mindex->length++;
+  mindex->spare--;
+
+  // Sort the list
+  qsort_r(mindex->items, mindex->length, sizeof(void *), mindex->compare, mindex->udata);
+
+  // Done
+}
+
+// Returns the INDEX within the items, not the item itself
+int mindex_get_internal(void **items, size_t length, void *pattern, int (*compare)(const void *a, const void *b, void *udata), void *udata) {
+  int sub;
+
+  // No entries = not found
+  if (length < 1) {
+    return -1;
+  }
+
+  // Test the middle of the array
+  size_t testIdx = length / 2;
+  int compare_result = compare(items[testIdx], pattern, udata);
+
+  // Match = found
+  if (compare_result == 0) {
+    return testIdx;
+  }
+
+  // Pattern = to the right
+  if (compare_result < 0) {
+    sub = mindex_get_internal(
+      &(items[testIdx+1]),
+      length - testIdx - 1,
+      pattern,
+      compare,
+      udata
+    );
+
+    // Pass along error code
+    if (sub < 0) {
+      return sub;
+    }
+
+    // Return mapped location
+    return sub + testIdx + 1;
+  }
+
+  // Pattern to the left
+  if (compare_result > 0) {
+    return mindex_get_internal(
+      items,
+      testIdx,
+      pattern,
+      compare,
+      udata
+    );
+  }
+
+  // Should never be called
+  return -2;
 }
 
 void * mindex_get(struct mindex_t *mindex, void *pattern) {
-  return NULL;
+  int idx = mindex_get_internal(mindex->items, mindex->length, pattern, mindex->compare, mindex->udata);
+
+  // Not found
+  if (idx < 0) {
+    return NULL;
+  }
+
+  return mindex->items[idx];
 }
 
 void * mindex_rand(struct mindex_t *mindex) {
-  return NULL;
+  if (!mindex->length) {
+    return NULL;
+  }
+  return mindex->items[rand() % mindex->length];
 }
 
-void mindex_delete(struct mindex_t *mindex, void *item) {
+// TODO: mindex_delete_internal(..., items, idx)
+
+void mindex_delete(struct mindex_t *mindex, void *pattern) {
+  int idx = mindex_get_internal(mindex->items, mindex->length, pattern, mindex->compare, mindex->udata);
+  void *item = mindex->items[idx];
 
+  // Purge if not an exact match
+  if (item != pattern) {
+    mindex->purge(item, mindex->udata);
+  }
+
+  // Move everything on it's right to it
+  void *dst = &(mindex->items[idx]);
+  void *src = &(mindex->items[idx+1]);
+  memmove(dst, src, mindex->length - idx - 1);
+
+  // Update our size trackers
+  mindex->length--;
+  mindex->spare++;
+
+  // Free some memory if we have a lot of spares
+  if (mindex->spare > (MINDEX_SPARE*2)) {
+    mindex->items = realloc(mindex->items, (mindex->length + MINDEX_SPARE) * sizeof(void*));
+    mindex->spare = MINDEX_SPARE;
+  }
+
+  // Done
 }
 
 size_t mindex_length(struct mindex_t *mindex) {
-  return 0;
+  return mindex->length;
 }
 
 void mindex_free(struct mindex_t *mindex) {
 
+  // Step 1, purge all entries
+  int i;
+  for (i=0; i < mindex->length; i++) {
+    mindex->purge(mindex->items[i], mindex->udata);
+  }
+
+  // Step 2, free the list
+  free(mindex->items);
+
+  // Step 3, free the mindex itself
+  free(mindex);
+
+  // Done
 }
diff --git a/src/mindex.h b/src/mindex.h
@@ -5,11 +5,14 @@
 
 struct mindex_t {
   int (*compare)(const void *a, const void *b, void *udata);
+  void (*purge)(const void *item, void *udata);
+  void *udata;
   size_t length;
+  size_t spare;
   void **items;
 };
 
-struct mindex_t * mindex_init(int (*compare)(const void *a, const void *b, void *udata), void *udata);
+struct mindex_t * mindex_init(int (*compare)(const void *a, const void *b, void *udata), void (*purge)(const void *item, void *udata), void *udata);
 void              mindex_set(struct mindex_t *mindex, void *item);
 void            * mindex_get(struct mindex_t *mindex, void *pattern);
 void            * mindex_rand(struct mindex_t *mindex);
diff --git a/test.c b/test.c
@@ -1,5 +1,66 @@
+#include <stdlib.h>
+#include <string.h>
+
 #include "finwo/assert.h"
+#include "mindex.h"
+
+static void fn_purge(const void *item, void *udata) {
+  // Intentionally empty
+}
+
+static int fn_compare(const void *a, const void *b, void *udata) {
+  const char *sa = a;
+  const char *sb = b;
+  return strcmp(sa, sb);
+}
+
+char *test_a00 = "Hello World";
+char *test_a01 = "Hello World";
+char *test_a02 = "Foobar";
+
+void test_mindex_basics() {
+  struct mindex_t *mindex = mindex_init(fn_compare, fn_purge, NULL);
+
+  ASSERT("mindex_init returns non-null", mindex != NULL);
+
+  mindex_set(mindex, test_a01);
+  mindex_set(mindex, test_a00);
+  mindex_set(mindex, test_a02);
+
+  ASSERT("length = 2 after inserting 3 strings with 1 duplicate", mindex_length(mindex) == 2);
+
+  char *found = mindex_get(mindex, test_a00);
+
+  ASSERT("Fetching by original = get original", found == test_a00);
+
+  found = mindex_get(mindex, test_a01);
+
+  ASSERT("Fetching by same content = get original", found == test_a00);
+
+  found = mindex_get(mindex, test_a02);
+
+  ASSERT("Fetching by other = get other", found == test_a02);
+
+  mindex_set(mindex, test_a01);
+  found = mindex_get(mindex, test_a00);
+
+  ASSERT("Overridden get by org returns new", found == test_a01);
+
+  found = mindex_get(mindex, test_a01);
+
+  ASSERT("Overridden get by new returns new", found == test_a01);
+}
 
 int main() {
+
+  // Seed random
+  unsigned int seed;
+  FILE* urandom = fopen("/dev/urandom", "r");
+  fread(&seed, sizeof(int), 1, urandom);
+  fclose(urandom);
+  srand(seed);
+
+  // Run the actual tests
+  RUN(test_mindex_basics);
   return TEST_REPORT();
 }