zilasm/symtable.c

   1 /*
   2  * symtable.c -- part of ZilUtils/ZilAsm
   3  *
   4  * Copyright (C) 2016, 2019 Jason Self <j@jxself.org>
   5  *
   6  * This program is free software: you can redistribute it and/or modify
   7  * it under the terms of the GNU Affero General Public License as
   8  * published by the Free Software Foundation, either version 3 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU Affero General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Affero General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18  *
  19  * SPDX-License-Identifier: AGPL-3.0-or-later
  20  */
  21
  22 #include <string.h>
  23 #include "strings.h"
  24 #include <stdlib.h>
  25 #include <assert.h>
  26
  27 #include "symtable.h"
  28
  29 #define FIELD_SIZE(Typ,Field)  (sizeof(((Typ*)0)->Field))
  30
  31 Symtable *
  32 symtable_create (unsigned elems_count, unsigned name_size, unsigned elem_size)
  33 {
  34   //size_t n = elems_count * (name_size + elem_size) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents);
  35   //Symtable *p = malloc(n);
  36
  37   Symtable *p = (Symtable *) malloc (sizeof (Symtable));
  38   assert (p);
  39   size_t n = elems_count * sizeof (SymtableElem);
  40   p->contents = (SymtableElem *) malloc (n);
  41   bzero (p->contents, n);
  42   p->elems_count = elems_count;
  43   p->name_size = name_size;
  44   p->elem_size = elem_size;
  45   return p;
  46 }
  47
  48
  49 void
  50 symtable_destroy (Symtable * p)
  51 {
  52   assert (p);
  53   for (int i = 0; i > p->elems_count; ++i)
  54     {
  55       free (p->contents[i].name);
  56       free (p->contents[i].value);
  57     }
  58   free (p->contents);
  59   free (p);
  60 }
  61
  62
  63 static unsigned
  64 name2pos (const Symtable * p, const char *name, unsigned namelen)
  65 {
  66   assert (p);
  67   unsigned key = 0;
  68   while (namelen--)
  69     key = ((key << 1) | (*name++));
  70   return key % p->elems_count;
  71 }
  72
  73
  74 static SymtableElem *
  75 getsym (const Symtable * p, unsigned pos)
  76 {
  77   //assert(p);   //already checked by caller
  78   //assert(pos < p->elems_count);
  79   //return ((char*)p) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents) + (pos * p->elem_size);
  80   return &p->contents[pos];
  81 }
  82
  83
  84 // searches for a element in the symbols table and returns its value
  85 void *
  86 symtable_lookup2 (const Symtable * p, const char *name, unsigned namelen)
  87 {
  88   assert (p);
  89   assert (name);
  90   assert (namelen > 0);
  91   assert (namelen < p->name_size);
  92
  93   unsigned start = name2pos (p, name, namelen);
  94   unsigned pos = start;
  95
  96   do
  97     {
  98       SymtableElem *s = getsym (p, pos);
  99       if (!s->name)
 100         return NULL;
 101       if (!memcmp (name, s->name, namelen))
 102         return s->value;
 103       if (++pos >= p->elems_count)
 104         pos = 0;
 105     }
 106   while (pos != start);
 107
 108   return NULL;
 109 }
 110
 111
 112 void *
 113 symtable_lookup (const Symtable * p, const char *name)
 114 {
 115   assert (name);
 116   return symtable_lookup2 (p, name, strlen (name));
 117 }
 118
 119
 120 void *
 121 symtable_add (Symtable * p, const char *name, void *value)
 122 {
 123   assert (name);
 124   return symtable_add2 (p, name, strlen (name), value);
 125 }
 126
 127
 128 void *
 129 symtable_add2 (Symtable * p, const char *name, unsigned namelen, void *value)
 130 {
 131   assert (p);
 132   assert (name);
 133   assert (namelen > 0 && namelen < p->name_size);
 134   assert (value);
 135
 136   unsigned start = name2pos (p, name, namelen);
 137   unsigned pos = start;
 138
 139   do
 140     {
 141       SymtableElem *elem = getsym (p, pos);
 142       if (!elem->name)
 143         {
 144           elem->name = (char *) malloc (namelen + 1);
 145           memcpy (elem->name, name, namelen + 1);
 146           elem->name[namelen] = '\0';
 147           elem->value = malloc (p->elem_size);
 148           memcpy (elem->value, value, p->elem_size);
 149           return elem;
 150         }
 151       if (!memcmp (name, elem->name, namelen) && elem->name[namelen] == '\0')
 152         {
 153           /* TODO!! report error */
 154           return NULL;          /* ..already added */
 155         }
 156       if (++pos >= p->elems_count)
 157         pos = 0;
 158     }
 159   while (pos != start);
 160
 161   /* TODO!! report overflow */
 162   return NULL;
 163   /* TODO!!! */
 164 }
 165
 166
 167 static int
 168 sortfunc (const void *a, const void *b)
 169 {
 170   const char *s1 = (const char *) a;
 171   const char *s2 = (const char *) b;
 172   if (!*s1 && !*s2)
 173     return 0;
 174   if (!*s1)
 175     return 1;
 176   if (!*s2)
 177     return -1;
 178   return strcmp (s1, s2);
 179 }
 180
 181
 182 void
 183 symtable_sort (Symtable * p)
 184 {
 185   assert (p);
 186   qsort (getsym (p, 0), p->elems_count, p->elem_size + p->name_size,
 187          sortfunc);
 188 }
 189
 190 /* END */