kernel/symtab.c

   1 /*
   2  *    Copyright (c) 2009 Joshua Phillips. All rights reserved.
   3  *
   4  *  Redistribution and use in source and binary forms, with or without
   5  *  modification, are permitted provided that the following conditions are
   6  *  met:
   7  *
   8  *    1. Redistributions of source code must retain the above copyright
   9  *       notice, this list of conditions and the following disclaimer.
  10  *    2. Redistributions in binary form must reproduce the above copyright
  11  *       notice, this list of conditions and the following disclaimer in
  12  *       the documentation and/or other materials provided with the
  13  *       distribution.
  14  *
  15  *  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
  16  *  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18  *  DISCLAIMED. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
  19  *  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  21  *  GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  22  *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  23  *  IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  *  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  25  *  IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "symtab.h"
  29 #include "trace.h"
  30 #include "console.h"
  31 #include "stdlib.h"
  32 #include "string.h"
  33
  34 enum {
  35     MAX_HASH = 256,
  36 };
  37
  38 struct sym {
  39     struct sym *hash_prev;
  40     uintptr_t value;
  41     char name[1];
  42 };
  43
  44 static struct sym *hashtab[MAX_HASH];
  45
  46 static int hash(const char *str)
  47 {
  48     unsigned int hash = 0;
  49     while (*str){
  50         hash = hash * 263 + *str;
  51         ++str;
  52     }
  53     return hash % MAX_HASH;
  54 }
  55
  56 void symtab_init(void)
  57 {
  58     memset(hashtab, 0, sizeof hashtab);
  59 }
  60
  61 int symtab_insert(const char *name, uintptr_t value)
  62 {
  63     const int h = hash(name);
  64     struct sym *s;
  65
  66     s = hashtab[h];
  67
  68     while (s){
  69         if (!strcmp(name, s->name)){
  70             // already in the symbol table
  71             return 0;
  72         }
  73         s = s->hash_prev;
  74     }
  75
  76     // insert into hash table
  77     s = malloc(sizeof *s + strlen(name));
  78     if (!s){
  79         TRACE("memory full");
  80         return 1;
  81     }
  82
  83     strcpy(s->name, name);
  84     s->value = value;
  85     s->hash_prev = hashtab[h];
  86     hashtab[h] = s;
  87     return 0;
  88 }
  89
  90 uintptr_t symtab_lookup(const char *name)
  91 {
  92     int h = hash(name);
  93     struct sym *s;
  94
  95     s = hashtab[h];
  96     while (s){
  97         if (!strcmp(name, s->name)){
  98             return s->value;
  99         }
 100         s = s->hash_prev;
 101     }
 102     return 0;
 103 }