1 /* GNU Mailutils -- a suite of utilities for electronic mail
2 Copyright (C) 2007-2021 Free Software Foundation, Inc.
3
4 GNU Mailutils is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3, or (at your option)
7 any later version.
8
9 GNU Mailutils 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 GNU Mailutils. If not, see <http://www.gnu.org/licenses/>. */
16
17 #if HAVE_CONFIG_H
18 # include <config.h>
19 #endif
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <mailutils/types.h>
24 #include <mailutils/assoc.h>
25 #include <mailutils/errno.h>
26 #include <mailutils/error.h>
27 #include <mailutils/iterator.h>
28 #include <mailutils/util.h>
29 #include <mailutils/cctype.h>
30 #include <mailutils/cstr.h>
31 #include <mailutils/sys/iterator.h>
32
33 /* |hash_size| defines a sequence of symbol table sizes. These are prime
34 numbers, the distance between each pair of them grows exponentially,
35 starting from 64. Hardly someone will need more than 16411 symbols, and
36 even if someone will, it is easy enough to add more numbers to the
37 sequence. */
38
39 static unsigned int hash_size[] = {
40 37, 101, 229, 487, 1009, 2039, 4091, 8191, 16411
41 };
42
43 /* |max_rehash| keeps the number of entries in |hash_size| table. */
44 static unsigned int max_rehash = sizeof (hash_size) / sizeof (hash_size[0]);
45
46 struct _mu_assoc_elem
47 {
48 char *name;
49 struct _mu_assoc_elem *next, *prev;
50 int mark:1;
51 char *data;
52 };
53
54 struct _mu_assoc
55 {
56 int flags;
57 unsigned int hash_num; /* Index to hash_size table */
58 unsigned (*hash) (const char *name, unsigned long hash_num);
59 struct _mu_assoc_elem **tab;
60 struct _mu_assoc_elem *head, *tail;
61 mu_deallocator_t free;
62 mu_iterator_t itr;
63 };
64
65 static void
assoc_elem_unlink(mu_assoc_t assoc,int idx)66 assoc_elem_unlink (mu_assoc_t assoc, int idx)
67 {
68 struct _mu_assoc_elem *p;
69
70 p = assoc->tab[idx]->prev;
71 if (p)
72 p->next = assoc->tab[idx]->next;
73 else
74 assoc->head = assoc->tab[idx]->next;
75
76 p = assoc->tab[idx]->next;
77 if (p)
78 p->prev = assoc->tab[idx]->prev;
79 else
80 assoc->tail = assoc->tab[idx]->prev;
81
82 assoc->tab[idx]->prev = assoc->tab[idx]->next = NULL;
83 }
84
85 static void
assoc_elem_link(mu_assoc_t assoc,int idx)86 assoc_elem_link (mu_assoc_t assoc, int idx)
87 {
88 assoc->tab[idx]->next = NULL;
89 assoc->tab[idx]->prev = assoc->tail;
90
91 if (assoc->tail)
92 assoc->tail->next = assoc->tab[idx];
93 else
94 assoc->head = assoc->tab[idx];
95 assoc->tail = assoc->tab[idx];
96 }
97
98 static unsigned
hash_dfl(const char * name,unsigned long hash_num)99 hash_dfl (const char *name, unsigned long hash_num)
100 {
101 unsigned i;
102
103 for (i = 0; *name; name++)
104 {
105 i <<= 1;
106 i ^= *(unsigned char*) name;
107 }
108 return i % hash_size[hash_num];
109 };
110
111 static unsigned
hash_ci(const char * name,unsigned long hash_num)112 hash_ci (const char *name, unsigned long hash_num)
113 {
114 unsigned i;
115
116 for (i = 0; *name; name++)
117 {
118 i <<= 1;
119 i ^= mu_tolower(*(unsigned char*) name);
120 }
121 return i % hash_size[hash_num];
122 };
123
124 static int assoc_find_slot (mu_assoc_t assoc, const char *name,
125 int *install, unsigned *slot);
126
127 static int
assoc_rehash(mu_assoc_t assoc)128 assoc_rehash (mu_assoc_t assoc)
129 {
130 struct _mu_assoc_elem **old_tab = assoc->tab;
131 struct _mu_assoc_elem **new_tab;
132 unsigned int i;
133 unsigned int hash_num = assoc->hash_num + 1;
134
135 if (hash_num >= max_rehash)
136 return MU_ERR_BUFSPACE;
137
138 new_tab = calloc (hash_size[hash_num], sizeof (new_tab[0]));
139 if (!new_tab)
140 return errno;
141 assoc->tab = new_tab;
142 if (old_tab)
143 {
144 assoc->hash_num = hash_num;
145 for (i = 0; i < hash_size[hash_num-1]; i++)
146 {
147 if (old_tab[i])
148 {
149 int tmp;
150 unsigned slot;
151 int rc = assoc_find_slot (assoc, old_tab[i]->name,
152 &tmp, &slot);
153 if (rc)
154 return rc;
155 assoc->tab[slot] = old_tab[i];
156 }
157 }
158 free (old_tab);
159 }
160 return 0;
161 }
162
163 static void
assoc_free_elem(mu_assoc_t assoc,unsigned idx)164 assoc_free_elem (mu_assoc_t assoc, unsigned idx)
165 {
166 if (assoc->tab[idx])
167 {
168 assoc_elem_unlink (assoc, idx);
169 if (assoc->free)
170 assoc->free (assoc->tab[idx]->data);
171 if (!(assoc->flags & MU_ASSOC_COPY_KEY))
172 free (assoc->tab[idx]->name);
173 free (assoc->tab[idx]);
174 assoc->tab[idx] = NULL;
175 }
176 }
177
178 static int
assoc_remove(mu_assoc_t assoc,unsigned idx)179 assoc_remove (mu_assoc_t assoc, unsigned idx)
180 {
181 unsigned int i, j, r;
182
183 if (!(idx < hash_size[assoc->hash_num]))
184 return EINVAL;
185
186 mu_iterator_delitem (assoc->itr, assoc->tab[idx]);
187 assoc_free_elem (assoc, idx);
188
189 for (i = idx;;)
190 {
191 assoc->tab[i] = NULL;
192 j = i;
193
194 do
195 {
196 if (++i >= hash_size[assoc->hash_num])
197 i = 0;
198 if (!assoc->tab[i])
199 return 0;
200 r = assoc->hash (assoc->tab[i]->name, assoc->hash_num);
201 }
202 while ((j < r && r <= i) || (i < j && j < r) || (r <= i && i < j));
203
204 if (j != i)
205 assoc->tab[j] = assoc->tab[i];
206 }
207 return 0;
208 }
209
210 static int
assoc_remove_elem(mu_assoc_t assoc,struct _mu_assoc_elem * elem,int nd)211 assoc_remove_elem (mu_assoc_t assoc, struct _mu_assoc_elem *elem, int nd)
212 {
213 unsigned i;
214
215 if (elem)
216 {
217 for (i = 0; i < hash_size[assoc->hash_num]; i++)
218 {
219 if (assoc->tab[i] == elem)
220 {
221 if (nd)
222 assoc->tab[i]->data = NULL;
223 assoc_remove (assoc, i);
224 return 0;
225 }
226 }
227 }
228 return MU_ERR_NOENT;
229 }
230
231 #define name_cmp(assoc,a,b) (((assoc)->flags & MU_ASSOC_ICASE) ? \
232 mu_c_strcasecmp(a,b) : strcmp(a,b))
233
234 static int
assoc_find_slot(mu_assoc_t assoc,const char * name,int * install,unsigned * slot)235 assoc_find_slot (mu_assoc_t assoc, const char *name,
236 int *install, unsigned *slot)
237 {
238 int rc;
239 unsigned i, pos;
240 struct _mu_assoc_elem *elem;
241
242 if (!assoc->tab)
243 {
244 if (install)
245 {
246 rc = assoc_rehash (assoc);
247 if (rc)
248 return rc;
249 }
250 else
251 return MU_ERR_NOENT;
252 }
253
254 pos = assoc->hash (name, assoc->hash_num);
255
256 for (i = pos; (elem = assoc->tab[i]);)
257 {
258 if (name_cmp (assoc, elem->name, name) == 0)
259 {
260 if (install)
261 *install = 0;
262 *slot = i;
263 return 0;
264 }
265
266 if (++i >= hash_size[assoc->hash_num])
267 i = 0;
268 if (i == pos)
269 break;
270 }
271
272 if (!install)
273 return MU_ERR_NOENT;
274
275 if (!elem)
276 {
277 *slot = i;
278 *install = 1;
279 return 0;
280 }
281
282 if ((rc = assoc_rehash (assoc)) != 0)
283 return rc;
284
285 return assoc_find_slot (assoc, name, install, slot);
286 }
287
288 int
mu_assoc_create(mu_assoc_t * passoc,int flags)289 mu_assoc_create (mu_assoc_t *passoc, int flags)
290 {
291 mu_assoc_t assoc = calloc (1, sizeof (*assoc));
292 if (!assoc)
293 return ENOMEM;
294 assoc->flags = flags;
295 assoc->hash = flags & MU_ASSOC_ICASE ? hash_ci : hash_dfl;
296 *passoc = assoc;
297 return 0;
298 }
299
300 void
mu_assoc_clear(mu_assoc_t assoc)301 mu_assoc_clear (mu_assoc_t assoc)
302 {
303 unsigned i, hs;
304
305 if (!assoc || !assoc->tab)
306 return;
307
308 hs = hash_size[assoc->hash_num];
309 for (i = 0; i < hs; i++)
310 assoc_free_elem (assoc, i);
311 }
312
313 void
mu_assoc_destroy(mu_assoc_t * passoc)314 mu_assoc_destroy (mu_assoc_t *passoc)
315 {
316 mu_assoc_t assoc;
317 if (passoc && (assoc = *passoc) != NULL)
318 {
319 mu_assoc_clear (assoc);
320 free (assoc->tab);
321 free (assoc);
322 *passoc = NULL;
323 }
324 }
325
326 int
mu_assoc_set_destroy_item(mu_assoc_t assoc,mu_deallocator_t fn)327 mu_assoc_set_destroy_item (mu_assoc_t assoc, mu_deallocator_t fn)
328 {
329 if (!assoc)
330 return EINVAL;
331 assoc->free = fn;
332 return 0;
333 }
334
335 int
mu_assoc_lookup(mu_assoc_t assoc,const char * name,void * dataptr)336 mu_assoc_lookup (mu_assoc_t assoc, const char *name, void *dataptr)
337 {
338 int rc;
339 unsigned idx;
340
341 if (!assoc || !name)
342 return EINVAL;
343
344 rc = assoc_find_slot (assoc, name, NULL, &idx);
345 if (rc == 0)
346 {
347 if (dataptr)
348 *(void**)dataptr = assoc->tab[idx]->data;
349 }
350 return rc;
351 }
352
353
354 void *
mu_assoc_get(mu_assoc_t assoc,const char * name)355 mu_assoc_get (mu_assoc_t assoc, const char *name)
356 {
357 int rc;
358 unsigned idx;
359
360 if (!assoc || !name)
361 return NULL;
362
363 rc = assoc_find_slot (assoc, name, NULL, &idx);
364 if (rc == 0)
365 return assoc->tab[idx]->data;
366 return NULL;
367 }
368
369 int
mu_assoc_install(mu_assoc_t assoc,const char * name,void * value)370 mu_assoc_install (mu_assoc_t assoc, const char *name, void *value)
371 {
372 int rc;
373 int inst;
374 unsigned idx;
375 struct _mu_assoc_elem *elem;
376
377 if (!assoc || !name)
378 return EINVAL;
379
380 rc = assoc_find_slot (assoc, name, &inst, &idx);
381 if (rc)
382 return rc;
383 if (!inst)
384 return MU_ERR_EXISTS;
385
386 elem = malloc (sizeof *elem);
387 if (!elem)
388 return errno;
389
390 if (assoc->flags & MU_ASSOC_COPY_KEY)
391 elem->name = (char *) name;
392 else
393 {
394 elem->name = strdup (name);
395 if (!elem->name)
396 {
397 int rc = errno;
398 free (elem);
399 return rc;
400 }
401 }
402 elem->data = value;
403 assoc->tab[idx] = elem;
404 assoc_elem_link (assoc, idx);
405 return 0;
406 }
407
408 int
mu_assoc_lookup_ref(mu_assoc_t assoc,const char * name,void * dataptr)409 mu_assoc_lookup_ref (mu_assoc_t assoc, const char *name, void *dataptr)
410 {
411 int rc;
412 unsigned idx;
413
414 if (!assoc || !name)
415 return EINVAL;
416
417 rc = assoc_find_slot (assoc, name, NULL, &idx);
418 if (rc == 0)
419 {
420 if (dataptr)
421 *(void**)dataptr = &assoc->tab[idx]->data;
422 }
423 return rc;
424 }
425
426 int
mu_assoc_install_ref2(mu_assoc_t assoc,const char * name,void * ret_val,const char ** ret_name)427 mu_assoc_install_ref2 (mu_assoc_t assoc, const char *name,
428 void *ret_val,
429 const char **ret_name)
430 {
431 int rc;
432 int inst;
433 unsigned idx;
434
435 if (!assoc || !name)
436 return EINVAL;
437
438 rc = assoc_find_slot (assoc, name, &inst, &idx);
439 if (rc)
440 return rc;
441
442 if (inst)
443 {
444 struct _mu_assoc_elem *elem;
445
446 elem = malloc (sizeof *elem);
447 if (!elem)
448 return errno;
449
450 if (assoc->flags & MU_ASSOC_COPY_KEY)
451 elem->name = (char *) name;
452 else
453 {
454 elem->name = strdup (name);
455 if (!elem->name)
456 {
457 int rc = errno;
458 free (elem);
459 return rc;
460 }
461 }
462 elem->data = NULL;
463 assoc->tab[idx] = elem;
464 assoc_elem_link (assoc, idx);
465 }
466
467 *(void**)ret_val = &assoc->tab[idx]->data;
468 if (ret_name)
469 *ret_name = assoc->tab[idx]->name;
470
471 return inst ? 0 : MU_ERR_EXISTS;
472 }
473
474 int
mu_assoc_install_ref(mu_assoc_t assoc,const char * name,void * pval)475 mu_assoc_install_ref (mu_assoc_t assoc, const char *name, void *pval)
476 {
477 return mu_assoc_install_ref2 (assoc, name, pval, NULL);
478 }
479
480 int
mu_assoc_remove(mu_assoc_t assoc,const char * name)481 mu_assoc_remove (mu_assoc_t assoc, const char *name)
482 {
483 int rc;
484 unsigned idx;
485
486 if (!assoc || !name)
487 return EINVAL;
488 rc = assoc_find_slot (assoc, name, NULL, &idx);
489 if (rc)
490 return rc;
491 return assoc_remove (assoc, idx);
492 }
493
494 /* Iterator interface */
495
496 struct assoc_iterator
497 {
498 mu_assoc_t assoc;
499 struct _mu_assoc_elem *elem;
500 int backwards; /* true if iterating backwards */
501 };
502
503 static int
itrctl(void * owner,enum mu_itrctl_req req,void * arg)504 itrctl (void *owner, enum mu_itrctl_req req, void *arg)
505 {
506 struct assoc_iterator *itr = owner;
507 mu_assoc_t assoc = itr->assoc;
508
509 switch (req)
510 {
511 case mu_itrctl_tell:
512 /* Return current position in the object */
513 {
514 size_t n = 0;
515 struct _mu_assoc_elem *elem;
516
517 for (elem = itr->elem; elem; elem = elem->prev)
518 n++;
519 *(size_t*)arg = n;
520 }
521 break;
522
523 case mu_itrctl_delete:
524 case mu_itrctl_delete_nd:
525 /* Delete current element */
526 return assoc_remove_elem (assoc, itr->elem, req == mu_itrctl_delete_nd);
527
528 case mu_itrctl_replace:
529 case mu_itrctl_replace_nd:
530 /* Replace current element */
531 if (itr->elem == NULL)
532 return MU_ERR_NOENT;
533 if (req == mu_itrctl_replace && assoc->free)
534 assoc->free (itr->elem->data);
535 itr->elem->data = arg;
536 break;
537
538 case mu_itrctl_qry_direction:
539 if (!arg)
540 return EINVAL;
541 else
542 *(int*)arg = itr->backwards;
543 break;
544
545 case mu_itrctl_set_direction:
546 if (!arg)
547 return EINVAL;
548 else
549 itr->backwards = !!*(int*)arg;
550 break;
551
552 case mu_itrctl_count:
553 if (!arg)
554 return EINVAL;
555 return mu_assoc_count (assoc, arg);
556
557 default:
558 return ENOSYS;
559 }
560 return 0;
561 }
562
563 static int
first(void * owner)564 first (void *owner)
565 {
566 struct assoc_iterator *itr = owner;
567 mu_assoc_t assoc = itr->assoc;
568 itr->elem = itr->backwards ? assoc->tail : assoc->head;
569 return 0;
570 }
571
572 static int
next(void * owner)573 next (void *owner)
574 {
575 struct assoc_iterator *itr = owner;
576 itr->elem = itr->backwards ? itr->elem->prev : itr->elem->next;
577 return 0;
578 }
579
580 static int
getitem(void * owner,void ** pret,const void ** pkey)581 getitem (void *owner, void **pret, const void **pkey)
582 {
583 struct assoc_iterator *itr = owner;
584
585 if (!itr->elem)
586 return EINVAL;
587 *pret = itr->elem->data;
588 if (pkey)
589 *pkey = itr->elem->name;
590 return 0;
591 }
592
593 static int
finished_p(void * owner)594 finished_p (void *owner)
595 {
596 struct assoc_iterator *itr = owner;
597 return itr->elem == NULL;
598 }
599
600 static int
destroy(mu_iterator_t iterator,void * data)601 destroy (mu_iterator_t iterator, void *data)
602 {
603 struct assoc_iterator *itr = data;
604 mu_iterator_detach (&itr->assoc->itr, iterator);
605 free (data);
606 return 0;
607 }
608
609 static int
delitem(void * owner,void * item)610 delitem (void *owner, void *item)
611 {
612 struct assoc_iterator *itr = owner;
613 return itr->elem == item ? MU_ITR_DELITEM_NEXT : MU_ITR_DELITEM_NOTHING;
614 }
615
616 static int
assoc_data_dup(void ** ptr,void * owner)617 assoc_data_dup (void **ptr, void *owner)
618 {
619 *ptr = malloc (sizeof (struct assoc_iterator));
620 if (*ptr == NULL)
621 return ENOMEM;
622 memcpy (*ptr, owner, sizeof (struct assoc_iterator));
623 return 0;
624 }
625
626 int
mu_assoc_get_iterator(mu_assoc_t assoc,mu_iterator_t * piterator)627 mu_assoc_get_iterator (mu_assoc_t assoc, mu_iterator_t *piterator)
628 {
629 mu_iterator_t iterator;
630 int status;
631 struct assoc_iterator *itr;
632
633 if (!assoc)
634 return EINVAL;
635
636 itr = calloc (1, sizeof *itr);
637 if (!itr)
638 return ENOMEM;
639 itr->assoc = assoc;
640 itr->elem = NULL;
641
642 status = mu_iterator_create (&iterator, itr);
643 if (status)
644 {
645 free (itr);
646 return status;
647 }
648
649 mu_iterator_set_first (iterator, first);
650 mu_iterator_set_next (iterator, next);
651 mu_iterator_set_getitem (iterator, getitem);
652 mu_iterator_set_finished_p (iterator, finished_p);
653 mu_iterator_set_delitem (iterator, delitem);
654 mu_iterator_set_destroy (iterator, destroy);
655 mu_iterator_set_dup (iterator, assoc_data_dup);
656 mu_iterator_set_itrctl (iterator, itrctl);
657
658 mu_iterator_attach (&assoc->itr, iterator);
659
660 *piterator = iterator;
661 return 0;
662 }
663
664 int
mu_assoc_count(mu_assoc_t assoc,size_t * pcount)665 mu_assoc_count (mu_assoc_t assoc, size_t *pcount)
666 {
667 size_t length = 0;
668
669 if (!pcount)
670 return MU_ERR_OUT_PTR_NULL;
671 if (assoc)
672 {
673 struct _mu_assoc_elem *elt;
674 for (elt = assoc->head; elt; elt = elt->next)
675 length++;
676 }
677 *pcount = length;
678 return 0;
679 }
680
681 int
mu_assoc_is_empty(mu_assoc_t assoc)682 mu_assoc_is_empty (mu_assoc_t assoc)
683 {
684 return assoc == NULL || assoc->head == NULL;
685 }
686
687 int
mu_assoc_foreach(mu_assoc_t assoc,mu_assoc_action_t action,void * data)688 mu_assoc_foreach (mu_assoc_t assoc, mu_assoc_action_t action, void *data)
689 {
690 mu_iterator_t itr;
691 int rc;
692
693 if (!assoc || !action)
694 return EINVAL;
695 rc = mu_assoc_get_iterator (assoc, &itr);
696 if (rc)
697 return rc;
698 for (mu_iterator_first (itr); !mu_iterator_is_done (itr);
699 mu_iterator_next (itr))
700 {
701 char *name;
702 void *value;
703
704 rc = mu_iterator_current_kv (itr, (const void **)&name, (void**)&value);
705 if (rc)
706 break;
707
708 rc = action (name, value, data);
709 if (rc)
710 break;
711 }
712 mu_iterator_destroy (&itr);
713 return rc;
714 }
715
716 /* Merges the two NULL-terminated lists, LEFT and RIGHT, using CMP for
717 element comparison. DATA supplies call-specific data for CMP.
718
719 Both LEFT and RIGHT are treated as singly-linked lists, with NEXT pointing
720 to the successive element. PREV pointers are ignored.
721
722 Returns the resulting list.
723 */
724 static struct _mu_assoc_elem *
merge(struct _mu_assoc_elem * left,struct _mu_assoc_elem * right,mu_assoc_comparator_t cmp,void * data)725 merge (struct _mu_assoc_elem *left, struct _mu_assoc_elem *right,
726 mu_assoc_comparator_t cmp, void *data)
727 {
728 struct _mu_assoc_elem *head = NULL, **tailptr = &head, *tmp;
729
730 while (left && right)
731 {
732 if (cmp (left->name, left->data, right->name, right->data, data) <= 0)
733 {
734 tmp = left->next;
735 *tailptr = left;
736 tailptr = &left->next;
737 left = tmp;
738 }
739 else
740 {
741 tmp = right->next;
742 *tailptr = right;
743 tailptr = &right->next;
744 right = tmp;
745 }
746 }
747
748 *tailptr = left ? left : right;
749
750 return head;
751 }
752
753 /* Sort the singly-linked LIST of LENGTH elements using merge sort algorithm.
754 Elements are compared using the CMP function with DATA pointing to
755 call-specific data.
756 The elements of LIST are linked by the NEXT pointer. The NEXT pointer of
757 the last element (LIST[LENGTH], 1-based) must be NULL.
758
759 Returns the resulting list.
760
761 Side-effects: PREV pointers in the returned list are messed up.
762 */
763 static struct _mu_assoc_elem *
merge_sort(struct _mu_assoc_elem * list,size_t length,mu_assoc_comparator_t cmp,void * data)764 merge_sort (struct _mu_assoc_elem *list, size_t length,
765 mu_assoc_comparator_t cmp, void *data)
766 {
767 struct _mu_assoc_elem *left, *right;
768 size_t left_len, right_len, i;
769 struct _mu_assoc_elem *elt;
770
771 if (length <= 1)
772 return list;
773
774 if (length == 2)
775 {
776 elt = list->next;
777 if (cmp (list->name, list->data, elt->name, elt->data, data) > 0)
778 {
779 elt->next = list;
780 list->next = NULL;
781 return elt;
782 }
783 return list;
784 }
785
786 left = list;
787 left_len = (length + 1) / 2;
788
789 right_len = length / 2;
790 for (elt = list, i = left_len - 1; i; i--)
791 elt = elt->next;
792
793 right = elt->next;
794 elt->next = NULL;
795
796 left = merge_sort (left, left_len, cmp, data);
797 right = merge_sort (right, right_len, cmp, data);
798
799 return merge (left, right, cmp, data);
800 }
801
802 /* Sort the linked list of elements in ASSOC using merge sort. CMP points
803 to the function to use for comparing two elements. DATA supplies call-
804 specific data for CMP.
805 */
806 int
mu_assoc_sort_r(mu_assoc_t assoc,mu_assoc_comparator_t cmp,void * data)807 mu_assoc_sort_r (mu_assoc_t assoc, mu_assoc_comparator_t cmp, void *data)
808 {
809 struct _mu_assoc_elem *head, *prev, *p;
810 size_t length;
811
812 if (!assoc)
813 return EINVAL;
814 if (!cmp)
815 return 0;
816
817 mu_assoc_count (assoc, &length);
818 head = merge_sort (assoc->head, length, cmp, data);
819 /* The above call leaves PREV pointers in inconsistent state. Fix them
820 up: */
821 for (prev = NULL, p = head; p; prev = p, p = p->next)
822 p->prev = prev;
823
824 /* Update list head and tail */
825 assoc->head = head;
826 assoc->tail = prev;
827
828 return 0;
829 }
830
831 int
mu_assoc_mark(mu_assoc_t asc,int (* cond)(char const *,void *,void *),void * data)832 mu_assoc_mark (mu_assoc_t asc, int (*cond) (char const *, void *, void *),
833 void *data)
834 {
835 struct _mu_assoc_elem *elt;
836
837 if (!asc)
838 return EINVAL;
839 for (elt = asc->head; elt; elt = elt->next)
840 elt->mark = !!cond (elt->name, elt->data, data);
841 return 0;
842 }
843
844 int
mu_assoc_sweep(mu_assoc_t asc)845 mu_assoc_sweep (mu_assoc_t asc)
846 {
847 unsigned i;
848
849 if (!asc)
850 return EINVAL;
851
852 if (asc->tab)
853 {
854 for (i = hash_size[asc->hash_num]; i > 0; i--)
855 {
856 if (asc->tab[i-1] && asc->tab[i-1]->mark)
857 assoc_remove (asc, i-1);
858 }
859 }
860
861 return 0;
862 }
863
864 int
mu_assoc_sweep_unset(mu_assoc_t asc)865 mu_assoc_sweep_unset (mu_assoc_t asc)
866 {
867 unsigned i;
868
869 if (!asc)
870 return EINVAL;
871
872 if (asc->tab)
873 {
874 for (i = hash_size[asc->hash_num]; i > 0; i--)
875 {
876 if (asc->tab[i-1] && asc->tab[i-1]->mark)
877 {
878 if (asc->free)
879 asc->free (asc->tab[i]->data);
880 asc->tab[i]->data = NULL;
881 }
882 }
883 }
884
885 return 0;
886 }
887
888 int
mu_assoc_set_mark(mu_assoc_t asc,char const * name,int mark)889 mu_assoc_set_mark (mu_assoc_t asc, char const *name, int mark)
890 {
891 int rc;
892 unsigned i;
893
894 if (!asc || !name)
895 return EINVAL;
896
897 rc = assoc_find_slot (asc, name, NULL, &i);
898 if (rc == 0)
899 asc->tab[i]->mark = !!mark;
900 return rc;
901 }
902
903 int
mu_assoc_head_set_mark(mu_assoc_t asc,int mark)904 mu_assoc_head_set_mark (mu_assoc_t asc, int mark)
905 {
906 if (!asc)
907 return EINVAL;
908 if (asc->head)
909 asc->head->mark = !!mark;
910 return 0;
911 }
912
913 int
mu_assoc_tail_set_mark(mu_assoc_t asc,int mark)914 mu_assoc_tail_set_mark (mu_assoc_t asc, int mark)
915 {
916 if (!asc)
917 return EINVAL;
918 if (asc->tail)
919 asc->tail->mark = !!mark;
920 return 0;
921 }
922
923 int
mu_assoc_pop(mu_assoc_t asc,char const * name,void * ret_val)924 mu_assoc_pop (mu_assoc_t asc, char const *name, void *ret_val)
925 {
926 if (!asc || !name)
927 return EINVAL;
928
929 if (asc->tail && ret_val != NULL)
930 {
931 *(void**)ret_val = asc->tail->data;
932 }
933 return assoc_remove_elem (asc, asc->tail, ret_val != NULL);
934 }
935
936 int
mu_assoc_shift(mu_assoc_t asc,char const * name,void * ret_val)937 mu_assoc_shift (mu_assoc_t asc, char const *name, void *ret_val)
938 {
939 if (!asc || !name)
940 return EINVAL;
941
942 if (asc->head && ret_val != NULL)
943 {
944 *(void**)ret_val = asc->head->data;
945 }
946 return assoc_remove_elem (asc, asc->head, ret_val != NULL);
947 }
948
949 /* Given A and B - two associative arrays keeping the same kind of data,
950 move from B to A all elements whose names are present in A. Remove
951 from A all elements not thus updated.
952 */
953 void
mu_assoc_pull(mu_assoc_t a,mu_assoc_t b)954 mu_assoc_pull (mu_assoc_t a, mu_assoc_t b)
955 {
956 unsigned i;
957
958 for (i = 0; i < hash_size[a->hash_num]; i++)
959 {
960 if (a->tab[i])
961 {
962 unsigned j;
963 int rc;
964
965 rc = assoc_find_slot (b, a->tab[i]->name, NULL, &j);
966 if (rc == 0)
967 {
968 if (a->free)
969 a->free (a->tab[i]->data);
970 a->tab[i]->data = b->tab[j]->data;
971 b->tab[j]->data = NULL;
972 assoc_remove (b, j);
973 }
974 else
975 assoc_remove (a, i);
976 }
977 }
978 }
979
980 /* TODO
981 mu_assoc_union (mu_assoc_t *r, mu_assoc_t a, mu_assoc_t b)
982 Computes the union of A and B. Stores the result in R.
983 mu_assoc_intersect (mu_assoc_t *r, mu_assoc_t a, mu_assoc_t b)
984 Computes the intersection of A and B.
985 mu_assoc_symdiff (mu_assoc_t *r, mu_assoc_t a, mu_assoc_t b)
986 Computes the symmetric difference (disjunctive union) of the two
987 arrays.
988 */
989