panama tools and demos
[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 struct node {
24         // list/stack next
25         struct node *next;
26         // hash chain link/stack prev
27         struct node *link;
28
29         // payload
30         tree type;
31         char name[];
32 };
33
34 struct list {
35         struct node *head;
36         struct node *tail;
37 };
38
39 struct hash {
40         struct node *table[64];
41         struct list list;
42 };
43
44 static struct node *node_alloc(tree type, const char *name) {
45         struct node *n = (struct node *)xmalloc(sizeof(struct node) + (name ? strlen(name) + 1 : 1));
46
47         n->next = NULL;
48         n->link = NULL;
49         n->type = type;
50         if (name)
51                 strcpy(n->name, name);
52         else
53                 n->name[0] = 0;
54
55         return n;
56 }
57
58 static void stack_push(struct list *stack, struct node *node) {
59         if (stack->head) {
60                 stack->head->link = node;
61                 node->next = stack->head;
62                 stack->head = node;
63         } else {
64                 stack->head = node;
65                 stack->tail = node;
66         }
67 }
68
69 static struct node *stack_pull(struct list *stack) {
70         struct node *n = stack->head;
71
72         if (n) {
73                 stack->head = n->next;
74                 if (stack->head)
75                         stack->head->link = NULL;
76                 else
77                         stack->tail = NULL;
78         }
79
80         return n;
81 }
82
83 static unsigned int ez_hash_string(const char *s) {
84         unsigned int hash = 5381;
85
86         while (*s)
87                 //hash = (*s++) + (hash << 5) + hash;
88                 hash = hash * 33 + (*s++);
89
90         return hash;
91 }
92
93 static void list_add(struct list *list, struct node *node) {
94         if (list->head) {
95                 list->tail->next = node;
96                 list->tail = node;
97         } else {
98                 list->head = node;
99                 list->tail = node;
100         }
101 }
102
103 static void hash_put(struct hash *hash, struct node *node) {
104         int code = ez_hash_string(node->name) & 63;
105
106         list_add(&hash->list, node);
107
108         node->link = hash->table[code];
109         hash->table[code] = node;
110 }
111
112 struct node *hash_lookup(struct hash *hash, const char *name) {
113         int code = ez_hash_string(name) & 63;
114
115         for (struct node *n = hash->table[code]; n; n=n->link) {
116                 if (strcmp(n->name, name) == 0)
117                         return n;
118         }
119
120         return NULL;
121 }
122
123 /* simple growable c buffer */
124 struct buffer {
125         size_t size;
126         size_t pos;
127         char *data;
128 };
129
130 static void buffer_init(struct buffer *b, size_t size) {
131         b->size = size;
132         b->pos = 0;
133         b->data = (char *)xmalloc(size);
134 }
135
136 static void buffer_room(struct buffer *b, size_t len) {
137         if (b->pos + len >= b->size) {
138                 do {
139                         b->size *= 2;
140                 } while (b->pos + len >= b->size);
141
142                 b->data = (char *)xrealloc(b->data, b->size);
143         }
144 }
145
146 static void buffer_add(struct buffer *b, const char *v) {
147         size_t len = strlen(v);
148
149         buffer_room(b, len);
150         strcpy(b->data + b->pos, v);
151         b->pos += len;
152 }