1 /* darray.c -- dynamic arrays handling
2
3 Copyright (c) 1996-99 Akim Demaille, Miguel Santana
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
8 any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
18
19 /* Author: Akim Demaille <demaille@inf.enst.fr> */
20
21 #include <system.h>
22
23 #include "darray.h"
24
25 int da_exit_error = 1; /* exit value when encounters *
26 * an error */
27
28 #define QSORT_INSERT_SORT_LIMIT 37 /* Bellow, insert sort is used */
29 #define QSORT_STACK 100
30 #define DA_SWAP(a,i,j) \
31 do { \
32 tmp = a->content [i]; \
33 a->content [i] = a->content [j]; \
34 a->content [j] = tmp ; \
35 } while (0)
36
37 /*
38 * Create a dynamic array
39 */
40 struct darray *
da_new(const char * name,size_t size,enum da_growth growth,size_t increment,da_print_func_t self_print,da_cmp_func_t cmp)41 da_new (const char * name, size_t size,
42 enum da_growth growth, size_t increment,
43 da_print_func_t self_print,
44 da_cmp_func_t cmp)
45 {
46 struct darray * res;
47
48 /* No longer relevant: size_t cannot be null */
49 if (size == 0)
50 error (da_exit_error, 0, "invalid size for dynamic array `%s': %d",
51 name, size);
52 if (increment == 0 && growth != da_steady)
53 error (da_exit_error, 0, "invalid increment for dynamic array `%s': %d",
54 name, increment);
55
56 res = XMALLOC (struct darray, 1);
57 res->name = name;
58 res->original_size = size;
59 res->size = size;
60 res->content = XCALLOC (void *, res->size);
61 res->growth = growth;
62 res->increment = increment;
63 res->len = 0;
64
65 /* Routines */
66 res->self_print = self_print;
67 res->cmp = cmp;
68
69 return res;
70 }
71
72 static inline void
_da_erase(struct darray * arr)73 _da_erase (struct darray * arr)
74 {
75 if (arr) {
76 XFREE (arr->content);
77 free (arr);
78 }
79 }
80
81 void
da_erase(struct darray * arr)82 da_erase (struct darray * arr)
83 {
84 _da_erase (arr);
85 }
86
87 /*
88 * Set length of ARR to 0, and free with FREE_FUNC if non NULL
89 */
90 static inline void
_da_free_content(struct darray * arr,da_map_func_t free_func)91 _da_free_content (struct darray * arr, da_map_func_t free_func)
92 {
93 size_t i;
94
95 if (free_func)
96 for (i = 0 ; i < arr->len ; i++)
97 (*free_func) (arr->content [i]);
98
99 arr->len = 0;
100 }
101
102 void
da_free_content(struct darray * arr,da_map_func_t free_func)103 da_free_content (struct darray * arr, da_map_func_t free_func)
104 {
105 _da_free_content (arr, free_func);
106 }
107
108 /*
109 * Set length of ARR to 0, and free with FREE_FUNC if non NULL
110 * and free the structure
111 */
112 void
da_free(struct darray * arr,da_map_func_t free_func)113 da_free (struct darray * arr, da_map_func_t free_func)
114 {
115 _da_free_content (arr, free_func);
116 _da_erase (arr);
117 }
118
119 /*
120 * Report the status of the array
121 */
122 void
da_print_stats(struct darray * arr,FILE * stream)123 da_print_stats (struct darray * arr, FILE * stream)
124 {
125 const char * cp = NULL;
126
127 fprintf (stream, _("Dynamic array `%s':\n"), arr->name);
128 fprintf (stream, _("\tload: %d/%d (%2.1f%%)\n"),
129 arr->len, arr->size, 100.0 * arr->len / arr->size);
130 switch (arr->growth) {
131 case da_steady:
132 /* growth is steady, i.e., it cannot grow, it is constant */
133 cp = "[const]";
134 break;
135 case da_linear:
136 /* growth is linear. eg. 2, 4, 6, 8 */
137 cp = "+=";
138 break;
139 case da_geometrical:
140 /* growth is exponential. eg. 2, 4, 8, 16 */
141 cp = "*=";
142 break;
143 default:
144 abort ();
145 }
146 fprintf (stream, _("\toriginal size: %d, growth: %s %d\n"),
147 arr->original_size, cp, arr->increment);
148 }
149
150 /*
151 * Resize, unless too small to fit
152 */
153 void
da_resize(struct darray * arr,size_t size)154 da_resize (struct darray * arr, size_t size)
155 {
156 if (arr->len + 1 < size)
157 {
158 arr->size = size;
159 arr->content = XREALLOC (arr->content, void *, arr->size);
160 }
161 }
162
163 /*
164 * Make a dyn. array bigger
165 */
166 void
da_grow(struct darray * arr)167 da_grow (struct darray * arr)
168 {
169 switch (arr->growth) {
170 case da_steady:
171 return;
172
173 case da_linear:
174 arr->size += arr->increment;
175 break;
176
177 case da_geometrical:
178 arr->size *= arr->increment;
179 break;
180
181 default:
182 abort ();
183 }
184 arr->content = XREALLOC (arr->content, void *, arr->size);
185 }
186
187 /*
188 * Make a clone
189 */
190 struct darray *
da_clone(struct darray * array)191 da_clone (struct darray * array)
192 {
193 struct darray * res;
194 res = CLONE (array);
195 res->content = CCLONE (array->content, array->len);
196 return res;
197 }
198
199
200 /*
201 * Is it sorted?
202 */
203 int
da_is_sorted(struct darray * arr)204 da_is_sorted (struct darray * arr)
205 {
206 size_t i;
207
208 for (i = 1 ; i < arr->len ; i++)
209 if (arr->cmp (arr->content [i], arr->content [i - 1]) < 0)
210 return 0;
211 return 1;
212 }
213
214 /*
215 * Are two darray equal (pointer-wise)?
216 */
217 int
da_equal(struct darray * ar1,struct darray * ar2)218 da_equal (struct darray * ar1, struct darray * ar2)
219 {
220 size_t i;
221
222 if (ar1->len != ar2->len)
223 return 0;
224
225 for (i = 0 ; i< ar1->len ; i++)
226 if (ar1->content [i] != ar2->content [i])
227 return 0;
228 return 1;
229 }
230
231 /*
232 * Do two arrays have same semantics (wrt cmp) content?
233 * (ar1->cmp is used for the comparison)
234 */
235 int
da_cmp_equal(struct darray * ar1,struct darray * ar2)236 da_cmp_equal (struct darray * ar1, struct darray * ar2)
237 {
238 size_t i;
239
240 if (ar1->len != ar2->len)
241 return 0;
242
243 for (i = 0 ; i< ar1->len ; i++)
244 if (ar1->cmp (ar1->content [i], ar2->content [i]))
245 return 0;
246 return 1;
247 }
248
249 /*
250 * Where is STUFF in ARR (equal in the sense of self_cmp)
251 * -1 if is not in.
252 */
253 int
da_where(struct darray * arr,const void * stuff)254 da_where (struct darray * arr, const void * stuff)
255 {
256 size_t i;
257
258 for (i = 0 ; i < arr->len ; i++)
259 if (!arr->cmp (arr->content[i], stuff))
260 return (int) i;
261
262 return -1;
263 }
264
265 /*
266 * Does this stuff is selfcmp equal to an item of the darray?
267 */
268 int
da_includes(struct darray * arr,const void * stuff)269 da_includes (struct darray * arr, const void * stuff)
270 {
271 return (da_where (arr, stuff) != -1);
272 }
273
274 /*
275 * Append an element
276 */
277 void
da_append(struct darray * arr,void * elem)278 da_append (struct darray * arr, void * elem)
279 {
280 if (da_is_full (arr))
281 da_grow (arr);
282
283 arr->content [arr->len++] = elem;
284 }
285
286 /*
287 * Insert an element at a given place.
288 */
289 void
da_insert_at(struct darray * arr,void * elem,size_t where)290 da_insert_at (struct darray * arr, void * elem, size_t where)
291 {
292 size_t i;
293
294 if (where > arr->len)
295 error (da_exit_error, 0, "can't insert at %d in darray %s [0,%d]\n",
296 where, arr->name, arr->len - 1);
297
298 if (da_is_full (arr))
299 da_grow (arr);
300
301 for (i = arr->len ; where < i ; i--)
302 arr->content [i] = arr->content [i - 1];
303
304 arr->content [ where ] = elem;
305 arr->len ++;
306 }
307
308 /*
309 * Remove an element at a given place.
310 */
311 void
da_remove_at(struct darray * arr,size_t where,da_map_func_t free_func)312 da_remove_at (struct darray * arr, size_t where, da_map_func_t free_func)
313 {
314 size_t i;
315
316 if (where >= arr->len)
317 error (da_exit_error, 0, "can't remove at %d in darray %s [0,%d]\n",
318 where, arr->name, arr->len - 1);
319
320 if (free_func)
321 (*free_func) (arr->content [where]);
322
323 for (i = where + 1 ; i < arr->len ; i++)
324 arr->content [i - 1] = arr->content [i];
325
326 arr->len --;
327 }
328
329 /*
330 * Concat the second in the first
331 */
332 void
da_concat(struct darray * arr,struct darray * arr2)333 da_concat (struct darray * arr, struct darray * arr2)
334 {
335 size_t i;
336 size_t len = arr->len + arr2->len;
337
338 if (len > arr->size) {
339 arr->size = len + 1;
340 arr->content = XREALLOC (arr->content, void *, arr->size);
341 }
342
343 for (i = 0 ; i < arr2->len ; i++)
344 arr->content [arr->len++] = arr2->content[i];
345 }
346
347 /*
348 * Prefix the content of ARR by that of ARR2
349 */
350 void
da_prefix(struct darray * arr,struct darray * arr2)351 da_prefix (struct darray * arr, struct darray * arr2)
352 {
353 int i;
354 size_t len = arr->len + arr2->len;
355
356 if (len > arr->size) {
357 arr->size = len + 1;
358 arr->content = XREALLOC (arr->content, void *, arr->size);
359 }
360
361 /* Move the content of ARR */
362 for (i = (int) arr->len - 1 ; i >= 0 ; i--)
363 arr->content [ i + arr2->len ] = arr->content [ i ];
364
365 /* Copy the content of ARR2 */
366 for (i = 0 ; i < (int) arr2->len ; i++)
367 arr->content [ i ] = arr2->content[ i ];
368
369 arr->len += arr2->len;
370 }
371
372 /*
373 * Implementation of QSORT as given by Sedgewick
374 */
375 void
da_qsort(struct darray * arr)376 da_qsort (struct darray * arr)
377 {
378 int ir, j, k, l, i;
379 int jstack, *istack;
380 void * a, * tmp;
381
382 /* Do not sort an empty array */
383 if (arr->len <= 1)
384 return;
385
386 istack = XMALLOC (int, QSORT_STACK);
387 ir = arr->len - 1;
388 l = 0;
389 jstack = 0;
390
391 for (;;) {
392 if (ir - l < QSORT_INSERT_SORT_LIMIT)
393 { /* Insertion sort is then prefered */
394 for (j = l + 1 ; j <= ir ; j++) {
395 a = arr->content [j];
396 for (i = j - 1 ; i >= l ; i--) {
397 if (arr->cmp (arr->content [i], a) <= 0)
398 break;
399 arr->content [i + 1] = arr->content [i];
400 }
401 arr->content [i + 1] = a;
402 }
403 if (jstack == 0)
404 break;
405 ir = istack [jstack--];
406 l = istack [jstack--];
407 }
408 else
409 {
410 k = (l + ir) / 2;
411 DA_SWAP (arr, k, l + 1);
412 if (arr->cmp (arr->content [l], arr->content [ir]) > 0)
413 DA_SWAP (arr, l, ir);
414 if (arr->cmp (arr->content [l + 1], arr->content [ir]) > 0)
415 DA_SWAP (arr, l + 1, ir);
416 if (arr->cmp (arr->content [l], arr->content [l + 1]) > 0)
417 DA_SWAP (arr, l, l + 1);
418 i = l + 1;
419 j = ir;
420 a = arr->content [l + 1];
421 for (;;) {
422 do i++; while (arr->cmp (arr->content [i], a) < 0);
423 do j--; while (arr->cmp (arr->content [j], a) > 0);
424 if (j < i)
425 break; /* Partion is completed */
426 DA_SWAP (arr, i, j);
427 }
428 arr->content [l + 1] = arr->content [j];
429 arr->content [j] = a;
430 jstack += 2;
431 /* Push pointers to larger subarry on stack.
432 * Process smaller subarrays now */
433 if (jstack > QSORT_STACK)
434 error (da_exit_error, 0, "da_qsort: QSORT_STACK too small (%d)",
435 QSORT_STACK);
436 if (ir - i + 1 >= j - l) {
437 istack [jstack] = ir;
438 istack [jstack - 1] = i;
439 ir = j - 1;
440 } else {
441 istack [jstack] = j - 1;
442 istack [jstack - 1] = l;
443 l = i;
444 }
445 }
446 }
447 free (istack);
448 }
449
450 /*
451 * Implementation of QSORT as given by Sedgewick
452 */
453 void
da_qsort_with_arg(struct darray * arr,da_cmp_arg_func_t cmp,const void * arg)454 da_qsort_with_arg (struct darray * arr, da_cmp_arg_func_t cmp,
455 const void * arg)
456 {
457 int ir, j, k, l, i;
458 int jstack, *istack;
459 void * a, * tmp;
460
461 /* Do not sort an empty array */
462 if (arr->len <= 1)
463 return;
464
465 istack = XMALLOC (int, QSORT_STACK);
466 ir = arr->len - 1;
467 l = 0;
468 jstack = 0;
469
470 for (;;) {
471 if (ir - l < QSORT_INSERT_SORT_LIMIT)
472 { /* Insertion sort is then prefered */
473 for (j = l + 1 ; j <= ir ; j++) {
474 a = arr->content [j];
475 for (i = j - 1 ; i >= l ; i--) {
476 if (cmp (arr->content [i], a, arg) <= 0)
477 break;
478 arr->content [i + 1] = arr->content [i];
479 }
480 arr->content [i + 1] = a;
481 }
482 if (jstack == 0)
483 break;
484 ir = istack [jstack--];
485 l = istack [jstack--];
486 }
487 else
488 {
489 k = (l + ir) / 2;
490 DA_SWAP (arr, k, l + 1);
491 if (cmp (arr->content [l], arr->content [ir], arg) > 0)
492 DA_SWAP (arr, l, ir);
493 if (cmp (arr->content [l + 1], arr->content [ir], arg) > 0)
494 DA_SWAP (arr, l + 1, ir);
495 if (cmp (arr->content [l], arr->content [l + 1], arg) > 0)
496 DA_SWAP (arr, l, l + 1);
497 i = l + 1;
498 j = ir;
499 a = arr->content [l + 1];
500 for (;;) {
501 do i++; while (cmp (arr->content [i], a, arg) < 0);
502 do j--; while (cmp (arr->content [j], a, arg) > 0);
503 if (j < i)
504 break; /* Partion is completed */
505 DA_SWAP (arr, i, j);
506 }
507 arr->content [l + 1] = arr->content [j];
508 arr->content [j] = a;
509 jstack += 2;
510 /* Push pointers to larger subarry on stack.
511 * Process smaller subarrays now */
512 if (jstack > QSORT_STACK)
513 error (da_exit_error, 0, "da_qsort: QSORT_STACK too small (%d)",
514 QSORT_STACK);
515 if (ir - i + 1 >= j - l) {
516 istack [jstack] = ir;
517 istack [jstack - 1] = i;
518 ir = j - 1;
519 } else {
520 istack [jstack] = j - 1;
521 istack [jstack - 1] = l;
522 l = i;
523 }
524 }
525 }
526 free (istack);
527 }
528
529 /*
530 * Leave the first of each doubles
531 */
532 void
da_unique(struct darray * arr,da_map_func_t free_func)533 da_unique (struct darray * arr, da_map_func_t free_func)
534 {
535 size_t c;
536
537 c = 1;
538 while (c < arr->len) {
539 if (arr->cmp (arr->content [c - 1], arr->content[c]) == 0)
540 da_remove_at (arr, c, free_func);
541 else
542 c++;
543 }
544 }
545
546 /*
547 * Merge A2 into A1. Both *are sorted*.
548 * In the result there are never two equal entries
549 * (in the sense of self_cmp).
550 *
551 * In case of conflict (equal entries from the point of view
552 * of a1->cmp),
553 * - if POLICY == da_1_wins, keep that of A1
554 * - if POLICY == da_2_wins, keep that of A2
555 *
556 * If there are doubles in a1 and/or in a2, they still will be doubles
557 * in the returned result.
558 */
559 void
da_merge(struct darray * a1,struct darray * a2,da_map_func_t free_func,enum da_include_policy policy)560 da_merge (struct darray * a1, struct darray * a2,
561 da_map_func_t free_func, enum da_include_policy policy)
562 {
563 size_t c1, c2; /* Counters on a1, and a2 */
564
565 c1 = c2 = 0;
566
567 while ((c1 != a1->len) || (c2 != a2->len))
568 {
569 /* Leave what is in a1 as long as it is strictly smaller than the
570 * next item of a2 */
571 while ((c1 < a1->len)
572 && ((c2 == a2->len)
573 || (a1->cmp (a1->content [c1], a2->content [c2]) < 0)))
574 c1 ++;
575
576 /* Skip whatever appears in a1, but is in a2 too */
577 while ((c1 < a1->len) && (c2 < a2->len)
578 && (a1->cmp (a1->content [c1], a2->content [c2]) == 0))
579 if (policy == da_1_wins)
580 {
581 if (free_func)
582 da_remove_at (a2, c2, free_func);
583 else
584 c2++;
585 }
586 else
587 {
588 if (free_func)
589 da_remove_at (a1, c1, free_func);
590 else
591 c1++;
592 }
593
594 /* Take what is is a2 as long as it is smaller or equal to
595 * what appeared last in a1 */
596 while ((c2 < a2->len)
597 && ((c1 == a1->len)
598 || (a1->cmp (a1->content [c1], a2->content [c2]) >= 0)))
599 da_insert_at (a1, a2->content [c2++], c1);
600 }
601 }
602
603
604 /*
605 * Dump on stderr the content
606 */
607 void
da_self_print(struct darray * arr,FILE * stream)608 da_self_print (struct darray * arr, FILE * stream)
609 {
610 size_t i;
611
612 fprintf (stream, _("Dynamic array `%s':\n"), arr->name);
613 if (!arr->self_print)
614 abort ();
615 for (i = 0 ; i < arr->len ; i++) {
616 fprintf (stream, "[%2d] = ", i);
617 arr->self_print (arr->content [i], stream);
618 fprintf (stream, "\n");
619 }
620 }
621
622 /*
623 * For each item of ARR, call FN (ITEM)
624 */
625 void
da_map(struct darray * arr,da_map_func_t fn)626 da_map (struct darray * arr, da_map_func_t fn)
627 {
628 size_t i;
629
630 for (i = 0 ; i < arr->len ; i++)
631 (*fn) (arr->content [i]);
632 }
633
634 /*
635 * Idem, but with an argument
636 */
637 void
da_maparg(struct darray * arr,da_maparg_func_t func,void * arg)638 da_maparg (struct darray * arr, da_maparg_func_t func, void * arg)
639 {
640 size_t i;
641 for (i = 0 ; i < arr->len ; i++)
642 (*func) (arr->content [i], arg);
643 }
644
645 /*
646 * Some helping routines for special darray cases
647 */
648 /*
649 * darray of strings
650 */
651 int
da_str_cmp(const char * s1,const char * s2)652 da_str_cmp (const char * s1, const char * s2)
653 {
654 return strcmp (s1, s2);
655 }
656
657 void
da_str_print(const char * s1,FILE * stream)658 da_str_print (const char * s1, FILE * stream)
659 {
660 fputs ((const char *) s1, stream);
661 }
662
663 void
da_str_printnl(const char * s1,FILE * stream)664 da_str_printnl (const char * s1, FILE * stream)
665 {
666 fputs ((const char *) s1, stream);
667 putc ('\n', stream);
668 }
669