1 /*
2 * Copyright (C) 2000,2001 Ross Combs (rocombs@cs.nmsu.edu)
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18 #define HASHTABLE_INTERNAL_ACCESS
19 #include "common/setup_before.h"
20 #ifdef HAVE_STDDEF_H
21 # include <stddef.h>
22 #else
23 # ifndef NULL
24 # define NULL ((void *)0)
25 # endif
26 #endif
27 #ifdef STDC_HEADERS
28 # include <stdlib.h>
29 #else
30 # ifdef HAVE_MALLOC_H
31 # include <malloc.h>
32 # endif
33 #endif
34 #include "common/eventlog.h"
35 #include "common/hashtable.h"
36 #include "common/xalloc.h"
37 #include "common/setup_after.h"
38
39
40 static int nodata; /* if data points to this, then the entry was actually deleted */
41
42
43 static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row);
44
45
hashtable_entry_export(t_internentry * entry,t_hashtable const * hashtable,unsigned int row)46 static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row)
47 {
48 t_entry * temp;
49
50 if (!entry)
51 {
52 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
53 return NULL;
54 }
55 if (!hashtable)
56 {
57 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
58 return NULL;
59 }
60 if (row>=hashtable->num_rows)
61 {
62 eventlog(eventlog_level_error,__FUNCTION__,"got bad row %u (max %u)",row,hashtable->num_rows-1);
63 return NULL;
64 }
65
66 temp = xmalloc(sizeof(t_entry));
67 temp->row = row;
68 temp->real = entry;
69 temp->hashtable = hashtable;
70
71 return temp;
72 }
73
74
hashtable_create(unsigned int num_rows)75 extern t_hashtable * hashtable_create(unsigned int num_rows)
76 {
77 t_hashtable * new;
78 unsigned int i;
79
80 if (num_rows<1)
81 {
82 eventlog(eventlog_level_error,__FUNCTION__,"num_rows must be at least 1");
83 return NULL;
84 }
85
86 new = xmalloc(sizeof(t_hashtable));
87 new->rows = xmalloc(sizeof(t_internentry *)*num_rows);
88 new->num_rows = num_rows;
89 new->len = 0;
90 for (i=0; i<num_rows; i++)
91 new->rows[i] = NULL;
92
93 return new;
94 }
95
96
hashtable_destroy(t_hashtable * hashtable)97 extern int hashtable_destroy(t_hashtable * hashtable)
98 {
99 unsigned int i;
100
101 if (!hashtable)
102 {
103 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
104 return -1;
105 }
106
107 hashtable_purge(hashtable);
108 for (i=0; i<hashtable->num_rows; i++)
109 if (hashtable->rows[i])
110 eventlog(eventlog_level_error,__FUNCTION__,"got non-empty hashtable");
111
112 xfree(hashtable->rows);
113 xfree(hashtable);
114
115 return 0;
116 }
117
118
hashtable_purge(t_hashtable * hashtable)119 extern int hashtable_purge(t_hashtable * hashtable)
120 {
121 unsigned int row;
122 t_internentry * curr;
123 t_internentry * head;
124 t_internentry * next;
125 t_internentry * * change;
126
127 if (!hashtable)
128 {
129 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
130 return -1;
131 }
132
133 #ifdef HASHTABLE_DEBUG
134 hashtable_check(hashtable);
135 #endif
136
137 for (row=0; row<hashtable->num_rows; row++)
138 {
139 head = NULL;
140 change = NULL;
141 for (curr=hashtable->rows[row]; curr; curr=next)
142 {
143 next = curr->next;
144 if (curr->data==&nodata)
145 {
146 if (change)
147 *change = next;
148 xfree(curr);
149 }
150 else
151 {
152 if (!head)
153 head = curr;
154 change = &curr->next;
155 }
156 }
157 hashtable->rows[row] = head;
158 }
159
160 return 0;
161 }
162
163
hashtable_check(t_hashtable const * hashtable)164 extern int hashtable_check(t_hashtable const * hashtable)
165 {
166 unsigned int emptycnt;
167 unsigned int validcnt;
168 unsigned int row;
169 unsigned int temp;
170 t_internentry const * tail;
171 t_internentry const * curr;
172
173 if (!hashtable)
174 {
175 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
176 return -1;
177 }
178 if (hashtable->num_rows<1)
179 {
180 eventlog(eventlog_level_error,__FUNCTION__,"num_rows=%u",hashtable->num_rows);
181 return -1;
182 }
183 if (!hashtable->rows)
184 {
185 eventlog(eventlog_level_error,__FUNCTION__,"hashtable->rows is NULL");
186 return -1;
187 }
188
189 emptycnt=validcnt = 0;
190 for (row=0; row<hashtable->num_rows; row++)
191 {
192 tail = NULL;
193 for (curr=hashtable->rows[row]; curr; curr=curr->next)
194 {
195 if (tail)
196 {
197 if (curr==tail) /* tail is currently the previous node */
198 {
199 eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==prev==%p)",row,curr);
200 return -1;
201 }
202 if (curr->next==tail)
203 {
204 eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr->next==prev==%p)",row,curr);
205 return -1;
206 }
207 for (temp=0; temp<hashtable->num_rows; temp++)
208 if (curr==hashtable->rows[temp])
209 {
210 eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==rows[%u]==%p)",row,temp,curr);
211 return -1;
212 }
213 }
214 if (curr->data==&nodata)
215 emptycnt++;
216 else
217 validcnt++;
218 tail = curr;
219 }
220 }
221
222 if (emptycnt>10 && emptycnt>validcnt+5) /* arbitrary heuristic to detect missing list_purge() cal
223 ls */
224 eventlog(eventlog_level_warn,__FUNCTION__,"emptycnt=%u but validcnt=%u",emptycnt,validcnt);
225 if (hashtable->len!=validcnt)
226 {
227 eventlog(eventlog_level_error,__FUNCTION__,"hashtable->len=%u but validcnt=%u",hashtable->len,validcnt);
228 return -1;
229 }
230
231 return 0;
232 }
233
234
hashtable_get_length(t_hashtable const * hashtable)235 extern unsigned int hashtable_get_length(t_hashtable const * hashtable)
236 {
237 if (!hashtable)
238 {
239 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
240 return 0;
241 }
242
243 return hashtable->len;
244 }
245
246
hashtable_insert_data(t_hashtable * hashtable,void * data,unsigned int hash)247 extern int hashtable_insert_data(t_hashtable * hashtable, void * data, unsigned int hash)
248 {
249 unsigned int row;
250 t_internentry * entry;
251
252 if (!hashtable)
253 {
254 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
255 return -1;
256 }
257
258 entry = xmalloc(sizeof(t_internentry));
259 entry->data = data;
260
261 row = hash%hashtable->num_rows;
262 entry->next = hashtable->rows[row];
263 hashtable->rows[row] = entry;
264 hashtable->len++;
265
266 return 0;
267 }
268
269
hashtable_get_entry_by_data(t_hashtable const * hashtable,void const * data,unsigned int hash)270 extern t_entry * hashtable_get_entry_by_data(t_hashtable const * hashtable, void const * data, unsigned int hash)
271 {
272 unsigned int row;
273 t_internentry * curr;
274
275 if (!hashtable)
276 {
277 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
278 return NULL;
279 }
280
281 row = hash%hashtable->num_rows;
282 for (curr=hashtable->rows[row]; curr; curr=curr->next)
283 if (curr->data==data)
284 return hashtable_entry_export(curr,hashtable,row);
285
286 return NULL;
287 }
288
289
hashtable_get_entry_by_data_const(t_hashtable const * hashtable,void const * data,unsigned int hash)290 extern t_entry const * hashtable_get_entry_by_data_const(t_hashtable const * hashtable, void const * data, unsigned int hash)
291 {
292 unsigned int row;
293 t_internentry * curr;
294
295 if (!hashtable)
296 {
297 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
298 return NULL;
299 }
300
301 row = hash%hashtable->num_rows;
302 for (curr=hashtable->rows[row]; curr; curr=curr->next)
303 if (curr->data==data)
304 return hashtable_entry_export(curr,hashtable,row);
305
306 return NULL;
307 }
308
309
hashtable_remove_entry(t_hashtable * hashtable,t_entry * entry)310 extern int hashtable_remove_entry(t_hashtable * hashtable, t_entry * entry)
311 {
312 if (!hashtable)
313 {
314 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
315 return -1;
316 }
317 if (!entry)
318 {
319 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
320 return -1;
321 }
322 if (!entry->real)
323 {
324 eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
325 return -1;
326 }
327 if (entry->real->data==&nodata)
328 {
329 eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
330 return -1;
331 }
332
333 entry->real->data = &nodata;
334 hashtable->len--;
335
336 return 0;
337 }
338
339
hashtable_remove_data(t_hashtable * hashtable,void const * data,unsigned int hash)340 extern int hashtable_remove_data(t_hashtable * hashtable, void const * data, unsigned int hash)
341 {
342 t_entry * entry;
343 int retval;
344
345 if (!hashtable)
346 {
347 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
348 return -1;
349 }
350
351 if (!(entry = hashtable_get_entry_by_data(hashtable,data,hash)))
352 return -1;
353
354 retval = hashtable_remove_entry(hashtable,entry);
355
356 hashtable_entry_release(entry);
357
358 return retval;
359 }
360
361
entry_get_data(t_entry const * entry)362 extern void * entry_get_data(t_entry const * entry)
363 {
364 if (!entry)
365 {
366 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
367 return NULL;
368 }
369 if (!entry->real)
370 {
371 eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
372 return NULL;
373 }
374 if (entry->real->data==&nodata)
375 {
376 eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
377 return NULL;
378 }
379
380 return entry->real->data;
381 }
382
383
hashtable_get_data_by_pos(t_hashtable const * hashtable,unsigned int pos)384 extern void * hashtable_get_data_by_pos(t_hashtable const * hashtable, unsigned int pos)
385 {
386 t_internentry const * curr;
387 unsigned int row;
388 unsigned int len;
389
390 if (!hashtable)
391 {
392 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
393 return NULL;
394 }
395
396 len = 0;
397 row = 0;
398 curr = NULL;
399 for (;;)
400 {
401 if (!curr)
402 {
403 if (row>=hashtable->num_rows)
404 break;
405 curr = hashtable->rows[row++];
406 continue;
407 }
408 if (curr->data!=&nodata && len++==pos)
409 return curr->data;
410 curr = curr->next;
411 }
412
413 eventlog(eventlog_level_error,__FUNCTION__,"requested position %u but len=%u",pos,len);
414 return NULL;
415 }
416
417
418 #ifdef HASHTABLE_DEBUG
hashtable_get_first_real(t_hashtable const * hashtable,char const * fn,unsigned int ln)419 extern t_entry * hashtable_get_first_real(t_hashtable const * hashtable, char const * fn, unsigned int ln)
420 #else
421 extern t_entry * hashtable_get_first(t_hashtable const * hashtable)
422 #endif
423 {
424 unsigned int row;
425 t_internentry * curr;
426
427 if (!hashtable)
428 {
429 #ifdef HASHTABLE_DEBUG
430 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
431 #else
432 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
433 #endif
434 return NULL;
435 }
436
437 for (row=0; row<hashtable->num_rows; row++)
438 for (curr=hashtable->rows[row]; curr; curr=curr->next)
439 if (curr->data!=&nodata)
440 return hashtable_entry_export(curr,hashtable,row);
441
442 return NULL;
443 }
444
445
entry_get_next(t_entry * entry)446 extern t_entry * entry_get_next(t_entry * entry)
447 {
448 t_hashtable const * hashtable;
449 unsigned int row;
450 t_internentry * curr;
451
452 if (!entry)
453 {
454 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
455 return NULL;
456 }
457
458 hashtable = entry->hashtable;
459
460 for (curr=entry->real->next; curr; curr=curr->next)
461 if (curr->data!=&nodata)
462 {
463 entry->real = curr;
464 return entry;
465 }
466
467 for (row=entry->row+1; row<hashtable->num_rows; row++)
468 for (curr=hashtable->rows[row]; curr; curr=curr->next)
469 if (curr->data!=&nodata)
470 {
471 entry->real = curr;
472 entry->row = row;
473 return entry;
474 }
475
476 hashtable_entry_release(entry);
477 return NULL;
478 }
479
480
481 #ifdef HASHTABLE_DEBUG
hashtable_get_first_matching_real(t_hashtable const * hashtable,unsigned int hash,char const * fn,unsigned int ln)482 extern t_entry * hashtable_get_first_matching_real(t_hashtable const * hashtable, unsigned int hash, char const * fn, unsigned int ln)
483 #else
484 extern t_entry * hashtable_get_first_matching(t_hashtable const * hashtable, unsigned int hash)
485 #endif
486 {
487 unsigned int row;
488 t_internentry * curr;
489
490 if (!hashtable)
491 {
492 #ifdef HASHTABLE_DEBUG
493 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
494 #else
495 eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
496 #endif
497 return NULL;
498 }
499
500 row = hash%hashtable->num_rows;
501 for (curr=hashtable->rows[row]; curr; curr=curr->next)
502 if (curr->data!=&nodata)
503 return hashtable_entry_export(curr,hashtable,row);
504
505 return NULL;
506 }
507
508
entry_get_next_matching(t_entry * entry)509 extern t_entry * entry_get_next_matching(t_entry * entry)
510 {
511 t_internentry * curr;
512
513 if (!entry)
514 {
515 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
516 return NULL;
517 }
518
519 for (curr=entry->real->next; curr; curr=curr->next)
520 if (curr->data!=&nodata)
521 {
522 entry->real = curr;
523 return entry;
524 }
525
526 hashtable_entry_release(entry);
527 return NULL;
528 }
529
530
hashtable_entry_release(t_entry * entry)531 extern int hashtable_entry_release(t_entry * entry)
532 {
533 if (!entry)
534 {
535 eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
536 return -1;
537 }
538 if (!entry->hashtable)
539 {
540 eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL hashtable");
541 return -1;
542 }
543 if (!entry->real)
544 {
545 eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL real pointer");
546 return -1;
547 }
548 if (entry->row>=entry->hashtable->num_rows)
549 {
550 eventlog(eventlog_level_error,__FUNCTION__,"entry has bad row %u (max %u)",entry->row,entry->hashtable->num_rows-1);
551 return -1;
552 }
553
554 #ifdef HASHTABLE_DEBUG
555 hashtable_check(entry->hashtable);
556 #endif
557 xfree(entry);
558 return 0;
559 }
560
561
hashtable_stats(t_hashtable * hashtable)562 extern int hashtable_stats(t_hashtable * hashtable)
563 {
564 unsigned int row;
565 t_internentry * curr;
566 unsigned int rcount, max, min;
567
568 if (!hashtable)
569 {
570 eventlog(eventlog_level_error, __FUNCTION__,"got NULL hashtable");
571 return -1;
572 }
573
574 #ifdef HASHTABLE_DEBUG
575 hashtable_check(hashtable);
576 #endif
577
578 max = 0;
579 min = hashtable->len;
580 for (row=0; row<hashtable->num_rows; row++)
581 {
582 rcount = 0;
583 for (curr=hashtable->rows[row]; curr; curr=curr->next)
584 if (curr->data!=&nodata) rcount++;
585 if (rcount > max) max = rcount;
586 if (rcount < min) min = rcount;
587 }
588
589 eventlog(eventlog_level_info, __FUNCTION__, "hashsize: %u min: %u max: %u avg: %.2f diff: %.2f%c", hashtable->num_rows, min, max, (float)(min + max)/2, (float)(max - min)/max*100, '%');
590 return 0;
591 }
592
593
594