1 /**********************************************************************
2 table_util.c
3 **********************************************************************
4
5 table_util - Data table routines.
6 Copyright ©2000-2003, Stewart Adcock <stewart@linux-domain.com>
7 All rights reserved.
8
9 The latest version of this program should be available at:
10 http://gaul.sourceforge.net/
11
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version. Alternatively, if your project
16 is incompatible with the GPL, I will probably agree to requests
17 for permission to use the terms of any other license.
18
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY WHATSOEVER.
21
22 A full copy of the GNU General Public License should be in the file
23 "COPYING" provided with this distribution; if not, see:
24 http://www.gnu.org/
25
26 **********************************************************************
27
28 Synopsis: Table data structure. (basically a growable table)
29
30 *** THIS IS NOT A HASH TABLE IMPLEMENTATION! ***
31
32 Thread-safe.
33
34 To do: Add table_compress().
35 Need to add more safety checks and create 'fast' versions.
36 Document and comment!
37
38 Compile test program with something like:
39 gcc table.c -DTABLE_COMPILE_MAIN `glib-config --cflags` -I..
40 -DVERSION_STRING=NULL -lmethods -lglib -L.
41
42 **********************************************************************/
43
44 #include "gaul/table_util.h"
45
_next_pow2(unsigned int num)46 static unsigned int _next_pow2(unsigned int num)
47 {
48 unsigned int n = 1;
49
50 num++;
51
52 while(n < num) n <<= 1;
53
54 return n;
55 }
56
57
table_ensure_size(TableStruct * table,unsigned int size)58 static boolean table_ensure_size(TableStruct *table, unsigned int size)
59 {
60 unsigned int i;
61
62 if(table->size < size)
63 {
64 size = _next_pow2(size);
65 table->data = s_realloc(table->data, sizeof(vpointer)*size);
66 table->unused = s_realloc(table->unused, sizeof(unsigned int)*size);
67
68 for (i=table->size; i<size; i++)
69 table->data[i]=NULL;
70
71 table->size = size;
72
73 /*
74 printf("DEBUG: Table size is now %d\n", size);
75 */
76 }
77
78 return TRUE;
79 }
80
81
table_new(void)82 TableStruct *table_new(void)
83 {
84 TableStruct *table;
85
86 table = s_malloc(sizeof(TableStruct));
87
88 table->data = NULL;
89 table->unused = NULL;
90 /*
91 table->deallocate = NULL;
92 */
93 table->size = 0;
94 table->numfree = 0;
95 table->next = 0;
96
97 return (TableStruct*) table;
98 }
99
100
table_destroy(TableStruct * table)101 void table_destroy(TableStruct *table)
102 {
103 /*
104 if(table->deallocate)
105 s_free(table->data);
106 */
107 if (table->data) s_free(table->data);
108 if (table->unused) s_free(table->unused);
109
110 s_free(table);
111
112 return;
113 }
114
115
table_set_size(TableStruct * table,unsigned int size)116 boolean table_set_size(TableStruct *table, unsigned int size)
117 {
118
119 if(table->size < size)
120 {
121 return table_ensure_size(table, size);
122 }
123 else
124 {
125 printf("FIXME: Maybe need to shrink table if possible.");
126 }
127
128 return TRUE;
129 }
130
131
132 /* Returns data removed, NULL otherwise. */
table_remove_index(TableStruct * table,unsigned int index)133 vpointer table_remove_index(TableStruct *table, unsigned int index)
134 {
135 vpointer data;
136
137 if (!table) die("NULL pointer to TableStruct passed.");
138
139 /* if (index < 0 || index >= table->next) die("Invalid index passed."); */
140 if (index >= table->next) die("Invalid index passed.");
141
142 data = table->data[index];
143
144 /* Is this index used? Do nothing if not. */
145 if (data)
146 {
147 /* Add index to unused list. */
148 table->unused[table->numfree]=index;
149 table->numfree++;
150 table->data[index] = NULL;
151 }
152 else
153 {
154 printf("WARNING: Trying to remove unused item.\n");
155 }
156
157 return data;
158 }
159
160
161 /* Returns index of data removed, TABLE_ERROR_INDEX otherwise. */
table_remove_data(TableStruct * table,vpointer data)162 unsigned int table_remove_data(TableStruct *table, vpointer data)
163 {
164 unsigned int index=0;
165
166 if (!table) die("NULL pointer to TableStruct passed.");
167 if (!data) die("NULL pointer to user data passed.");
168
169 while ( index < table->next)
170 {
171 if ( table->data[index] == data )
172 { /* Data found in table */
173 /* Add index to unused list. */
174 table->unused[table->numfree]=index;
175 table->numfree++;
176 table->data[index] = NULL;
177 return index;
178 }
179 index++;
180 }
181
182 printf("WARNING: Trying to remove unused item.\n");
183
184 return TABLE_ERROR_INDEX;
185 }
186
187
188 /* Count of items removed, TABLE_ERROR_INDEX otherwise. */
table_remove_data_all(TableStruct * table,vpointer data)189 unsigned int table_remove_data_all(TableStruct *table, vpointer data)
190 {
191 unsigned int index=0;
192 unsigned int count=0;
193
194 if (!table) die("NULL pointer to TableStruct passed.");
195 if (!data) die("NULL pointer to user data passed.");
196
197 while ( index < table->next)
198 {
199 if ( table->data[index] == data )
200 { /* Data found in table */
201 /* Add index to unused list. */
202 table->unused[table->numfree]=index;
203 table->numfree++;
204 table->data[index] = NULL;
205 count++;
206 }
207 index++;
208 }
209
210 return count;
211 }
212
213
table_get_data(TableStruct * table,unsigned int index)214 vpointer table_get_data(TableStruct *table, unsigned int index)
215 {
216
217 if (!table) die("NULL pointer to TableStruct passed.");
218
219 /* if (index < 0 || index >= table->next) dief("Invalid index (%d) passed.", index);*/
220 if (index >= table->next) dief("Invalid index (%d) passed.", index);
221
222 return table->data[index];
223 }
224
225
226 /* Return array of all stored pointers. Caller must deallocate the array. */
table_get_data_all(TableStruct * table)227 vpointer *table_get_data_all(TableStruct *table)
228 {
229 unsigned int index=0;
230 unsigned int count=0;
231 vpointer *data; /* Array of data to return. */
232
233 if (!table) die("NULL pointer to TableStruct passed.");
234
235 data = (vpointer*) s_malloc(sizeof(vpointer)*(table->size-table->numfree));
236
237 while ( index < table->next)
238 {
239 if (table->data[index] != NULL)
240 data[count++] = table->data[index];
241 index++;
242 }
243
244 return data;
245 }
246
247
248 /* Return array of all used indices. Caller must deallocate the array. */
table_get_index_all(TableStruct * table)249 unsigned int *table_get_index_all(TableStruct *table)
250 {
251 unsigned int index=0;
252 unsigned int count=0;
253 unsigned int *data; /* Array of indices to return. */
254
255 if (!table) die("NULL pointer to TableStruct passed.");
256
257 data = (unsigned int*) s_malloc(sizeof(vpointer)*(table->size-table->numfree));
258
259 while ( index < table->next)
260 {
261 if (table->data[index] != NULL)
262 data[count++] = index;
263 index++;
264 }
265
266 return data;
267 }
268
269
270 /* Returns the index for given data, or TABLE_ERROR_INDEX on failure. */
table_lookup_index(TableStruct * table,vpointer data)271 unsigned int table_lookup_index(TableStruct *table, vpointer data)
272 {
273 unsigned int index=0;
274
275 if (!table) die("NULL pointer to TableStruct passed.");
276 if (!data) die("NULL vpointer data passed.");
277
278 while ( index < table->next )
279 {
280 if (table->data[index] == data) return index;
281 index++;
282 }
283
284 return TABLE_ERROR_INDEX;
285 }
286
287
table_add(TableStruct * table,vpointer data)288 unsigned int table_add(TableStruct *table, vpointer data)
289 {
290 unsigned int index;
291
292 if (!table) die("NULL pointer to TableStruct passed.");
293 if (!data) die("NULL vpointer data passed.");
294
295 if (table->numfree>0)
296 { /* Re-use some old indices. */
297 table->numfree--;
298 table->data[table->unused[table->numfree]]=data;
299 return table->unused[table->numfree];
300 }
301
302 /* Must append to end of array. */
303 index = table->next;
304 table->next++;
305 table_ensure_size(table, table->next);
306 table->data[index] = data;
307
308 return index;
309 }
310
311
table_count_items(TableStruct * table)312 unsigned int table_count_items(TableStruct *table)
313 {
314 if (!table) die("NULL pointer to TableStruct passed.");
315
316 return (table->next-table->numfree);
317 }
318
319
table_diagnostics(void)320 void table_diagnostics(void)
321 {
322 printf("=== Table diagnostics ========================================\n");
323 printf("Version: %s\n", GA_VERSION_STRING);
324 printf("Build date: %s\n", GA_BUILD_DATE_STRING);
325 printf("Compilation machine characteristics:\n%s\n", GA_UNAME_STRING);
326
327 printf("--------------------------------------------------------------\n");
328 printf("TABLE_ERROR_INDEX: %u\n", TABLE_ERROR_INDEX);
329
330 printf("--------------------------------------------------------------\n");
331 printf("structure sizeof\n");
332 printf("TableStruct %lu\n", (unsigned long) sizeof(TableStruct));
333 printf("==============================================================\n");
334
335 return;
336 }
337
338
339 #ifdef TABLE_COMPILE_MAIN
main(int argc,char * argv[])340 int main(int argc, char *argv[])
341 #else
342 boolean table_test(void)
343 #endif
344 {
345 /*
346 int i, j;
347 */
348 TableStruct *table;
349
350 printf("Testing my table routines.\n");
351 printf("FIXME: Actually add some tests!\n");
352
353 table = table_new();
354 table_set_size(table, 200);
355
356 /*
357 vpointer table_remove_index(TableStruct *table, unsigned int index);
358 vpointer table_get_data(TableStruct *table, unsigned int index);
359 unsigned int table_add(TableStruct *table, vpointer data);
360 */
361
362 table_destroy(table);
363
364 #ifdef TABLE_COMPILE_MAIN
365 exit(EXIT_SUCCESS);
366 #else
367 return TRUE;
368 #endif
369 }
370