1 /* ====================================================================
2 * The Kannel Software License, Version 1.0
3 *
4 * Copyright (c) 2001-2014 Kannel Group
5 * Copyright (c) 1998-2001 WapIT Ltd.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. The end-user documentation included with the redistribution,
21 * if any, must include the following acknowledgment:
22 * "This product includes software developed by the
23 * Kannel Group (http://www.kannel.org/)."
24 * Alternately, this acknowledgment may appear in the software itself,
25 * if and wherever such third-party acknowledgments normally appear.
26 *
27 * 4. The names "Kannel" and "Kannel Group" must not be used to
28 * endorse or promote products derived from this software without
29 * prior written permission. For written permission, please
30 * contact org@kannel.org.
31 *
32 * 5. Products derived from this software may not be called "Kannel",
33 * nor may "Kannel" appear in their name, without prior written
34 * permission of the Kannel Group.
35 *
36 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39 * DISCLAIMED. IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS
40 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
41 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
42 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
44 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
45 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
46 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Kannel Group. For more information on
51 * the Kannel Group, please see <http://www.kannel.org/>.
52 *
53 * Portions of this software are based upon software originally written at
54 * WapIT Ltd., Helsinki, Finland for the Kannel project.
55 */
56
57 /*
58 * list.c - generic dynamic list
59 *
60 * This module implements the generic list. See list.h for an explanation
61 * of how to use the list.
62 *
63 * The list is implemented as an array, a starting index into the array,
64 * and an integer giving the length of the list. The list's element i is
65 * not necessarily at array element i, but instead it is found at element
66 *
67 * (start + i) % len
68 *
69 * This is because we need to make it fast to use the list as a queue,
70 * meaning that adding elements to the end and removing them from the
71 * beginning must be very fast. Insertions into the middle of the list
72 * need not be fast, however. It would be possible to implement the list
73 * with a linked list, of course, but this would cause many more memory
74 * allocations: every time an item is added to the list, a new node would
75 * need to be allocated, and when it is removed, it would need to be freed.
76 * Using an array lets us reduce the number of allocations. It also lets
77 * us access an arbitrary element in constant time, which is specially
78 * useful since it lets us simplify the list API by not adding iterators
79 * or an explicit list item type.
80 *
81 * If insertions and deletions into the middle of the list become common,
82 * it would be more efficient to use a buffer gap implementation, but
83 * there's no point in doing that until the need arises.
84 *
85 * Lars Wirzenius <liw@wapit.com>
86 */
87
88 #include "gw-config.h"
89
90 #include <string.h>
91 #include <unistd.h>
92 #include <stdlib.h>
93 #include <errno.h>
94
95 #include "gwassert.h"
96 #include "list.h"
97 #include "log.h"
98 #include "thread.h"
99 #include "gwmem.h"
100
101
102 struct List
103 {
104 void **tab;
105 long tab_size;
106 long start;
107 long len;
108 Mutex *single_operation_lock;
109 Mutex *permanent_lock;
110 pthread_cond_t nonempty;
111 long num_producers;
112 long num_consumers;
113 };
114
115 #define INDEX(list, i) (((list)->start + i) % (list)->tab_size)
116 #define GET(list, i) ((list)->tab[INDEX(list, i)])
117
118
119 long gwthread_self(void);
120
121 static void lock(List *list);
122 static void unlock(List *list);
123 static void make_bigger(List *list, long items);
124 static void delete_items_from_list(List *list, long pos, long count);
125
126
gwlist_create_real(void)127 List *gwlist_create_real(void)
128 {
129 List *list;
130
131 list = gw_malloc(sizeof(List));
132 list->tab = NULL;
133 list->tab_size = 0;
134 list->start = 0;
135 list->len = 0;
136 list->single_operation_lock = mutex_create();
137 list->permanent_lock = mutex_create();
138 pthread_cond_init(&list->nonempty, NULL);
139 list->num_producers = 0;
140 list->num_consumers = 0;
141 return list;
142 }
143
144
gwlist_destroy(List * list,gwlist_item_destructor_t * destructor)145 void gwlist_destroy(List *list, gwlist_item_destructor_t *destructor)
146 {
147 long len, i;
148
149 if (list == NULL)
150 return;
151
152 if (destructor != NULL) {
153 len = gwlist_len(list); /* Using while(x != NULL) is unreliable, what if someone added NULL values? */
154 for (i = 0; i < len; i++)
155 destructor(gwlist_extract_first(list));
156 }
157
158 mutex_destroy(list->permanent_lock);
159 mutex_destroy(list->single_operation_lock);
160 pthread_cond_destroy(&list->nonempty);
161 gw_free(list->tab);
162 gw_free(list);
163 }
164
165
gwlist_len(List * list)166 long gwlist_len(List *list)
167 {
168 long len;
169
170 if (list == NULL)
171 return 0;
172 lock(list);
173 len = list->len;
174 unlock(list);
175 return len;
176 }
177
178
gwlist_append(List * list,void * item)179 void gwlist_append(List *list, void *item)
180 {
181 lock(list);
182 make_bigger(list, 1);
183 list->tab[INDEX(list, list->len)] = item;
184 ++list->len;
185 pthread_cond_signal(&list->nonempty);
186 unlock(list);
187 }
188
189
gwlist_append_unique(List * list,void * item,int (* cmp)(void *,void *))190 void gwlist_append_unique(List *list, void *item, int (*cmp)(void *, void *))
191 {
192 void *it;
193 long i;
194
195 lock(list);
196 it = NULL;
197 for (i = 0; i < list->len; ++i) {
198 it = GET(list, i);
199 if (cmp(it, item)) {
200 break;
201 }
202 }
203 if (i == list->len) {
204 /* not yet in list, so add it */
205 make_bigger(list, 1);
206 list->tab[INDEX(list, list->len)] = item;
207 ++list->len;
208 pthread_cond_signal(&list->nonempty);
209 }
210 unlock(list);
211 }
212
213
gwlist_insert(List * list,long pos,void * item)214 void gwlist_insert(List *list, long pos, void *item)
215 {
216 long i;
217
218 lock(list);
219 gw_assert(pos >= 0);
220 gw_assert(pos <= list->len);
221
222 make_bigger(list, 1);
223 for (i = list->len; i > pos; --i)
224 list->tab[INDEX(list, i)] = GET(list, i - 1);
225 list->tab[INDEX(list, pos)] = item;
226 ++list->len;
227 pthread_cond_signal(&list->nonempty);
228 unlock(list);
229 }
230
231
gwlist_delete(List * list,long pos,long count)232 void gwlist_delete(List *list, long pos, long count)
233 {
234 lock(list);
235 delete_items_from_list(list, pos, count);
236 unlock(list);
237 }
238
239
gwlist_delete_matching(List * list,void * pat,gwlist_item_matches_t * matches)240 long gwlist_delete_matching(List *list, void *pat, gwlist_item_matches_t *matches)
241 {
242 long i;
243 long count;
244
245 lock(list);
246
247 /* XXX this could be made more efficient by noticing
248 consecutive items to be removed, but leave that for later.
249 --liw */
250 i = 0;
251 count = 0;
252 while (i < list->len) {
253 if (matches(GET(list, i), pat)) {
254 delete_items_from_list(list, i, 1);
255 count++;
256 } else {
257 ++i;
258 }
259 }
260 unlock(list);
261
262 return count;
263 }
264
265
gwlist_delete_equal(List * list,void * item)266 long gwlist_delete_equal(List *list, void *item)
267 {
268 long i;
269 long count;
270
271 lock(list);
272
273 /* XXX this could be made more efficient by noticing
274 consecutive items to be removed, but leave that for later.
275 --liw */
276 i = 0;
277 count = 0;
278 while (i < list->len) {
279 if (GET(list, i) == item) {
280 delete_items_from_list(list, i, 1);
281 count++;
282 } else {
283 ++i;
284 }
285 }
286 unlock(list);
287
288 return count;
289 }
290
291
gwlist_get(List * list,long pos)292 void *gwlist_get(List *list, long pos)
293 {
294 void *item;
295
296 lock(list);
297 gw_assert(pos >= 0);
298 gw_assert(pos < list->len);
299 item = GET(list, pos);
300 unlock(list);
301 return item;
302 }
303
304
gwlist_extract_first(List * list)305 void *gwlist_extract_first(List *list)
306 {
307 void *item;
308
309 gw_assert(list != NULL);
310 lock(list);
311 if (list->len == 0)
312 item = NULL;
313 else {
314 item = GET(list, 0);
315 delete_items_from_list(list, 0, 1);
316 }
317 unlock(list);
318 return item;
319 }
320
321
gwlist_extract_matching(List * list,void * pat,gwlist_item_matches_t * cmp)322 List *gwlist_extract_matching(List *list, void *pat, gwlist_item_matches_t *cmp)
323 {
324 List *new_list;
325 long i;
326
327 new_list = gwlist_create();
328 lock(list);
329 i = 0;
330 while (i < list->len) {
331 if (cmp(GET(list, i), pat)) {
332 gwlist_append(new_list, GET(list, i));
333 delete_items_from_list(list, i, 1);
334 } else
335 ++i;
336 }
337 unlock(list);
338
339 if (gwlist_len(new_list) == 0) {
340 gwlist_destroy(new_list, NULL);
341 return NULL;
342 }
343 return new_list;
344 }
345
346
gwlist_lock(List * list)347 void gwlist_lock(List *list)
348 {
349 gw_assert(list != NULL);
350 mutex_lock(list->permanent_lock);
351 }
352
353
gwlist_unlock(List * list)354 void gwlist_unlock(List *list)
355 {
356 gw_assert(list != NULL);
357 mutex_unlock(list->permanent_lock);
358 }
359
360
gwlist_wait_until_nonempty(List * list)361 int gwlist_wait_until_nonempty(List *list)
362 {
363 int ret;
364
365 lock(list);
366 while (list->len == 0 && list->num_producers > 0) {
367 list->single_operation_lock->owner = -1;
368 pthread_cleanup_push((void(*)(void*))pthread_mutex_unlock, &list->single_operation_lock->mutex);
369 pthread_cond_wait(&list->nonempty,
370 &list->single_operation_lock->mutex);
371 list->single_operation_lock->owner = gwthread_self();
372 pthread_cleanup_pop(0);
373 }
374 if (list->len > 0)
375 ret = 1;
376 else
377 ret = -1;
378 unlock(list);
379 return ret;
380 }
381
382
gwlist_add_producer(List * list)383 void gwlist_add_producer(List *list)
384 {
385 lock(list);
386 ++list->num_producers;
387 unlock(list);
388 }
389
390
gwlist_producer_count(List * list)391 int gwlist_producer_count(List *list)
392 {
393 int ret;
394 lock(list);
395 ret = list->num_producers;
396 unlock(list);
397 return ret;
398 }
399
400
gwlist_remove_producer(List * list)401 void gwlist_remove_producer(List *list)
402 {
403 lock(list);
404 gw_assert(list->num_producers > 0);
405 --list->num_producers;
406 pthread_cond_broadcast(&list->nonempty);
407 unlock(list);
408 }
409
410
gwlist_produce(List * list,void * item)411 void gwlist_produce(List *list, void *item)
412 {
413 gwlist_append(list, item);
414 }
415
416
gwlist_consumer_count(List * list)417 int gwlist_consumer_count(List *list)
418 {
419 int ret;
420 lock(list);
421 ret = list->num_consumers;
422 unlock(list);
423 return ret;
424 }
425
426
gwlist_consume(List * list)427 void *gwlist_consume(List *list)
428 {
429 void *item;
430
431 lock(list);
432 ++list->num_consumers;
433 while (list->len == 0 && list->num_producers > 0) {
434 list->single_operation_lock->owner = -1;
435 pthread_cleanup_push((void(*)(void*))pthread_mutex_unlock, &list->single_operation_lock->mutex);
436 pthread_cond_wait(&list->nonempty,
437 &list->single_operation_lock->mutex);
438 pthread_cleanup_pop(0);
439 list->single_operation_lock->owner = gwthread_self();
440 }
441 if (list->len > 0) {
442 item = GET(list, 0);
443 delete_items_from_list(list, 0, 1);
444 } else {
445 item = NULL;
446 }
447 --list->num_consumers;
448 unlock(list);
449 return item;
450 }
451
452
gwlist_timed_consume(List * list,long sec)453 void *gwlist_timed_consume(List *list, long sec)
454 {
455 void *item;
456 struct timespec abstime;
457 int rc;
458
459 abstime.tv_sec = time(NULL) + sec;
460 abstime.tv_nsec = 0;
461
462 lock(list);
463 ++list->num_consumers;
464 while (list->len == 0 && list->num_producers > 0) {
465 list->single_operation_lock->owner = -1;
466 pthread_cleanup_push((void(*)(void*))pthread_mutex_unlock, &list->single_operation_lock->mutex);
467 rc = pthread_cond_timedwait(&list->nonempty,
468 &list->single_operation_lock->mutex, &abstime);
469 pthread_cleanup_pop(0);
470 list->single_operation_lock->owner = gwthread_self();
471 if (rc == ETIMEDOUT)
472 break;
473 }
474 if (list->len > 0) {
475 item = GET(list, 0);
476 delete_items_from_list(list, 0, 1);
477 } else {
478 item = NULL;
479 }
480 --list->num_consumers;
481 unlock(list);
482 return item;
483 }
484
485
gwlist_search(List * list,void * pattern,int (* cmp)(void *,void *))486 void *gwlist_search(List *list, void *pattern, int (*cmp)(void *, void *))
487 {
488 void *item;
489 long i;
490
491 lock(list);
492 item = NULL;
493 for (i = 0; i < list->len; ++i) {
494 item = GET(list, i);
495 if (cmp(item, pattern)) {
496 break;
497 }
498 }
499 if (i == list->len) {
500 item = NULL;
501 }
502 unlock(list);
503
504 return item;
505 }
506
507
gwlist_search_all(List * list,void * pattern,int (* cmp)(void *,void *))508 List *gwlist_search_all(List *list, void *pattern, int (*cmp)(void *, void *))
509 {
510 List *new_list;
511 void *item;
512 long i;
513
514 new_list = gwlist_create();
515
516 lock(list);
517 item = NULL;
518 for (i = 0; i < list->len; ++i) {
519 item = GET(list, i);
520 if (cmp(item, pattern))
521 gwlist_append(new_list, item);
522 }
523 unlock(list);
524
525 if (gwlist_len(new_list) == 0) {
526 gwlist_destroy(new_list, NULL);
527 new_list = NULL;
528 }
529
530 return new_list;
531 }
532
533
gwlist_search_equal(List * list,void * item)534 long gwlist_search_equal(List *list, void *item)
535 {
536 long i;
537 long ret = -1;
538
539 lock(list);
540 for (i = 0; i < list->len; i++) {
541 if (GET(list, i) == item) {
542 ret = i;
543 break;
544 }
545 }
546 unlock(list);
547
548 return ret;
549 }
550
551
quicksort(List * list,long left,long right,int (* cmp)(const void *,const void *))552 static void quicksort(List *list, long left, long right, int(*cmp)(const void *, const void *))
553 {
554 if (left < right) {
555 long l = left;
556 long r = right;
557 void *pivot = GET(list, right);
558
559 do {
560 while (cmp(GET(list, l), pivot) < 0) l++;
561 while (cmp(GET(list, r), pivot) > 0) r--;
562 if (l <= r) {
563 void *swap = GET(list, l);
564 GET(list, l) = GET(list, r);
565 GET(list, r) = swap;
566 l++;
567 r--;
568 }
569 } while(l <= r);
570
571 quicksort(list, left, r, cmp);
572 quicksort(list, l, right, cmp);
573 }
574 }
575
gwlist_sort(List * list,int (* cmp)(const void *,const void *))576 void gwlist_sort(List *list, int(*cmp)(const void *, const void *))
577 {
578 gw_assert(list != NULL && cmp != NULL);
579
580 lock(list);
581 if (list->len == 0) {
582 /* nothing to sort */
583 unlock(list);
584 return;
585 }
586 quicksort(list, 0, list->len - 1, cmp);
587 unlock(list);
588 }
589
590
591 /*************************************************************************/
592
lock(List * list)593 static void lock(List *list)
594 {
595 gw_assert(list != NULL);
596 mutex_lock(list->single_operation_lock);
597 }
598
unlock(List * list)599 static void unlock(List *list)
600 {
601 gw_assert(list != NULL);
602 mutex_unlock(list->single_operation_lock);
603 }
604
605
606 /*
607 * Make the array bigger. It might be more efficient to make the size
608 * bigger than what is explicitly requested.
609 *
610 * Assume list has been locked for a single operation already.
611 */
make_bigger(List * list,long items)612 static void make_bigger(List *list, long items)
613 {
614 long old_size, new_size;
615 long len_at_beginning, len_at_end;
616
617 if (list->len + items <= list->tab_size)
618 return;
619
620 old_size = list->tab_size;
621 new_size = old_size + items;
622 list->tab = gw_realloc(list->tab, new_size * sizeof(void *));
623 list->tab_size = new_size;
624
625 /*
626 * Now, one of the following situations is in effect
627 * (* is used, empty is unused element):
628 *
629 * Case 1: Used area did not wrap. No action is necessary.
630 *
631 * old_size new_size
632 * v v
633 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
634 * | |*|*|*|*|*|*| | | | | | | | | | | | | | | | |
635 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
636 * ^ ^
637 * start start+len
638 *
639 * Case 2: Used area wrapped, but the part at the beginning
640 * of the array fits into the new area. Action: move part
641 * from beginning to new area.
642 *
643 * old_size new_size
644 * v v
645 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
646 * |*|*| | | | | | | |*|*|*| | | | | | | | | | | |
647 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
648 * ^ ^
649 * start+len start
650 *
651 * Case 3: Used area wrapped, and the part at the beginning
652 * of the array does not fit into the new area. Action: move
653 * as much as will fit from beginning to new area and move
654 * the rest to the beginning.
655 *
656 * old_size new_size
657 * v v
658 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
659 * |*|*|*|*|*|*|*|*|*| | | | | | | | |*|*|*|*| | |
660 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
661 * ^ ^
662 * start+len start
663 */
664
665 gw_assert(list->start < old_size ||
666 (list->start == 0 && old_size == 0));
667 if (list->start + list->len > old_size) {
668 len_at_end = old_size - list->start;
669 len_at_beginning = list->len - len_at_end;
670 if (len_at_beginning <= new_size - old_size) {
671 /* This is Case 2. */
672 memmove(list->tab + old_size,
673 list->tab,
674 len_at_beginning * sizeof(void *));
675 } else {
676 /* This is Case 3. */
677 memmove(list->tab + old_size,
678 list->tab,
679 (new_size - old_size) * sizeof(void *));
680 memmove(list->tab,
681 list->tab + (new_size - old_size),
682 (len_at_beginning - (new_size - old_size))
683 * sizeof(void *));
684 }
685 }
686 }
687
688
689 /*
690 * Remove items `pos' through `pos+count-1' from list. Assume list has
691 * been locked by caller already.
692 */
delete_items_from_list(List * list,long pos,long count)693 static void delete_items_from_list(List *list, long pos, long count)
694 {
695 long i, from, to;
696
697 gw_assert(pos >= 0);
698 gw_assert(pos < list->len);
699 gw_assert(count >= 0);
700 gw_assert(pos + count <= list->len);
701
702 /*
703 * There are four cases:
704 *
705 * Case 1: Deletion at beginning of list. Just move start
706 * marker forwards (wrapping it at end of array). No need
707 * to move any items.
708 *
709 * Case 2: Deletion at end of list. Just shorten the length
710 * of the list. No need to move any items.
711 *
712 * Case 3: Deletion in the middle so that the list does not
713 * wrap in the array. Move remaining items at end of list
714 * to the place of the deletion.
715 *
716 * Case 4: Deletion in the middle so that the list does indeed
717 * wrap in the array. Move as many remaining items at the end
718 * of the list as will fit to the end of the array, then move
719 * the rest to the beginning of the array.
720 */
721 if (pos == 0) {
722 list->start = (list->start + count) % list->tab_size;
723 list->len -= count;
724 } else if (pos + count == list->len) {
725 list->len -= count;
726 } else if (list->start + list->len < list->tab_size) {
727 memmove(list->tab + list->start + pos,
728 list->tab + list->start + pos + count,
729 (list->len - pos - count) * sizeof(void *));
730 list->len -= count;
731 } else {
732 /*
733 * This is not specially efficient, but it's simple and
734 * works. Faster methods would have to take more special
735 * cases into account.
736 */
737 for (i = 0; i < list->len - count - pos; ++i) {
738 from = INDEX(list, pos + i + count);
739 to = INDEX(list, pos + i);
740 list->tab[to] = list->tab[from];
741 }
742 list->len -= count;
743 }
744 }
745