1 /* set.c -- Set routines for Khepera
2 * Created: Wed Nov 9 13:31:24 1994 by faith@dict.org
3 * Copyright 1994-1997, 2002 Rickard E. Faith (faith@dict.org)
4 * Copyright 2002-2008 Aleksey Cheusov (vle@gmx.net)
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 * \section{Set Routines}
26 *
27 * \intro The set implementation is similar to the hash table
28 * implementation, except that the set object does not associate a |datum|
29 * with a |key|. For sets, keys are called elements. All of the hash
30 * table functions are supported, with the addition of a membership test
31 * and several set operations.
32 *
33 * The underlying data structure is a hash table of prime length, with
34 * self-organizing linked lists \cite[pp.~398--9]{faith:Knuth73c} used for
35 * collision resolution. The hash table automatically grows as necessary
36 * to preserve efficient access.
37 *
38 */
39
40 #include "maaP.h"
41
42 typedef struct bucket {
43 const void *elem;
44 unsigned long hash;
45 struct bucket *next;
46 } *bucketType;
47
48 typedef struct set {
49 #if MAA_MAGIC
50 int magic;
51 #endif
52 unsigned long prime;
53 unsigned long entries;
54 bucketType *buckets;
55 unsigned long resizings;
56 unsigned long retrievals;
57 unsigned long hits;
58 unsigned long misses;
59 unsigned long (*hash)(const void *);
60 int (*compare)(const void *, const void *);
61 int readonly;
62 } *setType;
63
_set_check(setType t,const char * function)64 static void _set_check(setType t, const char *function)
65 {
66 if (!t) err_internal(function, "set is null");
67 #if MAA_MAGIC
68 if (t->magic != SET_MAGIC)
69 err_internal(function,
70 "Bad magic: 0x%08x (should be 0x%08x)",
71 t->magic,
72 SET_MAGIC);
73 #endif
74 }
75
_set_create(unsigned long seed,set_HashFunction hash,set_CompareFunction compare)76 static set_Set _set_create(unsigned long seed,
77 set_HashFunction hash,
78 set_CompareFunction compare)
79 {
80 setType t;
81 unsigned long i;
82 unsigned long prime = prm_next_prime(seed);
83
84 t = xmalloc(sizeof(struct set));
85 #if MAA_MAGIC
86 t->magic = SET_MAGIC;
87 #endif
88 t->prime = prime;
89 t->entries = 0;
90 t->buckets = xmalloc(t->prime * sizeof(struct bucket));
91 t->resizings = 0;
92 t->retrievals = 0;
93 t->hits = 0;
94 t->misses = 0;
95 t->hash = hash ? hash : hsh_string_hash;
96 t->compare = compare ? compare : hsh_string_compare;
97 t->readonly = 0;
98
99 for (i = 0; i < t->prime; i++) t->buckets[i] = NULL;
100
101 return t;
102 }
103
104 /* \doc The |set_create| function initilizes a set object. Elements are
105 pointers to "void".
106
107 The internal representation of the set will grow automatically when an
108 insertion is performed and the table is more than half full.
109
110 The |hash| function should take a pointer to a |elem| and return an
111 "unsigned int". If |hash| is "NULL", then the |elem| is assumed to be a
112 pointer to a null-terminated string, and the function shown in
113 \grindref{fig:hshstringhash} will be used for |hash|.
114
115 The |compare| function should take a pair of pointers to elements and
116 return zero if the elements are the same and non-zero if they are
117 different. If |compare| is "NULL", then the elements are assumed to
118 point to null-terminated strings, and the |strcmp| function will be used
119 for |compare|.
120
121 Additionally, the |hsh_pointer_hash| and |hsh_pointer_compare| functions
122 are available and can be used to treat the \emph{value} of the "void"
123 pointer as the element. These functions are often useful for
124 maintaining sets of objects. */
125
set_create(set_HashFunction hash,set_CompareFunction compare)126 set_Set set_create(set_HashFunction hash, set_CompareFunction compare)
127 {
128 return _set_create(0, hash, compare);
129 }
130
set_get_hash(set_Set set)131 set_HashFunction set_get_hash(set_Set set)
132 {
133 setType t = (setType)set;
134
135 _set_check(t, __func__);
136 return t->hash;
137 }
138
set_get_compare(set_Set set)139 set_CompareFunction set_get_compare(set_Set set)
140 {
141 setType t = (setType)set;
142
143 _set_check(t, __func__);
144 return t->compare;
145 }
146
_set_destroy_buckets(set_Set set)147 static void _set_destroy_buckets(set_Set set)
148 {
149 unsigned long i;
150 setType t = (setType)set;
151
152 _set_check(t, __func__);
153 for (i = 0; i < t->prime; i++) {
154 bucketType b = t->buckets[i];
155
156 while (b) {
157 bucketType next = b->next;
158
159 xfree(b); /* terminal */
160 b = next;
161 }
162 }
163
164 xfree(t->buckets); /* terminal */
165 t->buckets = NULL;
166 }
167
_set_destroy_table(set_Set set)168 static void _set_destroy_table(set_Set set)
169 {
170 setType t = (setType)set;
171
172 _set_check(t, __func__);
173
174 #if MAA_MAGIC
175 t->magic = SET_MAGIC_FREED;
176 #endif
177 xfree(t); /* terminal */
178 }
179
180 /* \doc |set_destroy| frees all of the memory associated with the set
181 object.
182
183 The memory used by elements is \emph{not} freed---this memory is the
184 responsibility of the user. However, a call to |set_iterate| can be
185 used to free this memory \emph{immediately} before a call to
186 |set_destroy|. */
187
set_destroy(set_Set set)188 void set_destroy(set_Set set)
189 {
190 setType t = (setType)set;
191
192 _set_check(t, __func__);
193 if (t->readonly)
194 err_internal(__func__, "Attempt to destroy readonly set");
195 _set_destroy_buckets(set);
196 _set_destroy_table(set);
197 }
198
_set_insert(set_Set set,unsigned long hash,const void * elem)199 static void _set_insert(set_Set set, unsigned long hash, const void *elem)
200 {
201 setType t = (setType)set;
202 unsigned long h = hash % t->prime;
203 bucketType b;
204
205 _set_check(t, __func__);
206
207 b = xmalloc(sizeof(struct bucket));
208 b->hash = hash;
209 b->elem = elem;
210 b->next = NULL;
211
212 if (t->buckets[h]) b->next = t->buckets[h];
213 t->buckets[h] = b;
214 ++t->entries;
215 }
216
217 /* \doc |set_insert| inserts a new |elem| into the |set|. If the insertion
218 is successful, zero is returned. If the |elem| already exists, 1 is
219 returned.
220
221 If the internal representation of the set becomes more than half full,
222 its size is increased automatically. At present, this requires that all
223 of the element pointers are copied into a new set. Rehashing is not
224 required, however, since the hash values are stored for each element. */
225
set_insert(set_Set set,const void * elem)226 int set_insert(set_Set set, const void *elem)
227 {
228 setType t = (setType)set;
229 unsigned long hashValue = t->hash(elem);
230 unsigned long h;
231
232 _set_check(t, __func__);
233 if (t->readonly)
234 err_internal(__func__, "Attempt to insert into readonly set");
235
236 /* Keep table less than half full */
237 if (t->entries * 2 > t->prime) {
238 setType new = _set_create(t->prime * 3, t->hash, t->compare);
239 unsigned long i;
240
241 for (i = 0; i < t->prime; i++) {
242 if (t->buckets[i]) {
243 bucketType pt;
244
245 for (pt = t->buckets[i]; pt; pt = pt->next)
246 _set_insert(new, pt->hash, pt->elem);
247 }
248 }
249
250 /* fixup values */
251 _set_destroy_buckets(t);
252 t->prime = new->prime;
253 t->buckets = new->buckets;
254 _set_destroy_table(new);
255 ++t->resizings;
256 }
257
258 h = hashValue % t->prime;
259
260 if (t->buckets[h]) { /* Assert uniqueness */
261 bucketType pt;
262
263 for (pt = t->buckets[h]; pt; pt = pt->next)
264 if (!t->compare(pt->elem, elem)) return 1;
265 }
266
267 _set_insert(t, hashValue, elem);
268 return 0;
269 }
270
271 /* \doc |set_delete| removes an |elem| from the |set|. Zero is returned if
272 the |elem| was present. Otherwise, 1 is returned. */
273
set_delete(set_Set set,const void * elem)274 int set_delete(set_Set set, const void *elem)
275 {
276 setType t = (setType)set;
277 unsigned long h = t->hash(elem) % t->prime;
278
279 _set_check(t, __func__);
280 if (t->readonly)
281 err_internal(__func__, "Attempt to delete from readonly set");
282
283 if (t->buckets[h]) {
284 bucketType pt;
285 bucketType prev;
286
287 for (prev = NULL, pt = t->buckets[h]; pt; prev = pt, pt = pt->next)
288 if (!t->compare(pt->elem, elem)) {
289 --t->entries;
290
291 if (!prev) t->buckets[h] = pt->next;
292 else prev->next = pt->next;
293
294 xfree(pt);
295 return 0;
296 }
297 }
298
299 return 1;
300 }
301
302 /* \doc |set_member| returns 1 if |elem| is in |set|. Otherwise, zero is
303 returned. */
304
set_member(set_Set set,const void * elem)305 int set_member(set_Set set, const void *elem)
306 {
307 setType t = (setType)set;
308 unsigned long h = t->hash(elem) % t->prime;
309
310 _set_check(t, __func__);
311
312 ++t->retrievals;
313 if (t->buckets[h]) {
314 bucketType pt;
315 bucketType prev;
316
317 for (prev = NULL, pt = t->buckets[h]; pt; prev = pt, pt = pt->next)
318 if (!t->compare(pt->elem, elem)) {
319 if (!prev) {
320 ++t->hits;
321 } else if (!t->readonly) {
322 /* Self organize */
323 prev->next = pt->next;
324 pt->next = t->buckets[h];
325 t->buckets[h] = pt;
326 }
327 return 1;
328 }
329 }
330
331 ++t->misses;
332 return 0;
333 }
334
335 /* \doc |set_iterate| is used to iterate a function over every |elem| in
336 the |set|. The function, |iterator|, is passed each |elem|. If
337 |iterator| returns a non-zero value, the iterations stop, and
338 |set_iterate| returns. Note that the elements are in some arbitrary
339 order, and that this order may change between two successive calls to
340 |set_iterate|. */
341
set_iterate(set_Set set,int (* iterator)(const void * elem))342 int set_iterate(set_Set set,
343 int (*iterator)(const void *elem))
344 {
345 setType t = (setType)set;
346 unsigned long i;
347 int savedReadonly;
348
349 _set_check(t, __func__);
350
351 savedReadonly = t->readonly;
352 t->readonly = 1;
353
354 for (i = 0; i < t->prime; i++) {
355 if (t->buckets[i]) {
356 bucketType pt;
357
358 for (pt = t->buckets[i]; pt; pt = pt->next)
359 if (iterator(pt->elem)) {
360 t->readonly = savedReadonly;
361 return 1;
362 }
363 }
364 }
365
366 t->readonly = savedReadonly;
367 return 0;
368 }
369
370 /* \doc |set_iterate_arg| is used to iterate a function over every |elem|
371 in the |set|. The function, |iterator|, is passed each |elem|. If
372 |iterator| returns a non-zero value, the iterations stop, and
373 |set_iterate| returns. Note that the elements are in some arbitrary
374 order, and that this order may change between two successive calls to
375 |set_iterate|. */
376
set_iterate_arg(set_Set set,int (* iterator)(const void * elem,void * arg),void * arg)377 int set_iterate_arg(set_Set set,
378 int (*iterator)(const void *elem, void *arg),
379 void *arg)
380 {
381 setType t = (setType)set;
382 unsigned long i;
383 int savedReadonly;
384
385 _set_check(t, __func__);
386
387 savedReadonly = t->readonly;
388 t->readonly = 1;
389
390 for (i = 0; i < t->prime; i++) {
391 if (t->buckets[i]) {
392 bucketType pt;
393
394 for (pt = t->buckets[i]; pt; pt = pt->next)
395 if (iterator(pt->elem, arg)) {
396 t->readonly = savedReadonly;
397 return 1;
398 }
399 }
400 }
401
402 t->readonly = savedReadonly;
403 return 0;
404 }
405
406 /* \doc |set_init_position| returns a position marker for some arbitary
407 first element in the set. This marker can be used with
408 |set_next_position| and |set_get_position|. */
409
set_init_position(set_Set set)410 set_Position set_init_position(set_Set set)
411 {
412 setType t = (setType)set;
413 unsigned long i;
414
415 _set_check(t, __func__);
416 for (i = 0; i < t->prime; i++) if (t->buckets[i]) {
417 t->readonly = 1;
418 return t->buckets[i];
419 }
420 return NULL;
421 }
422
423 /* \doc |set_next_position| returns a position marker for the next element
424 in the set. Elements are in arbitrary order based on their positions in
425 the hash table. */
426
set_next_position(set_Set set,set_Position position)427 set_Position set_next_position(set_Set set, set_Position position)
428 {
429 setType t = (setType)set;
430 bucketType b = (bucketType)position;
431 unsigned long i;
432 unsigned long h;
433
434 _set_check(t, __func__);
435
436 if (!b) {
437 t->readonly = 0;
438 return NULL;
439 }
440
441 if (b->next) return b->next;
442
443 for (h = b->hash % t->prime, i = h + 1; i < t->prime; i++)
444 if (t->buckets[i]) return t->buckets[i];
445
446 t->readonly = 0;
447 return NULL;
448 }
449
450 /* \doc |set_get_position| returns the element associated with the
451 |position| marker, or "NULL" if there is no such element. */
452
set_get_position(set_Position position)453 void *set_get_position(set_Position position)
454 {
455 bucketType b = (bucketType)position;
456
457 if (!b) return NULL;
458 return __UNCONST(b->elem); /* Discard const */
459 }
460
461 /* \doc |set_readonly| sets the |readonly| flag for the |set| to |flag|.
462 |flag| should be 0 or 1. The value of the previous flag is returned.
463 When a set is marked as readonly, self-organization of the
464 bucket-overflow lists will not take place, and any attempt to modify the
465 list (e.g., insertion or deletion) will result in an error. */
466
set_readonly(set_Set set,int flag)467 int set_readonly(set_Set set, int flag)
468 {
469 setType t = (setType)set;
470 int current;
471
472 _set_check(t, __func__);
473
474 current = t->readonly;
475 t->readonly = flag;
476 return current;
477 }
478
479 /* \doc |set_add| returns |set1|, which now contains all of the elements
480 in |set1| and |set2|. Only pointers to elements are copied, \emph{not}
481 the data pointed (this has memory management implications). The |hash|
482 and |compare| functions must be identical for the two sets. |set2| is
483 not changed. */
484
set_add(set_Set set1,set_Set set2)485 set_Set set_add(set_Set set1, set_Set set2)
486 {
487 setType t1 = (setType)set1;
488 setType t2 = (setType)set2;
489 unsigned long i;
490
491 _set_check(t1, __func__);
492 _set_check(t2, __func__);
493
494 if (t1->hash != t2->hash)
495 err_fatal(__func__,
496 "Sets do not have identical hash functions");
497
498 if (t1->compare != t2->compare)
499 err_fatal(__func__,
500 "Sets do not have identical comparison functions");
501
502 for (i = 0; i < t2->prime; i++) {
503 if (t2->buckets[i]) {
504 bucketType pt;
505
506 for (pt = t2->buckets[i]; pt; pt = pt->next)
507 set_insert(set1, pt->elem);
508 }
509 }
510
511 return set1;
512 }
513
514 /* \doc |set_del| returns |set1|, which now contains all of the elements in
515 |set1| other than those in |set2|. Only pointers to elements are
516 copied, \emph{not} the data pointed (this has memory management
517 implications). The |hash| and |compare| functions must be identical for
518 the two sets. |set2| is not changed. */
519
set_del(set_Set set1,set_Set set2)520 set_Set set_del(set_Set set1, set_Set set2)
521 {
522 setType t1 = (setType)set1;
523 setType t2 = (setType)set2;
524 unsigned long i;
525
526 _set_check(t1, __func__);
527 _set_check(t2, __func__);
528
529 if (t1->hash != t2->hash)
530 err_fatal(__func__,
531 "Sets do not have identical hash functions");
532
533 if (t1->compare != t2->compare)
534 err_fatal(__func__,
535 "Sets do not have identical comparison functions");
536
537 for (i = 0; i < t2->prime; i++) {
538 if (t2->buckets[i]) {
539 bucketType pt;
540
541 for (pt = t2->buckets[i]; pt; pt = pt->next)
542 set_delete(set1, pt->elem);
543 }
544 }
545
546 return set1;
547 }
548
549 /* \doc |set_union| returns a new set which is the union of |set1| and
550 |set2|. Only pointers to elements are copied, \emph{not} the data
551 pointed (this has memory management implications). The |hash| and
552 |compare| functions must be identical for the two sets. */
553
set_union(set_Set set1,set_Set set2)554 set_Set set_union(set_Set set1, set_Set set2)
555 {
556 setType t1 = (setType)set1;
557 setType t2 = (setType)set2;
558 set_Set set;
559 unsigned long i;
560
561 _set_check(t1, __func__);
562 _set_check(t2, __func__);
563
564 if (t1->hash != t2->hash)
565 err_fatal(__func__,
566 "Sets do not have identical hash functions");
567
568 if (t1->compare != t2->compare)
569 err_fatal(__func__,
570 "Sets do not have identical comparison functions");
571
572 set = set_create(t1->hash, t1->compare);
573
574 for (i = 0; i < t1->prime; i++) {
575 if (t1->buckets[i]) {
576 bucketType pt;
577
578 for (pt = t1->buckets[i]; pt; pt = pt->next)
579 set_insert(set, pt->elem);
580 }
581 }
582
583 for (i = 0; i < t2->prime; i++) {
584 if (t2->buckets[i]) {
585 bucketType pt;
586
587 for (pt = t2->buckets[i]; pt; pt = pt->next)
588 set_insert(set, pt->elem);
589 }
590 }
591
592 return set;
593 }
594
595 /* \doc |set_inter| returns a new set which is the intersection of |set1|
596 and |set2|. Only pointers to elements are copied, \emph{not} the data
597 pointed (this has memory management implications). The |hash| and
598 |compare| functions must be identical for the two sets. */
599
set_inter(set_Set set1,set_Set set2)600 set_Set set_inter(set_Set set1, set_Set set2)
601 {
602 setType t1 = (setType)set1;
603 setType t2 = (setType)set2;
604 set_Set set;
605 unsigned long i;
606 int savedReadonly;
607
608 _set_check(t1, __func__);
609 _set_check(t2, __func__);
610
611 if (t1->hash != t2->hash)
612 err_fatal(__func__,
613 "Sets do not have identical hash functions");
614
615 if (t1->compare != t2->compare)
616 err_fatal(__func__,
617 "Sets do not have identical comparison functions");
618
619 set = set_create(t1->hash, t1->compare);
620
621 savedReadonly = t2->readonly;
622 t2->readonly = 1; /* save time on set_member */
623 for (i = 0; i < t1->prime; i++) {
624 if (t1->buckets[i]) {
625 bucketType pt;
626
627 for (pt = t1->buckets[i]; pt; pt = pt->next)
628 if (set_member(t2, pt->elem))
629 set_insert(set, pt->elem);
630 }
631 }
632 t2->readonly = savedReadonly;
633
634 return set;
635 }
636
637 /* \doc |set_diff| returns a new set which is the difference resulting from
638 removing every element in |set2| from the elements in |set1|. Only
639 pointers to elements are copied, \emph{not} the data pointed (this has
640 memory management implications). The |hash| and |compare| functions
641 must be identical for the two sets. */
642
set_diff(set_Set set1,set_Set set2)643 set_Set set_diff(set_Set set1, set_Set set2)
644 {
645 setType t1 = (setType)set1;
646 setType t2 = (setType)set2;
647 set_Set set;
648 unsigned long i;
649 int savedReadonly;
650
651 _set_check(t1, __func__);
652 _set_check(t2, __func__);
653
654 if (t1->hash != t2->hash)
655 err_fatal(__func__,
656 "Sets do not have identical hash functions");
657
658 if (t1->compare != t2->compare)
659 err_fatal(__func__,
660 "Sets do not have identical comparison functions");
661
662 set = set_create(t1->hash, t1->compare);
663
664 savedReadonly = t2->readonly;
665 t2->readonly = 1; /* save time on set_member */
666 for (i = 0; i < t1->prime; i++) {
667 if (t1->buckets[i]) {
668 bucketType pt;
669
670 for (pt = t1->buckets[i]; pt; pt = pt->next)
671 if (!set_member(t2, pt->elem))
672 set_insert(set, pt->elem);
673 }
674 }
675 t2->readonly = savedReadonly;
676
677 return set;
678 }
679
680 /* \doc |set_equal| returns non-zero if |set1| and |set2| contain the same
681 number of elements, and all of the elements in |set1| are also in
682 |set2|. The |hash| and |compare| functions must be identical for the
683 two sets. */
684
set_equal(set_Set set1,set_Set set2)685 int set_equal(set_Set set1, set_Set set2)
686 {
687 setType t1 = (setType)set1;
688 setType t2 = (setType)set2;
689 unsigned long i;
690 int savedReadonly;
691
692 _set_check(t1, __func__);
693 _set_check(t2, __func__);
694
695 if (t1->hash != t2->hash)
696 err_fatal(__func__,
697 "Sets do not have identical hash functions");
698
699 if (t1->compare != t2->compare)
700 err_fatal(__func__,
701 "Sets do not have identical comparison functions");
702
703 if (t1->entries != t2->entries) return 0; /* not equal */
704
705 savedReadonly = t2->readonly;
706 t2->readonly = 1; /* save time on set_member */
707 for (i = 0; i < t1->prime; i++) {
708 if (t1->buckets[i]) {
709 bucketType pt;
710
711 for (pt = t1->buckets[i]; pt; pt = pt->next)
712 if (!set_member(t2, pt->elem)) {
713 t2->readonly = savedReadonly;
714 return 0; /* not equal */
715 }
716 }
717 }
718 t2->readonly = savedReadonly;
719
720 return 1; /* equal */
721 }
722
set_count(set_Set set)723 int set_count(set_Set set)
724 {
725 setType t = (setType)set;
726
727 _set_check(t, __func__);
728 return t->entries;
729 }
730
731 /* \doc |set_get_stats| returns statistics about the |set|. The
732 |set_Stats| structure is shown in \grind{set_Stats}. */
733
set_get_stats(set_Set set)734 set_Stats set_get_stats(set_Set set)
735 {
736 setType t = (setType)set;
737 set_Stats s = xmalloc(sizeof(struct set_Stats));
738 unsigned long i;
739 unsigned long count;
740
741 _set_check(t, __func__);
742
743 s->size = t->prime;
744 s->resizings = t->resizings;
745 s->entries = 0;
746 s->buckets_used = 0;
747 s->singletons = 0;
748 s->maximum_length = 0;
749 s->retrievals = t->retrievals;
750 s->hits = t->hits;
751 s->misses = t->misses;
752
753 for (i = 0; i < t->prime; i++) {
754 if (t->buckets[i]) {
755 bucketType pt;
756
757 ++s->buckets_used;
758 for (count = 0, pt = t->buckets[i]; pt; ++count, pt = pt->next);
759 if (count == 1) ++s->singletons;
760 s->maximum_length = max(s->maximum_length, count);
761 s->entries += count;
762 }
763 }
764
765 if (t->entries != s->entries)
766 err_internal(__func__,
767 "Incorrect count for entries: %lu vs. %lu",
768 t->entries,
769 s->entries);
770
771
772 return s;
773 }
774
775 /* \doc |set_print_stats| prints the statistics for |set| on the specified
776 |stream|. If |stream| is "NULL", then "stdout" will be used. */
777
set_print_stats(set_Set set,FILE * stream)778 void set_print_stats(set_Set set, FILE *stream)
779 {
780 setType t = (setType)set;
781 FILE *str = stream ? stream : stdout;
782 set_Stats s = set_get_stats(t);
783
784 _set_check(t, __func__);
785
786 fprintf(str, "Statistics for set at %p:\n", set);
787 fprintf(str, " %lu resizings to %lu total\n", s->resizings, s->size);
788 fprintf(str, " %lu entries (%lu buckets used, %lu without overflow)\n",
789 s->entries, s->buckets_used, s->singletons);
790 fprintf(str, " maximum list length is %lu", s->maximum_length);
791 if (s->buckets_used)
792 fprintf(str, " (optimal is %.1f)\n",
793 (double)s->entries / (double)s->buckets_used);
794 else
795 fprintf(str, "\n");
796 fprintf(str, " %lu retrievals (%lu from top, %lu failed)\n",
797 s->retrievals, s->hits, s->misses);
798
799 xfree(s); /* rare */
800 }
801