src/oblist.c

   1 /*
   2 Copyright (C) 2017-2018 Keziah Wesley
   3
   4 You can redistribute and/or modify this file under the terms of the
   5 GNU Affero General Public License as published by the Free Software
   6 Foundation, either version 3 of the License, or (at your option) any
   7 later version.
   8
   9 This file is distributed in the hope that it will be useful, but
  10 WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12 Affero General Public License for more details.
  13
  14 You should have received a copy of the GNU Affero General Public
  15 License along with this file. If not, see
  16 <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #include "alloc.h"
  20 #include "atom.h"
  21 #include "hash.h"
  22 #include "object.h"
  23 #include "oblist.h"
  24
  25 #include <assert.h>
  26 #include <string.h>
  27
  28 uvector_object
  29 oblist_create (uint32_t buckct)
  30 {
  31   heap_ptr body = heap_alloc_uv (buckct);
  32   memset (UV_VAL (body), '\0', buckct * sizeof (uv_val));
  33   uvector_object oblist = new_uvector (body, buckct);
  34   *uv_dope (&oblist) = new_dope (buckct, EVALTYPE_LIST);
  35   chtype ((object *) & oblist, EVALTYPE_OBLIST);
  36   return oblist;
  37 }
  38
  39 // TODO: define for other numeric types, move to general utility library
  40 inline static uint32_t
  41 u32_min (uint32_t x, uint32_t y)
  42 {
  43   return (x < y) ? x : y;
  44 }
  45
  46 #define MIN(x, y)                                 \
  47   _Generic((x+y),                                  \
  48            uint32_t: u32_min(x, y)                 \
  49           )
  50
  51 // debugging:
  52 #include <stdio.h>
  53 atom_object
  54 oblist_find_or_insert (uvector_object oblist, const char *name,
  55                        uint32_t namelen)
  56 {
  57   assert (oblist.val.len);
  58   uint32_t hash = fnv_32a_extend (name, namelen, fnv_32a_init ());
  59   uint32_t nbucket = hash % oblist.val.len;
  60   list_val *bucket = &UV_VAL (oblist.val.body)[nbucket].list;
  61   // linear search in the bucket
  62   pool_ptr *prev = &bucket->head;
  63   pool_ptr tail = 0;
  64   while (*prev)
  65     {
  66       atom_object *other = &POOL_OBJECT (*prev)->atom;
  67       int cmp =
  68         strncmp (name, atom_pname (*other),
  69                  MIN (namelen, atom_namelen (*other)));
  70       if (cmp < 0)
  71         {
  72           tail = *prev;
  73           break;
  74         }
  75       else if (!cmp)
  76         return *other;
  77       prev = &POOL_OBJECT (*prev)->rest;
  78     }
  79   // Either:
  80   // - reached end of list without finding; tail==0
  81   // - found where it should be in the list; tail is the rest (if any)
  82   *prev = pool_alloc (1);
  83   atom_object new = atom_create (name, namelen);
  84   POOL_OBJECT (*prev)->atom = new;
  85   POOL_OBJECT (*prev)->atom.rest = tail;
  86   return new;
  87 }
  88
  89 /*
  90 object
  91 oblist_lookup (uvector_object oblist, string_object name)
  92 {
  93 }
  94 */
  95
  96 #if 0
  97 atom_object
  98 intern_atom (const char *p, int len)
  99 {
 100   // TODO: look up in existing oblists first
 101
 102   uint32_t lenobjs = (len + sizeof (object) - 1) / sizeof (object);
 103   //heap_ptr body = heap_alloc (sizeof (atom_body) + lenobjs);
 104   heap_ptr body = atom_body_alloc (1);
 105   return new_atom (0);
 106 }
 107 #endif