Remove some internal dumps.
[panamaz] / 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 }