zilasm/symtable.c

   1 /*
   2  * symtable.c -- part of ZilUtils/ZilAsm
   3  *
   4  * Copyright (C) 2016 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 <stdlib.h>
  24 #include <assert.h>
  25
  26 #include "symtable.h"
  27
  28 #define FIELD_SIZE(Typ,Field)  (sizeof(((Typ*)0)->Field))
  29
  30 Symtable* symtable_create(unsigned elems_count, unsigned name_size, unsigned elem_size)
  31 {
  32         size_t n = elems_count * (name_size + elem_size) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents);
  33         Symtable *p = malloc(n);
  34         assert(p);
  35         bzero(p, n);
  36         p->elems_count = elems_count;
  37         p->name_size   = name_size;
  38         p->elem_size   = elem_size;
  39         return p;
  40 }
  41
  42 void symtable_destroy(Symtable *p)
  43 {
  44         assert(p);
  45         free(p);
  46 }
  47
  48 static unsigned name2pos(const Symtable *p, const char *name, unsigned namelen)
  49 {
  50         assert(p);
  51         unsigned key = 0;
  52         while(namelen--)
  53                 key = ((key << 1) | (*name++));
  54         return key % p->elems_count;
  55 }
  56
  57 static char *getsym(const Symtable *p, unsigned pos)
  58 {
  59         //assert(p);   //already checked by caller
  60         //assert(pos < p->elems_count);
  61         return ((char*)p) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents) + (pos * p->elem_size);
  62 }
  63
  64 void* symtable_lookup2(const Symtable *p, const char *name, unsigned namelen)
  65 {
  66         assert(p);
  67         assert(name);
  68         assert(namelen > 0);
  69         assert(namelen < p->name_size);
  70
  71         unsigned start = name2pos(p, name, namelen);
  72         unsigned pos = start;
  73
  74         do {
  75                 char *s = getsym(p, pos);
  76                 if (!*s)
  77                         return NULL;
  78                 if (!memcmp(name, s, namelen))
  79                         return s + p->name_size;
  80                 if (++pos >= p->elems_count)
  81                         pos = 0;
  82         } while(pos != start);
  83
  84         return NULL;
  85 }
  86
  87 void* symtable_lookup(const Symtable *p, const char *name)
  88 {
  89         assert(name);
  90         return symtable_lookup2(p, name, strlen(name));
  91 }
  92
  93 void* symtable_add(Symtable *p, const char *name, void *contents)
  94 {
  95         assert(name);
  96         return symtable_add2(p, name, strlen(name), contents);
  97 }
  98
  99 void* symtable_add2(Symtable *p, const char *name, unsigned namelen, void *contents)
 100 {
 101         assert(p);
 102         assert(name);
 103         assert(namelen > 0 && namelen < p->name_size);
 104         assert(contents);
 105
 106         unsigned start = name2pos(p, name, namelen);
 107         unsigned pos = start;
 108
 109         do {
 110                 char *s = getsym(p, pos);
 111                 if (!*s) {
 112                         memcpy(s, name, namelen + 1);
 113                         s[namelen] = '\0';
 114                         memcpy(s + p->name_size, contents, p->elem_size);
 115                         return s + p->name_size;
 116                 }
 117                 if (!memcmp(name, s, namelen) && s[namelen] == '\0') {
 118                         /* TODO!! report error */
 119                         return NULL;  /* ..already added */
 120                 }
 121                 if (++pos >= p->elems_count)
 122                         pos = 0;
 123         } while(pos != start);
 124
 125         /* TODO!! report overflow */
 126         return NULL;
 127         /* TODO!!! */
 128 }
 129
 130 static int sortfunc(const void *a, const void *b)
 131 {
 132         const char *s1 = a;
 133         const char *s2 = b;
 134         if (!*s1 && !*s2) return  0;
 135         if (!*s1)         return  1;
 136         if (!*s2)         return -1;
 137         return strcmp(s1, s2);
 138 }
 139
 140 void symtable_sort(Symtable *p)
 141 {
 142         assert(p);
 143         qsort(getsym(p, 0), p->elems_count, p->elem_size + p->name_size, sortfunc);
 144 }
 145
 146 /* END */