Implement OBLISTs

[muddle-interpreter.git] / src / oblist.c

diff --git a/src/oblist.c b/src/oblist.c
new file mode 100644 (file)
index 0000000..895920a
--- /dev/null
+++ b/src/oblist.c
@@ -0,0 +1,107 @@
+/*
+Copyright (C) 2017-2018 Keziah Wesley
+
+You can redistribute and/or modify this file under the terms of the
+GNU Affero General Public License as published by the Free Software
+Foundation, either version 3 of the License, or (at your option) any
+later version.
+
+This file is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+Affero General Public License for more details.
+
+You should have received a copy of the GNU Affero General Public
+License along with this file. If not, see
+<http://www.gnu.org/licenses/>.
+*/
+
+#include "alloc.h"
+#include "atom.h"
+#include "hash.h"
+#include "object.h"
+#include "oblist.h"
+
+#include <assert.h>
+#include <string.h>
+
+uvector_object
+oblist_create (uint32_t buckct)
+{
+  heap_ptr body = heap_alloc_uv (buckct);
+  memset (UV_VAL (body), '\0', buckct * sizeof (uv_val));
+  uvector_object oblist = new_uvector (body, buckct);
+  *uv_dope (&oblist) = new_dope (buckct, EVALTYPE_LIST);
+  chtype ((object *) & oblist, EVALTYPE_OBLIST);
+  return oblist;
+}
+
+// TODO: define for other numeric types, move to general utility library
+inline static uint32_t
+u32_min (uint32_t x, uint32_t y)
+{
+  return (x < y) ? x : y;
+}
+
+#define MIN(x, y)                                 \
+  _Generic((x+y),                                  \
+           uint32_t: u32_min(x, y)                \
+          )
+
+// debugging:
+#include <stdio.h>
+atom_object
+oblist_find_or_insert (uvector_object oblist, const char *name,
+                      uint32_t namelen)
+{
+  assert (oblist.val.len);
+  uint32_t hash = fnv_32a_extend (name, namelen, fnv_32a_init ());
+  uint32_t nbucket = hash % oblist.val.len;
+  list_val *bucket = &UV_VAL (oblist.val.body)[nbucket].list;
+  // linear search in the bucket
+  pool_ptr *prev = &bucket->head;
+  pool_ptr tail = 0;
+  while (*prev)
+    {
+      atom_object *other = &POOL_OBJECT (*prev)->atom;
+      int cmp =
+       strncmp (name, atom_pname (*other),
+                MIN (namelen, atom_namelen (*other)));
+      if (cmp < 0)
+       {
+         tail = *prev;
+         break;
+       }
+      else if (!cmp)
+       return *other;
+      prev = &POOL_OBJECT (*prev)->rest;
+    }
+  // Either:
+  // - reached end of list without finding; tail==0
+  // - found where it should be in the list; tail is the rest (if any)
+  *prev = pool_alloc (1);
+  atom_object new = atom_create (name, namelen);
+  POOL_OBJECT (*prev)->atom = new;
+  POOL_OBJECT (*prev)->atom.rest = tail;
+  return new;
+}
+
+/*
+object
+oblist_lookup (uvector_object oblist, string_object name)
+{
+}
+*/
+
+#if 0
+atom_object
+intern_atom (const char *p, int len)
+{
+  // TODO: look up in existing oblists first
+
+  uint32_t lenobjs = (len + sizeof (object) - 1) / sizeof (object);
+  //heap_ptr body = heap_alloc (sizeof (atom_body) + lenobjs);
+  heap_ptr body = atom_body_alloc (1);
+  return new_atom (0);
+}
+#endif