Kannel: Open Source WAP and SMS gateway  $Revision: 5037 $
list.c
Go to the documentation of this file.
1 /* ====================================================================
2  * The Kannel Software License, Version 1.0
3  *
4  * Copyright (c) 2001-2016 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;
110  pthread_cond_t nonempty;
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 
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;
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 
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 
160  pthread_cond_destroy(&list->nonempty);
161  gw_free(list->tab);
162  gw_free(list);
163 }
164 
165 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
347 void gwlist_lock(List *list)
348 {
349  gw_assert(list != NULL);
350  mutex_lock(list->permanent_lock);
351 }
352 
353 
354 void gwlist_unlock(List *list)
355 {
356  gw_assert(list != NULL);
358 }
359 
360 
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);
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 
384 {
385  lock(list);
386  ++list->num_producers;
387  unlock(list);
388 }
389 
390 
392 {
393  int ret;
394  lock(list);
395  ret = list->num_producers;
396  unlock(list);
397  return ret;
398 }
399 
400 
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 
411 void gwlist_produce(List *list, void *item)
412 {
413  gwlist_append(list, item);
414 }
415 
416 
418 {
419  int ret;
420  lock(list);
421  ret = list->num_consumers;
422  unlock(list);
423  return ret;
424 }
425 
426 
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);
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 
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);
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 
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 
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 
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 
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 
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 
593 static void lock(List *list)
594 {
595  gw_assert(list != NULL);
597 }
598 
599 static void unlock(List *list)
600 {
601  gw_assert(list != NULL);
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  */
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  */
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 }
void * gwlist_search(List *list, void *pattern, int(*cmp)(void *, void *))
Definition: list.c:486
long gwlist_search_equal(List *list, void *item)
Definition: list.c:534
long num_consumers
Definition: list.c:112
static void lock(List *list)
Definition: list.c:593
#define mutex_unlock(m)
Definition: thread.h:136
void gwlist_append(List *list, void *item)
Definition: list.c:179
void gwlist_produce(List *list, void *item)
Definition: list.c:411
long gwlist_len(List *list)
Definition: list.c:166
#define mutex_create()
Definition: thread.h:96
void * gwlist_get(List *list, long pos)
Definition: list.c:292
void gwlist_sort(List *list, int(*cmp)(const void *, const void *))
Definition: list.c:576
static void quicksort(List *list, long left, long right, int(*cmp)(const void *, const void *))
Definition: list.c:552
int gwlist_wait_until_nonempty(List *list)
Definition: list.c:361
List * gwlist_extract_matching(List *list, void *pat, gwlist_item_matches_t *cmp)
Definition: list.c:322
List * gwlist_search_all(List *list, void *pattern, int(*cmp)(void *, void *))
Definition: list.c:508
void gwlist_unlock(List *list)
Definition: list.c:354
static Octstr * from
Definition: mtbatch.c:95
List * gwlist_create_real(void)
Definition: list.c:127
void gwlist_item_destructor_t(void *item)
Definition: list.h:129
int gwlist_consumer_count(List *list)
Definition: list.c:417
void * gwlist_extract_first(List *list)
Definition: list.c:305
long len
Definition: list.c:107
void gwlist_delete(List *list, long pos, long count)
Definition: list.c:232
long tab_size
Definition: list.c:105
void gwlist_remove_producer(List *list)
Definition: list.c:401
static void unlock(List *list)
Definition: list.c:599
pthread_mutex_t mutex
Definition: thread.h:77
Mutex * single_operation_lock
Definition: list.c:108
long gwlist_delete_equal(List *list, void *item)
Definition: list.c:266
static void delete_items_from_list(List *list, long pos, long count)
Definition: list.c:693
gw_assert(wtls_machine->packet_to_send!=NULL)
long gwthread_self(void)
void mutex_destroy(Mutex *mutex)
Definition: thread.c:97
void gwlist_insert(List *list, long pos, void *item)
Definition: list.c:214
void gwlist_lock(List *list)
Definition: list.c:347
long gwlist_delete_matching(List *list, void *pat, gwlist_item_matches_t *matches)
Definition: list.c:240
void gwlist_append_unique(List *list, void *item, int(*cmp)(void *, void *))
Definition: list.c:190
void * gwlist_consume(List *list)
Definition: list.c:427
pthread_cond_t nonempty
Definition: list.c:110
int gwlist_item_matches_t(void *item, void *pattern)
Definition: list.h:122
#define gwlist_create()
Definition: list.h:136
Definition: thread.h:76
long start
Definition: list.c:106
Mutex * permanent_lock
Definition: list.c:109
void ** tab
Definition: list.c:104
static void make_bigger(List *list, long items)
Definition: list.c:612
void gwlist_add_producer(List *list)
Definition: list.c:383
#define mutex_lock(m)
Definition: thread.h:130
void * gwlist_timed_consume(List *list, long sec)
Definition: list.c:453
long num_producers
Definition: list.c:111
Definition: list.c:102
long owner
Definition: thread.h:78
#define INDEX(list, i)
Definition: list.c:115
#define GET(list, i)
Definition: list.c:116
int gwlist_producer_count(List *list)
Definition: list.c:391
void gwlist_destroy(List *list, gwlist_item_destructor_t *destructor)
Definition: list.c:145
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.