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 "gmqcc.h"
  26
  27 /*
  28  * This implements a hashtable for typedef type keywords which end up
  29  * being translated to their full-expressed type.  This uses a singly
  30  * linked list with a fast hash function.
  31  */
  32 static typedef_node *typedef_table[1024];
  33
  34 void typedef_init() {
  35         int i;
  36         for(i = 0; i < sizeof(typedef_table)/sizeof(*typedef_table); i++)
  37                 typedef_table[i] = NULL;
  38 }
  39
  40 /*
  41  * Fast collisionless hashfunction based off of:
  42  * http://www.azillionmonkeys.com/qed/hash.html
  43  * By: Paul Hsieh
  44  *
  45  * The code is licensed under LGPL 2.1 or Paul
  46  * Hsieh's derivative license. Stated on his page
  47  * quote:
  48  *
  49  *      The LGPL 2.1 is not necessarily a more liberal license than my
  50  *      derivative license, but this additional licensing makes the code
  51  *      available to more developers. Note that this does not give you
  52  *      multi-licensing rights. You can only use the code under one of
  53  *      the licenses at a time.
  54  *
  55  *  Paul Hsieh derivative license
  56  *
  57  *      The derivative content includes raw computer source code, ideas,
  58  *      opinions, and excerpts whose original source is covered under
  59  *      another license and transformations of such derivatives.
  60  *      Note that mere excerpts by themselves (with the exception of raw
  61  *      source code) are not considered derivative works under this license.
  62  *      Use and redistribution is limited to the following conditions:
  63  *
  64  *      One may not create a derivative work which, in any way, violates the
  65  *      Paul Hsieh exposition license described above on the original content.
  66  *
  67  *      One may not apply a license to a derivative work that precludes anyone
  68  *      else from using and redistributing derivative content.
  69  *
  70  *      One may not attribute any derivative content to authors not involved
  71  *      in the creation of the content, though an attribution to the author
  72  *      is not necessary.
  73  *
  74  *      Paul Hsieh exposition license
  75  *
  76  *      The content of all text, figures, tables and displayed layout is
  77  *      copyrighted by its author and owner Paul Hsieh unless specifically
  78  *      denoted otherwise. Redistribution is limited to the following conditions:
  79  *
  80  *      The redistributor must fully attribute the content's authorship and
  81  *      make a good faith effort to cite the original location of the original
  82  *      content.
  83  *
  84  *      The content may not be modified via excerpt or otherwise with the
  85  *      exception of additional citations such as described above without prior
  86  *      consent of Paul Hsieh.
  87  *
  88  *      The content may not be subject to a change in license without prior
  89  *      consent of Paul Hsieh.
  90  *
  91  *      The content may be used for commercial purposes.
  92  */
  93
  94 #if (defined(__GNUC__) && defined(__i386__)) || defined(_MSC_VER)
  95 /*
  96  * Unalligned loads are faster if we can do them, otherwise fall back
  97  * to safer version below.
  98  */
  99 #       define load16(D) (*((const uint16_t*)(D)))
 100 #else
 101 #       define load16(D) ((((uint32_t)(((const uint8_t*)(D))[1])) << 8) + \
 102                         (uint32_t)(((const uint8_t*)(D))[0]))
 103 #endif
 104 unsigned int inline typedef_hash(const char *data) {
 105         uint32_t hash = strlen(data);
 106         uint32_t size = hash;
 107         uint32_t temp = 0;
 108
 109         int last;
 110         if (size <= 0|| data == NULL)
 111                 return -1;
 112
 113         last   = size & 3;
 114         size >>= 2;
 115
 116         /* main loop */
 117         for (;size > 0; size--) {
 118                 hash += (load16(data));
 119                 temp  = (load16(data+2) << 11) ^ hash;
 120                 hash  = (hash << 16) ^ temp;
 121                 data += sizeof(uint16_t) << 1;
 122                 hash += hash >> 11;
 123         }
 124
 125         /* ends */
 126         switch (last) {
 127                 case 3:
 128                         hash += load16(data);
 129                         hash ^= hash << 16;
 130                         hash ^= ((signed char)data[sizeof(uint16_t)]) << 8;
 131                         hash += hash >> 11;
 132                         break;
 133                 case 2:
 134                         hash += load16(data);
 135                         hash ^= hash << 11;
 136                         hash += hash >> 17;
 137                         break;
 138                 case 1:
 139                         hash += (signed char)*data;
 140                         hash ^= hash << 10;
 141                         hash += hash >> 1;
 142                         break;
 143         }
 144
 145         /* force avalanching of final 127 bits */
 146         hash ^= hash << 3;
 147         hash += hash >> 5;
 148         hash ^= hash << 4;
 149         hash += hash >> 17;
 150         hash ^= hash << 25;
 151         hash += hash >> 6;
 152
 153         return hash % 1024;
 154 }
 155
 156 typedef_node *typedef_find(const char *s) {
 157         unsigned int  hash = typedef_hash(s);
 158         typedef_node *find = typedef_table[hash];
 159         return find;
 160 }