1 /* String-list functions for GNU Mailutils.
2 Copyright (C) 2007-2021 Free Software Foundation, Inc.
3
4 Based on slist module from GNU Radius. Written by Sergey Poznyakoff.
5
6 GNU Mailutils is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation; either version 3, or (at
9 your option) any later version.
10
11 GNU Mailutils is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU Mailutils. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #ifdef HAVE_CONFIG_H
21 # include <config.h>
22 #endif
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <stdint.h>
26 #include <string.h>
27 #include <mailutils/types.h>
28 #include <mailutils/alloc.h>
29 #include <mailutils/opool.h>
30 #include <mailutils/errno.h>
31 #include <mailutils/error.h>
32 #include <mailutils/nls.h>
33 #include <mailutils/iterator.h>
34
35 struct bucket_header
36 {
37 union mu_opool_bucket *next;
38 char *buf;
39 size_t level;
40 size_t size;
41 };
42
43 union mu_opool_bucket
44 {
45 struct bucket_header hdr;
46 long double align_double;
47 uintmax_t align_uintmax;
48 void *align_ptr;
49 };
50
51 struct _mu_opool
52 {
53 int flags; /* Flag bits */
54 size_t bucket_size; /* Default bucket size */
55 size_t itr_count; /* Number of iterators created for this pool */
56 mu_nonlocal_jmp_t *jmp; /* Buffer for non-local exit */
57 union mu_opool_bucket *bkt_head, *bkt_tail;
58 union mu_opool_bucket *bkt_fini; /* List of finished objects */
59 };
60
61 static union mu_opool_bucket *
alloc_bucket(struct _mu_opool * opool,size_t size)62 alloc_bucket (struct _mu_opool *opool, size_t size)
63 {
64 union mu_opool_bucket *p = malloc (sizeof (*p) + size);
65 if (!p)
66 {
67 if (opool->flags & MU_OPOOL_ENOMEMABRT)
68 mu_alloc_die ();
69 if (opool->jmp)
70 longjmp (opool->jmp->buf, ENOMEM);
71 }
72 else
73 {
74 p->hdr.buf = (char*)(p + 1);
75 p->hdr.level = 0;
76 p->hdr.size = size;
77 p->hdr.next = NULL;
78 }
79 return p;
80 }
81
82 static int
alloc_pool(mu_opool_t opool,size_t size)83 alloc_pool (mu_opool_t opool, size_t size)
84 {
85 union mu_opool_bucket *p = alloc_bucket (opool, opool->bucket_size);
86 if (!p)
87 return ENOMEM;
88 if (opool->bkt_tail)
89 opool->bkt_tail->hdr.next = p;
90 else
91 opool->bkt_head = p;
92 opool->bkt_tail = p;
93 return 0;
94 }
95
96 static int
copy_chars(mu_opool_t opool,const char * str,size_t n,size_t * psize)97 copy_chars (mu_opool_t opool, const char *str, size_t n, size_t *psize)
98 {
99 size_t rest;
100
101 if (!opool->bkt_head
102 || opool->bkt_tail->hdr.level == opool->bkt_tail->hdr.size)
103 if (alloc_pool (opool, opool->bucket_size))
104 return ENOMEM;
105 rest = opool->bkt_tail->hdr.size - opool->bkt_tail->hdr.level;
106 if (n > rest)
107 n = rest;
108 memcpy (opool->bkt_tail->hdr.buf + opool->bkt_tail->hdr.level, str, n);
109 opool->bkt_tail->hdr.level += n;
110 *psize = n;
111 return 0;
112 }
113
114 int
mu_opool_create(mu_opool_t * pret,int flags)115 mu_opool_create (mu_opool_t *pret, int flags)
116 {
117 struct _mu_opool *x = malloc (sizeof (x[0]));
118 if (!x)
119 {
120 if (flags & MU_OPOOL_ENOMEMABRT)
121 mu_alloc_die ();
122 return ENOMEM;
123 }
124 x->flags = flags;
125 x->bucket_size = MU_OPOOL_BUCKET_SIZE;
126 x->itr_count = 0;
127 x->bkt_head = x->bkt_tail = x->bkt_fini = NULL;
128 x->jmp = NULL;
129 *pret = x;
130 return 0;
131 }
132
133 void
mu_opool_setjmp(mu_opool_t opool,mu_nonlocal_jmp_t * jmp)134 mu_opool_setjmp (mu_opool_t opool, mu_nonlocal_jmp_t *jmp)
135 {
136 if (jmp)
137 {
138 jmp->next = opool->jmp;
139 opool->jmp = jmp;
140 }
141 else
142 mu_opool_clrjmp (opool);
143 }
144
145 void
mu_opool_clrjmp(mu_opool_t opool)146 mu_opool_clrjmp (mu_opool_t opool)
147 {
148 if (opool->jmp)
149 opool->jmp = opool->jmp->next;
150 }
151
152 int
mu_opool_set_bucket_size(mu_opool_t opool,size_t size)153 mu_opool_set_bucket_size (mu_opool_t opool, size_t size)
154 {
155 if (!opool)
156 return EINVAL;
157 opool->bucket_size = size;
158 return 0;
159 }
160
161 int
mu_opool_get_bucket_size(mu_opool_t opool,size_t * psize)162 mu_opool_get_bucket_size (mu_opool_t opool, size_t *psize)
163 {
164 if (!opool || !psize)
165 return EINVAL;
166 *psize = opool->bucket_size;
167 return 0;
168 }
169
170 void
mu_opool_clear(mu_opool_t opool)171 mu_opool_clear (mu_opool_t opool)
172 {
173 if (!opool)
174 return;
175
176 if (opool->bkt_tail)
177 {
178 opool->bkt_tail->hdr.next = opool->bkt_fini;
179 opool->bkt_fini = opool->bkt_head;
180 opool->bkt_head = opool->bkt_tail = NULL;
181 }
182 }
183
184 void
mu_opool_less(mu_opool_t opool,size_t sz)185 mu_opool_less (mu_opool_t opool, size_t sz)
186 {
187 union mu_opool_bucket *p;
188 size_t total = 0;
189
190 if (!opool)
191 return;
192 for (p = opool->bkt_head; p; p = p->hdr.next)
193 {
194 if (total + p->hdr.level >= sz)
195 {
196 union mu_opool_bucket *t;
197 p->hdr.level = sz - total;
198 t = p->hdr.next;
199 p->hdr.next = NULL;
200
201 while (t)
202 {
203 union mu_opool_bucket *next = t->hdr.next;
204 free (t);
205 t = next;
206 }
207 break;
208 }
209 total += p->hdr.level;
210 }
211 }
212
213 void
mu_opool_destroy(mu_opool_t * popool)214 mu_opool_destroy (mu_opool_t *popool)
215 {
216 union mu_opool_bucket *p;
217 if (popool && *popool)
218 {
219 mu_opool_t opool = *popool;
220 mu_opool_clear (opool);
221 for (p = opool->bkt_fini; p; )
222 {
223 union mu_opool_bucket *next = p->hdr.next;
224 free (p);
225 p = next;
226 }
227 free (opool);
228 *popool = NULL;
229 }
230 }
231
232 int
mu_opool_alloc(mu_opool_t opool,size_t size)233 mu_opool_alloc (mu_opool_t opool, size_t size)
234 {
235 while (size)
236 {
237 size_t rest;
238
239 if (!opool->bkt_head
240 || opool->bkt_tail->hdr.level == opool->bkt_tail->hdr.size)
241 if (alloc_pool (opool, opool->bucket_size))
242 return ENOMEM;
243 rest = opool->bkt_tail->hdr.size - opool->bkt_tail->hdr.level;
244 if (size < rest)
245 rest = size;
246 opool->bkt_tail->hdr.level += rest;
247 size -= rest;
248 }
249 return 0;
250 }
251
252 int
mu_opool_append(mu_opool_t opool,const void * str,size_t n)253 mu_opool_append (mu_opool_t opool, const void *str, size_t n)
254 {
255 const char *ptr = str;
256 while (n)
257 {
258 size_t s;
259 if (copy_chars (opool, ptr, n, &s))
260 return ENOMEM;
261 ptr += s;
262 n -= s;
263 }
264 return 0;
265 }
266
267 int
mu_opool_append_char(mu_opool_t opool,char c)268 mu_opool_append_char (mu_opool_t opool, char c)
269 {
270 return mu_opool_append (opool, &c, 1);
271 }
272
273 int
mu_opool_appendz(mu_opool_t opool,const char * str)274 mu_opool_appendz (mu_opool_t opool, const char *str)
275 {
276 return mu_opool_append (opool, str, strlen (str));
277 }
278
279 size_t
mu_opool_size(mu_opool_t opool)280 mu_opool_size (mu_opool_t opool)
281 {
282 size_t size = 0;
283 union mu_opool_bucket *p;
284 for (p = opool->bkt_head; p; p = p->hdr.next)
285 size += p->hdr.level;
286 return size;
287 }
288
289 size_t
mu_opool_copy(mu_opool_t opool,void * buf,size_t size)290 mu_opool_copy (mu_opool_t opool, void *buf, size_t size)
291 {
292 char *cp = buf;
293 size_t total = 0;
294 union mu_opool_bucket *p;
295
296 for (p = opool->bkt_head; p && total < size; p = p->hdr.next)
297 {
298 size_t cpsize = size - total;
299 if (cpsize > p->hdr.level)
300 cpsize = p->hdr.level;
301 memcpy (cp, p->hdr.buf, cpsize);
302 cp += cpsize;
303 total += cpsize;
304 }
305 return total;
306 }
307
308 int
mu_opool_coalesce(mu_opool_t opool,size_t * psize)309 mu_opool_coalesce (mu_opool_t opool, size_t *psize)
310 {
311 size_t size;
312
313 if (opool->itr_count)
314 return MU_ERR_FAILURE;
315 if (opool->bkt_head && opool->bkt_head->hdr.next == NULL)
316 size = opool->bkt_head->hdr.level;
317 else
318 {
319 union mu_opool_bucket *bucket;
320 union mu_opool_bucket *p;
321
322 size = mu_opool_size (opool);
323
324 bucket = alloc_bucket (opool, size);
325 if (!bucket)
326 return ENOMEM;
327 for (p = opool->bkt_head; p; )
328 {
329 union mu_opool_bucket *next = p->hdr.next;
330 memcpy (bucket->hdr.buf + bucket->hdr.level, p->hdr.buf,
331 p->hdr.level);
332 bucket->hdr.level += p->hdr.level;
333 free (p);
334 p = next;
335 }
336 opool->bkt_head = opool->bkt_tail = bucket;
337 }
338 if (psize)
339 *psize = size;
340 return 0;
341 }
342
343 void *
mu_opool_head(mu_opool_t opool,size_t * psize)344 mu_opool_head (mu_opool_t opool, size_t *psize)
345 {
346 if (psize)
347 *psize = opool->bkt_head ? opool->bkt_head->hdr.level : 0;
348 return opool->bkt_head ? opool->bkt_head->hdr.buf : NULL;
349 }
350
351 void *
mu_opool_finish(mu_opool_t opool,size_t * psize)352 mu_opool_finish (mu_opool_t opool, size_t *psize)
353 {
354 if (mu_opool_coalesce (opool, psize))
355 return NULL;
356 mu_opool_clear (opool);
357 return opool->bkt_fini->hdr.buf;
358 }
359
360 void *
mu_opool_detach(mu_opool_t opool,size_t * psize)361 mu_opool_detach (mu_opool_t opool, size_t *psize)
362 {
363 union mu_opool_bucket *bp;
364
365 if (mu_opool_coalesce (opool, psize))
366 return NULL;
367 mu_opool_clear (opool);
368
369 bp = opool->bkt_fini;
370 opool->bkt_fini = bp->hdr.next;
371 memmove (bp, bp->hdr.buf, bp->hdr.level);
372 return bp;
373 }
374
375 void
mu_opool_free(mu_opool_t pool,void * obj)376 mu_opool_free (mu_opool_t pool, void *obj)
377 {
378 if (!pool)
379 return;
380 if (!obj)
381 {
382 if (pool->bkt_head)
383 mu_opool_finish (pool, NULL);
384 while (pool->bkt_fini)
385 {
386 union mu_opool_bucket *next = pool->bkt_fini->hdr.next;
387 free (pool->bkt_fini);
388 pool->bkt_fini = next;
389 }
390 }
391 else
392 {
393 union mu_opool_bucket *bucket = pool->bkt_fini,
394 **pprev = &pool->bkt_fini;
395 while (bucket)
396 {
397 if (bucket->hdr.buf == obj)
398 {
399 *pprev = bucket->hdr.next;
400 free (bucket);
401 return;
402 }
403 pprev = &bucket->hdr.next;
404 bucket = bucket->hdr.next;
405 }
406 }
407 }
408
409 void *
mu_opool_dup(mu_opool_t pool,void const * data,size_t size)410 mu_opool_dup (mu_opool_t pool, void const *data, size_t size)
411 {
412 if (mu_opool_append (pool, data, size))
413 return NULL;
414 return mu_opool_finish (pool, NULL);
415 }
416
417 int
mu_opool_union(mu_opool_t * pdst,mu_opool_t * psrc)418 mu_opool_union (mu_opool_t *pdst, mu_opool_t *psrc)
419 {
420 mu_opool_t src, dst;
421
422 if (!psrc)
423 return EINVAL;
424 if (!*psrc)
425 return 0;
426 src = *psrc;
427
428 if (!pdst)
429 return EINVAL;
430 if (!*pdst)
431 {
432 *pdst = src;
433 *psrc = NULL;
434 return 0;
435 }
436 else
437 dst = *pdst;
438
439 if (dst->bkt_tail)
440 dst->bkt_tail->hdr.next = src->bkt_head;
441 else
442 dst->bkt_head = src->bkt_head;
443 dst->bkt_tail = src->bkt_tail;
444
445 if (src->bkt_fini)
446 {
447 union mu_opool_bucket *p;
448
449 for (p = src->bkt_fini; p->hdr.next; p = p->hdr.next)
450 ;
451 p->hdr.next = dst->bkt_fini;
452 dst->bkt_fini = src->bkt_fini;
453 }
454
455 free (src);
456 *psrc = NULL;
457 return 0;
458 }
459
460
461 /* Iterator support */
462 struct opool_iterator
463 {
464 mu_opool_t opool;
465 union mu_opool_bucket *cur;
466 };
467
468 static int
opitr_first(void * owner)469 opitr_first (void *owner)
470 {
471 struct opool_iterator *itr = owner;
472 itr->cur = itr->opool->bkt_head;
473 return 0;
474 }
475
476 static int
opitr_next(void * owner)477 opitr_next (void *owner)
478 {
479 struct opool_iterator *itr = owner;
480 if (itr->cur)
481 {
482 itr->cur = itr->cur->hdr.next;
483 return 0;
484 }
485 return EINVAL;
486 }
487
488 static int
opitr_getitem(void * owner,void ** pret,const void ** pkey)489 opitr_getitem (void *owner, void **pret, const void **pkey)
490 {
491 struct opool_iterator *itr = owner;
492 if (!itr->cur)
493 return MU_ERR_NOENT;
494
495 *pret = itr->cur->hdr.buf;
496 if (pkey)
497 *(size_t*) pkey = itr->cur->hdr.level;
498 return 0;
499 }
500
501 static int
opitr_finished_p(void * owner)502 opitr_finished_p (void *owner)
503 {
504 struct opool_iterator *itr = owner;
505 return itr->cur == NULL;
506 }
507
508 static int
opitr_delitem(void * owner,void * item)509 opitr_delitem (void *owner, void *item)
510 {
511 struct opool_iterator *itr = owner;
512 return (itr->cur && itr->cur->hdr.buf == item) ?
513 MU_ITR_DELITEM_NEXT : MU_ITR_DELITEM_NOTHING;
514 }
515
516 static int
opitr_destroy(mu_iterator_t iterator,void * data)517 opitr_destroy (mu_iterator_t iterator, void *data)
518 {
519 struct opool_iterator *itr = data;
520 if (itr->opool->itr_count == 0)
521 {
522 /* oops! */
523 mu_error (_("%s: INTERNAL ERROR: zero reference count"),
524 "opool_destroy");
525 }
526 else
527 itr->opool->itr_count--;
528 free (data);
529 return 0;
530 }
531
532 static int
opitr_data_dup(void ** ptr,void * owner)533 opitr_data_dup (void **ptr, void *owner)
534 {
535 struct opool_iterator *itr = owner;
536
537 *ptr = malloc (sizeof (struct opool_iterator));
538 if (*ptr == NULL)
539 return ENOMEM;
540 memcpy (*ptr, owner, sizeof (struct opool_iterator));
541 itr->opool->itr_count++;
542 return 0;
543 }
544
545 static int
opitr_itrctl(void * owner,enum mu_itrctl_req req,void * arg)546 opitr_itrctl (void *owner, enum mu_itrctl_req req, void *arg)
547 {
548 struct opool_iterator *itr = owner;
549 switch (req)
550 {
551 case mu_itrctl_count:
552 if (!arg)
553 return EINVAL;
554 else
555 {
556 size_t n = 0;
557 union mu_opool_bucket *p;
558 for (p = itr->opool->bkt_head; p; p = p->hdr.next)
559 n++;
560 *(size_t*)arg = n;
561 }
562 break;
563
564 default:
565 return ENOSYS;
566 }
567 return 0;
568 }
569
570 int
mu_opool_get_iterator(mu_opool_t opool,mu_iterator_t * piterator)571 mu_opool_get_iterator (mu_opool_t opool, mu_iterator_t *piterator)
572 {
573 mu_iterator_t iterator;
574 int status;
575 struct opool_iterator *itr;
576
577 if (!opool)
578 return EINVAL;
579
580 itr = calloc (1, sizeof *itr);
581 if (!itr)
582 return ENOMEM;
583 itr->opool = opool;
584 itr->cur = opool->bkt_head;
585
586 status = mu_iterator_create (&iterator, itr);
587 if (status)
588 {
589 free (itr);
590 return status;
591 }
592
593 mu_iterator_set_first (iterator, opitr_first);
594 mu_iterator_set_next (iterator, opitr_next);
595 mu_iterator_set_getitem (iterator, opitr_getitem);
596 mu_iterator_set_finished_p (iterator, opitr_finished_p);
597 mu_iterator_set_delitem (iterator, opitr_delitem);
598 mu_iterator_set_destroy (iterator, opitr_destroy);
599 mu_iterator_set_dup (iterator, opitr_data_dup);
600 mu_iterator_set_itrctl (iterator, opitr_itrctl);
601
602 opool->itr_count++;
603
604 *piterator = iterator;
605 return 0;
606 }
607
608
609
610
611
612
613
614