typedef.c

   1 /*
   2  * Copyright (C) 2012
   3  *      Dale Weiler
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include <string.h>
  24 #include <stdint.h> /* replace if stdint.h doesn't exist! */
  25 #include <limits.h>
  26 #include "gmqcc.h"
  27
  28 /*
  29  * This implements a hashtable for typedef type keywords which end up
  30  * being translated to their full-expressed type.  This uses a singly
  31  * linked list with a fast hash function.
  32  */
  33 static typedef_node *typedef_table[1024];
  34
  35 void typedef_init() {
  36         int i;
  37         for(i = 0; i < sizeof(typedef_table)/sizeof(*typedef_table); i++)
  38                 typedef_table[i] = NULL;
  39 }
  40
  41 /*
  42  * Fast collisionless hashfunction based off of:
  43  * http://www.azillionmonkeys.com/qed/hash.html
  44  * By: Paul Hsieh
  45  *
  46  * The code is licensed under LGPL 2.1 or Paul
  47  * Hsieh's derivative license. Stated on his page
  48  * quote:
  49  *
  50  *      The LGPL 2.1 is not necessarily a more liberal license than my
  51  *      derivative license, but this additional licensing makes the code
  52  *      available to more developers. Note that this does not give you
  53  *      multi-licensing rights. You can only use the code under one of
  54  *      the licenses at a time.
  55  *
  56  *  Paul Hsieh derivative license
  57  *
  58  *      The derivative content includes raw computer source code, ideas,
  59  *      opinions, and excerpts whose original source is covered under
  60  *      another license and transformations of such derivatives.
  61  *      Note that mere excerpts by themselves (with the exception of raw
  62  *      source code) are not considered derivative works under this license.
  63  *      Use and redistribution is limited to the following conditions:
  64  *
  65  *      One may not create a derivative work which, in any way, violates the
  66  *      Paul Hsieh exposition license described above on the original content.
  67  *
  68  *      One may not apply a license to a derivative work that precludes anyone
  69  *      else from using and redistributing derivative content.
  70  *
  71  *      One may not attribute any derivative content to authors not involved
  72  *      in the creation of the content, though an attribution to the author
  73  *      is not necessary.
  74  *
  75  *  Paul Hsieh exposition license
  76  *
  77  *      The content of all text, figures, tables and displayed layout is
  78  *      copyrighted by its author and owner Paul Hsieh unless specifically
  79  *      denoted otherwise. Redistribution is limited to the following conditions:
  80  *
  81  *      The redistributor must fully attribute the content's authorship and
  82  *      make a good faith effort to cite the original location of the original
  83  *      content.
  84  *
  85  *      The content may not be modified via excerpt or otherwise with the
  86  *      exception of additional citations such as described above without prior
  87  *      consent of Paul Hsieh.
  88  *
  89  *      The content may not be subject to a change in license without prior
  90  *      consent of Paul Hsieh.
  91  *
  92  *      The content may be used for commercial purposes.
  93  */
  94
  95 #if (defined(__GNUC__) && defined(__i386__)) || defined(_MSC_VER)
  96 /*
  97  * Unalligned loads are faster if we can do them, otherwise fall back
  98  * to safer version below.
  99  */
 100 #   define load16(D) (*((const uint16_t*)(D)))
 101 #else
 102 #   define load16(D) ((((uint32_t)(((const uint8_t*)(D))[1])) << 8) + \
 103                         (uint32_t)(((const uint8_t*)(D))[0]))
 104 #endif
 105 unsigned int inline typedef_hash(const char *data) {
 106         uint32_t hash = strlen(data);
 107         uint32_t size = hash;
 108         uint32_t temp = 0;
 109
 110         int last;
 111         if (size <= 0|| data == NULL)
 112                 return -1;
 113
 114         last   = size & 3;
 115         size >>= 2;
 116
 117         /* main loop */
 118         for (;size > 0; size--) {
 119                 hash += (load16(data));
 120                 temp  = (load16(data+2) << 11) ^ hash;
 121                 hash  = (hash << 16) ^ temp;
 122                 data += sizeof(uint16_t) << 1;
 123                 hash += hash >> 11;
 124         }
 125
 126         /* ends */
 127         switch (last) {
 128                 case 3:
 129                         hash += load16(data);
 130                         hash ^= hash << 16;
 131                         hash ^= ((signed char)data[sizeof(uint16_t)]) << 8;
 132                         hash += hash >> 11;
 133                         break;
 134                 case 2:
 135                         hash += load16(data);
 136                         hash ^= hash << 11;
 137                         hash += hash >> 17;
 138                         break;
 139                 case 1:
 140                         hash += (signed char)*data;
 141                         hash ^= hash << 10;
 142                         hash += hash >> 1;
 143                         break;
 144         }
 145
 146         /* force avalanching of final 127 bits */
 147         hash ^= hash << 3;
 148         hash += hash >> 5;
 149         hash ^= hash << 4;
 150         hash += hash >> 17;
 151         hash ^= hash << 25;
 152         hash += hash >> 6;
 153
 154         return hash % 1024;
 155 }
 156
 157 typedef_node *typedef_find(const char *s) {
 158         unsigned int  hash = typedef_hash(s);
 159         typedef_node *find = typedef_table[hash];
 160         return find;
 161 }
 162
 163 int typedef_add(const char *from, const char *to) {
 164         unsigned int  hash = typedef_hash(to);
 165         typedef_node *find = typedef_table[hash];
 166         if (find)
 167                 return error(ERROR_PARSE, "typedef for %s already exists\n", to);
 168
 169         /* check if the type exists first */
 170         if (strncmp(from, "void",   sizeof("void"))   == 0 ||
 171             strncmp(from, "string", sizeof("string")) == 0 ||
 172             strncmp(from, "float",  sizeof("float"))  == 0 ||
 173             strncmp(from, "vector", sizeof("vector")) == 0 ||
 174             strncmp(from, "entity", sizeof("entity")) == 0) {
 175
 176                 typedef_table[hash]       = mem_a(sizeof(typedef_node));
 177                 typedef_table[hash]->name = strdup(from);
 178                 return -100;
 179         } else {
 180                 /* search the typedefs for it (typedef-a-typedef?) */
 181                 typedef_node *find = typedef_table[typedef_hash(from)];
 182                 if (find) {
 183                         typedef_table[hash]       = mem_a(sizeof(typedef_node));
 184                         typedef_table[hash]->name = strdup(find->name);
 185                         return -100;
 186                 }
 187         }
 188         return error(ERROR_PARSE, "cannot typedef %s (not a type)\n", from);
 189 }