NotZed's Source Code Repository - panamaz/blob - src/list.h

   1
   2 /*
   3   Copyright (C) 2010,2019,2020 Michael Zucchi
   4
   5    This program is free software: you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License
   7    as published by the Free Software Foundation, either version 3 of
   8    the License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public
  16    License along with this program. If not, see
  17    <http://www.gnu.org/licenses/>.
  18 */
  19
  20 /* **********************************************************************
  21  * a simple ordered hash/list/stack
  22  */
  23
  24 struct node;
  25
  26 struct list {
  27         struct node *head;
  28         struct node *tail;
  29 };
  30
  31 struct node {
  32         // list/stack next
  33         struct node *next;
  34         // hash chain link/stack prev
  35         struct node *link;
  36
  37         // metadata
  38         struct list list;
  39
  40         // payload
  41         tree type;
  42
  43         char name[];
  44 };
  45
  46 struct hash {
  47         struct node *table[64];
  48         struct list list;
  49 };
  50
  51 static struct node *node_alloc(tree type, const char *name) {
  52         struct node *n = (struct node *)xmalloc(sizeof(struct node) + (name ? strlen(name) + 1 : 1));
  53
  54         n->next = NULL;
  55         n->link = NULL;
  56         n->type = type;
  57         n->list.head = NULL;
  58         n->list.tail = NULL;
  59
  60         if (name)
  61                 strcpy(n->name, name);
  62         else
  63                 n->name[0] = 0;
  64
  65         return n;
  66 }
  67
  68 static void stack_push(struct list *stack, struct node *node) {
  69         if (stack->head) {
  70                 stack->head->link = node;
  71                 node->next = stack->head;
  72                 stack->head = node;
  73         } else {
  74                 node->next = NULL;
  75                 stack->head = node;
  76                 stack->tail = node;
  77         }
  78 }
  79
  80 static struct node *stack_pull(struct list *stack) {
  81         struct node *n = stack->head;
  82
  83         if (n) {
  84                 stack->head = n->next;
  85                 if (stack->head)
  86                         stack->head->link = NULL;
  87                 else
  88                         stack->tail = NULL;
  89         }
  90
  91         return n;
  92 }
  93
  94 static unsigned int ez_hash_string(const char *s) {
  95         unsigned int hash = 5381;
  96
  97         while (*s)
  98                 //hash = (*s++) + (hash << 5) + hash;
  99                 hash = hash * 33 + (*s++);
 100
 101         return hash;
 102 }
 103
 104 static void list_add(struct list *list, struct node *node) {
 105         node->next = NULL;
 106         if (list->head) {
 107                 list->tail->next = node;
 108                 list->tail = node;
 109         } else {
 110                 list->head = node;
 111                 list->tail = node;
 112         }
 113 }
 114
 115 static struct node *list_remhead(struct list *list) {
 116         struct node *node = list->head;
 117
 118         if (node && (list->head = node->next) == NULL)
 119                 list->tail = NULL;
 120
 121         return node;
 122 }
 123
 124 static void hash_put(struct hash *hash, struct node *node) {
 125         int code = ez_hash_string(node->name) & 63;
 126
 127         list_add(&hash->list, node);
 128
 129         node->link = hash->table[code];
 130         hash->table[code] = node;
 131 }
 132
 133 struct node *hash_lookup(struct hash *hash, const char *name) {
 134         int code = ez_hash_string(name) & 63;
 135
 136         for (struct node *n = hash->table[code]; n; n=n->link) {
 137                 if (strcmp(n->name, name) == 0)
 138                         return n;
 139         }
 140
 141         return NULL;
 142 }
 143
 144 static void hash_put_bytype(struct hash *hash, struct node *node) {
 145         int code = (int)((uintptr_t)node->type >> 5) & 63;
 146
 147         list_add(&hash->list, node);
 148
 149         node->link = hash->table[code];
 150         hash->table[code] = node;
 151 }
 152
 153 struct node *hash_lookup_bytype(struct hash *hash, tree type) {
 154         int code = (int)((uintptr_t)type >> 5) & 63;
 155
 156         for (struct node *n = hash->table[code]; n; n=n->link) {
 157                 if (n->type == type)
 158                         return n;
 159         }
 160
 161         return NULL;
 162 }
 163
 164 /* simple growable c buffer */
 165 struct buffer {
 166         size_t size;
 167         size_t pos;
 168         char *data;
 169 };
 170
 171 static void buffer_init(struct buffer *b, size_t size) {
 172         b->size = size;
 173         b->pos = 0;
 174         b->data = (char *)xmalloc(size);
 175 }
 176
 177 static void buffer_room(struct buffer *b, size_t len) {
 178         if (b->pos + len >= b->size) {
 179                 do {
 180                         b->size *= 2;
 181                 } while (b->pos + len >= b->size);
 182
 183                 b->data = (char *)xrealloc(b->data, b->size);
 184         }
 185 }
 186
 187 static void buffer_add(struct buffer *b, const char *v) {
 188         size_t len = strlen(v);
 189
 190         buffer_room(b, len);
 191         strcpy(b->data + b->pos, v);
 192         b->pos += len;
 193 }