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_sort
12. zend_llist_apply_with_argument
13. zend_llist_apply_with_arguments
14. zend_llist_count
15. zend_llist_get_first_ex
16. zend_llist_get_last_ex
17. zend_llist_get_next_ex
18. 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_qsort.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 
  37 ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
  38 {
  39         zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
  40 
  41         tmp->prev = l->tail;
  42         tmp->next = NULL;
  43         if (l->tail) {
  44                 l->tail->next = tmp;
  45         } else {
  46                 l->head = tmp;
  47         }
  48         l->tail = tmp;
  49         memcpy(tmp->data, element, l->size);
  50 
  51         ++l->count;
  52 }
  53 
  54 
  55 ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
  56 {
  57         zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
  58 
  59         tmp->next = l->head;
  60         tmp->prev = NULL;
  61         if (l->head) {
  62                 l->head->prev = tmp;
  63         } else {
  64                 l->tail = tmp;
  65         }
  66         l->head = tmp;
  67         memcpy(tmp->data, element, l->size);
  68 
  69         ++l->count;
  70 }
  71 
  72 
  73 #define DEL_LLIST_ELEMENT(current, l) \
  74                         if ((current)->prev) {\
  75                                 (current)->prev->next = (current)->next;\
  76                         } else {\
  77                                 (l)->head = (current)->next;\
  78                         }\
  79                         if ((current)->next) {\
  80                                 (current)->next->prev = (current)->prev;\
  81                         } else {\
  82                                 (l)->tail = (current)->prev;\
  83                         }\
  84                         if ((l)->dtor) {\
  85                                 (l)->dtor((current)->data);\
  86                         }\
  87                         pefree((current), (l)->persistent);\
  88                         --l->count;
  89 
  90 
  91 ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
  92 {
  93         zend_llist_element *current=l->head;
  94 
  95         while (current) {
  96                 if (compare(current->data, element)) {
  97                         DEL_LLIST_ELEMENT(current, l);
  98                         break;
  99                 }
 100                 current = current->next;
 101         }
 102 }
 103 
 104 
 105 ZEND_API void zend_llist_destroy(zend_llist *l)
 106 {
 107         zend_llist_element *current=l->head, *next;
 108         
 109         while (current) {
 110                 next = current->next;
 111                 if (l->dtor) {
 112                         l->dtor(current->data);
 113                 }
 114                 pefree(current, l->persistent);
 115                 current = next;
 116         }
 117 
 118         l->count = 0;
 119 }
 120 
 121 
 122 ZEND_API void zend_llist_clean(zend_llist *l)
 123 {
 124         zend_llist_destroy(l);
 125         l->head = l->tail = NULL;
 126 }
 127 
 128 
 129 ZEND_API void *zend_llist_remove_tail(zend_llist *l)
 130 {
 131         zend_llist_element *old_tail;
 132         void *data;
 133 
 134         if ((old_tail = l->tail)) {
 135                 if (old_tail->prev) {
 136                         old_tail->prev->next = NULL;
 137                 } else {
 138                         l->head = NULL;
 139                 }
 140         
 141                 data = old_tail->data;
 142 
 143                 l->tail = old_tail->prev;
 144                 if (l->dtor) {
 145                         l->dtor(data);
 146                 }
 147                 pefree(old_tail, l->persistent);
 148 
 149                 --l->count;
 150 
 151                 return data;
 152         }
 153 
 154         return NULL;
 155 }
 156 
 157 
 158 ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
 159 {
 160         zend_llist_element *ptr;
 161 
 162         zend_llist_init(dst, src->size, src->dtor, src->persistent);
 163         ptr = src->head;
 164         while (ptr) {
 165                 zend_llist_add_element(dst, ptr->data);
 166                 ptr = ptr->next;
 167         }
 168 }
 169 
 170 
 171 ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
 172 {
 173         zend_llist_element *element, *next;
 174 
 175         element=l->head;
 176         while (element) {
 177                 next = element->next;
 178                 if (func(element->data)) {
 179                         DEL_LLIST_ELEMENT(element, l);
 180                 }
 181                 element = next;
 182         }
 183 }
 184 
 185 
 186 ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
 187 {
 188         zend_llist_element *element;
 189 
 190         for (element=l->head; element; element=element->next) {
 191                 func(element->data TSRMLS_CC);
 192         }
 193 }
 194 
 195 ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
 196 {
 197         size_t i;
 198 
 199         zend_llist_element **elements;
 200         zend_llist_element *element, **ptr;
 201 
 202         if (l->count <= 0) {
 203                 return;
 204         }
 205 
 206         elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
 207 
 208         ptr = &elements[0];
 209 
 210         for (element=l->head; element; element=element->next) {
 211                 *ptr++ = element;
 212         }
 213 
 214         zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
 215 
 216         l->head = elements[0];
 217         elements[0]->prev = NULL;
 218 
 219         for (i = 1; i < l->count; i++) {
 220                 elements[i]->prev = elements[i-1];
 221                 elements[i-1]->next = elements[i];
 222         }
 223         elements[i-1]->next = NULL;
 224         l->tail = elements[i-1];
 225         efree(elements);
 226 }
 227 
 228 
 229 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC)
 230 {
 231         zend_llist_element *element;
 232 
 233         for (element=l->head; element; element=element->next) {
 234                 func(element->data, arg TSRMLS_CC);
 235         }
 236 }
 237 
 238 
 239 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...)
 240 {
 241         zend_llist_element *element;
 242         va_list args;
 243 
 244         va_start(args, num_args);
 245         for (element=l->head; element; element=element->next) {
 246                 func(element->data, num_args, args TSRMLS_CC);
 247         }
 248         va_end(args);
 249 }
 250 
 251 
 252 ZEND_API int zend_llist_count(zend_llist *l)
 253 {
 254         return l->count;
 255 }
 256 
 257 
 258 ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
 259 {
 260         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 261 
 262         *current = l->head;
 263         if (*current) {
 264                 return (*current)->data;
 265         } else {
 266                 return NULL;
 267         }
 268 }
 269 
 270 
 271 ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
 272 {
 273         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 274 
 275         *current = l->tail;
 276         if (*current) {
 277                 return (*current)->data;
 278         } else {
 279                 return NULL;
 280         }
 281 }
 282 
 283 
 284 ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
 285 {
 286         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 287 
 288         if (*current) {
 289                 *current = (*current)->next;
 290                 if (*current) {
 291                         return (*current)->data;
 292                 }
 293         }
 294         return NULL;
 295 }
 296 
 297 
 298 ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
 299 {
 300         zend_llist_position *current = pos ? pos : &l->traverse_ptr;
 301 
 302         if (*current) {
 303                 *current = (*current)->prev;
 304                 if (*current) {
 305                         return (*current)->data;
 306                 }
 307         }
 308         return NULL;
 309 }
 310 
 311 /*
 312  * Local variables:
 313  * tab-width: 4
 314  * c-basic-offset: 4
 315  * indent-tabs-mode: t
 316  * End:
 317  */