root/Zend/zend_llist.c

DEFINITIONS

1. zend_llist_init
2. zend_llist_add_element
3. zend_llist_prepend_element
4. zend_llist_del_element
5. zend_llist_destroy
6. zend_llist_clean
7. zend_llist_remove_tail
8. zend_llist_copy
9. zend_llist_apply_with_del
10. zend_llist_apply
11. zend_llist_swap
12. zend_llist_sort
13. zend_llist_apply_with_argument
14. zend_llist_apply_with_arguments
15. zend_llist_count
16. zend_llist_get_first_ex
17. zend_llist_get_last_ex
18. zend_llist_get_next_ex
19. zend_llist_get_prev_ex

   1 /*
   2    +----------------------------------------------------------------------+
   3    | Zend Engine                                                          |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 1998-2016 Zend Technologies Ltd. (http://www.zend.com) |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 2.00 of the Zend license,     |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.zend.com/license/2_00.txt.                                |
  11    | If you did not receive a copy of the Zend license and are unable to  |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@zend.com so we can mail you a copy immediately.              |
  14    +----------------------------------------------------------------------+
  15    | Authors: Andi Gutmans <andi@zend.com>                                |
  16    |          Zeev Suraski <zeev@zend.com>                                |
  17    +----------------------------------------------------------------------+
  18 */
  19 
  20 /* $Id$ */
  21 
  22 #include "zend.h"
  23 #include "zend_llist.h"
  24 #include "zend_sort.h"
  25 
  26 ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
  27 {
  28         l->head  = NULL;
  29         l->tail  = NULL;
  30         l->count = 0;
  31         l->size  = size;
  32         l->dtor  = dtor;
  33         l->persistent = persistent;
  34 }
  35 
  36 ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
  37 {
  38         zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
  39 
  40         tmp->prev = l->tail;
  41         tmp->next = NULL;
  42         if (l->tail) {
  43                 l->tail->next = tmp;
  44         } else {
  45                 l->head = tmp;
  46         }
  47         l->tail = tmp;
  48         memcpy(tmp->data, element, l->size);
  49 
  50         ++l->count;
  51 }
  52 
  53 
  54 ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
  55 {
  56         zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
  57 
  58         tmp->next = l->head;
  59         tmp->prev = NULL;
  60         if (l->head) {
  61                 l->head->prev = tmp;
  62         } else {
  63                 l->tail = tmp;
  64         }
  65         l->head = tmp;
  66         memcpy(tmp->data, element, l->size);
  67 
  68         ++l->count;
  69 }
  70 
  71 
  72 #define DEL_LLIST_ELEMENT(current, l) \
  73                         if ((current)->prev) {\
  74                                 (current)->prev->next = (current)->next;\
  75                         } else {\
  76                                 (l)->head = (current)->next;\
  77                         }\
  78                         if ((current)->next) {\
  79                                 (current)->next->prev = (current)->prev;\
  80                         } else {\
  81                                 (l)->tail = (current)->prev;\
  82                         }\
  83                         if ((l)->dtor) {\
  84                                 (l)->dtor((current)->data);\
  85                         }\
  86                         pefree((current), (l)->persistent);\
  87                         --l->count;
  88 
  89 
  90 ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
  91 {
  92         zend_llist_element *current=l->head;
  93 
  94         while (current) {
  95                 if (compare(current->data, element)) {
  96                         DEL_LLIST_ELEMENT(current, l);
  97                         break;
  98                 }
  99                 current = current->next;
 100         }
 101 }
 102 
 103 
 104 ZEND_API void zend_llist_destroy(zend_llist *l)
 105 {
 106         zend_llist_element *current=l->head, *next;
 107 
 108         while (current) {
 109                 next = current->next;
 110                 if (l->dtor) {
 111                         l->dtor(current->data);
 112                 }
 113                 pefree(current, l->persistent);
 114                 current = next;
 115         }
 116 
 117         l->count = 0;
 118 }
 119 
 120 
 121 ZEND_API void zend_llist_clean(zend_llist *l)
 122 {
 123         zend_llist_destroy(l);
 124         l->head = l->tail = NULL;
 125 }
 126 
 127 
 128 ZEND_API void zend_llist_remove_tail(zend_llist *l)
 129 {
 130         zend_llist_element *old_tail = l->tail;
 131         if (!old_tail) {
 132                 return;
 133         }
 134 
 135         if (old_tail->prev) {
 136                 old_tail->prev->next = NULL;
 137         } else {
 138                 l->head = NULL;
 139         }
 140 
 141         l->tail = old_tail->prev;
 142         --l->count;
 143 
 144         if (l->dtor) {
 145                 l->dtor(old_tail->data);
 146         }
 147         pefree(old_tail, l->persistent);
 148 }
 149 
 150 
 151 ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
 152 {
 153         zend_llist_element *ptr;
 154 
 155         zend_llist_init(dst, src->size, src->dtor, src->persistent);
 156         ptr = src->head;
 157         while (ptr) {
 158                 zend_llist_add_element(dst, ptr->data);
 159                 ptr = ptr->next;
 160         }
 161 }
 162 
 163 
 164 ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
 165 {
 166         zend_llist_element *element, *next;
 167 
 168         element=l->head;
 169         while (element) {
 170                 next = element->next;
 171                 if (func(element->data)) {
 172                         DEL_LLIST_ELEMENT(element, l);
 173                 }
 174                 element = next;
 175         }
 176 }
 177 
 178 
 179 ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
 180 {
 181         zend_llist_element *element;
 182 
 183         for (element=l->head; element; element=element->next) {
 184                 func(element->data);
 185         }
 186 }
 187 
 188 static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)
 189 {
 190         zend_llist_element *t;
 191         t = *p;
 192         *p = *q;
 193         *q = t;
 194 }
 195 
 196 ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
 197 {
 198         size_t i;
 199 
 200         zend_llist_element **elements;
 201         zend_llist_element *element, **ptr;
 202 
 203         if (l->count <= 0) {
 204                 return;
 205         }
 206 
 207         elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
 208 
 209         ptr = &elements[0];
 210 
 211         for (element=l->head; element; element=element->next) {
 212                 *ptr++ = element;
 213         }
 214 
 215         zend_sort(elements, l->count, sizeof(zend_llist_element *),
 216                         (compare_func_t) comp_func, (swap_func_t) zend_llist_swap);
 217 
 218         l->head = elements[0];
 219         elements[0]->prev = NULL;
 220 
 221         for (i = 1; i < l->count; i++) {
 222                 elements[i]->prev = elements[i-1];
 223                 elements[i-1]->next = elements[i];
 224         }
 225         elements[i-1]->next = NULL;
 226         l->tail = elements[i-1];
 227         efree(elements);
 228 }
 229 
 230 
 231 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg)
 232 {
 233         zend_llist_element *element;
 234 
 235         for (element=l->head; element; element=element->next) {
 236                 func(element->data, arg);
 237         }
 238 }
 239 
 240 
 241 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)
 242 {
 243         zend_llist_element *element;
 244         va_list args;
 245 
 246         va_start(args, num_args);
 247         for (element=l->head; element; element=element->next) {
 248                 func(element->data, num_args, args);
 249         }
 250         va_end(args);
 251 }
 252 
 253 
 254 ZEND_API size_t zend_llist_count(zend_llist *l)
 255 {
 256         return l->count;
 257 }
 258 
 259 
 260 ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
 261 {
 262         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 263 
 264         *current = l->head;
 265         if (*current) {
 266                 return (*current)->data;
 267         } else {
 268                 return NULL;
 269         }
 270 }
 271 
 272 
 273 ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
 274 {
 275         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 276 
 277         *current = l->tail;
 278         if (*current) {
 279                 return (*current)->data;
 280         } else {
 281                 return NULL;
 282         }
 283 }
 284 
 285 
 286 ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
 287 {
 288         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 289 
 290         if (*current) {
 291                 *current = (*current)->next;
 292                 if (*current) {
 293                         return (*current)->data;
 294                 }
 295         }
 296         return NULL;
 297 }
 298 
 299 
 300 ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
 301 {
 302         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 303 
 304         if (*current) {
 305                 *current = (*current)->prev;
 306                 if (*current) {
 307                         return (*current)->data;
 308                 }
 309         }
 310         return NULL;
 311 }
 312 
 313 /*
 314  * Local variables:
 315  * tab-width: 4
 316  * c-basic-offset: 4
 317  * indent-tabs-mode: t
 318  * End:
 319  */