Back to index

php5  5.3.10
zend_llist.c
Go to the documentation of this file.
00001 /*
00002    +----------------------------------------------------------------------+
00003    | Zend Engine                                                          |
00004    +----------------------------------------------------------------------+
00005    | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
00006    +----------------------------------------------------------------------+
00007    | This source file is subject to version 2.00 of the Zend license,     |
00008    | that is bundled with this package in the file LICENSE, and is        | 
00009    | available through the world-wide-web at the following url:           |
00010    | http://www.zend.com/license/2_00.txt.                                |
00011    | If you did not receive a copy of the Zend license and are unable to  |
00012    | obtain it through the world-wide-web, please send a note to          |
00013    | license@zend.com so we can mail you a copy immediately.              |
00014    +----------------------------------------------------------------------+
00015    | Authors: Andi Gutmans <andi@zend.com>                                |
00016    |          Zeev Suraski <zeev@zend.com>                                |
00017    +----------------------------------------------------------------------+
00018 */
00019 
00020 /* $Id: zend_llist.c 321634 2012-01-01 13:15:04Z felipe $ */
00021 
00022 #include "zend.h"
00023 #include "zend_llist.h"
00024 #include "zend_qsort.h"
00025 
00026 ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
00027 {
00028        l->head  = NULL;
00029        l->tail  = NULL;
00030        l->count = 0;
00031        l->size  = size;
00032        l->dtor  = dtor;
00033        l->persistent = persistent;
00034 }
00035 
00036 
00037 ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
00038 {
00039        zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
00040 
00041        tmp->prev = l->tail;
00042        tmp->next = NULL;
00043        if (l->tail) {
00044               l->tail->next = tmp;
00045        } else {
00046               l->head = tmp;
00047        }
00048        l->tail = tmp;
00049        memcpy(tmp->data, element, l->size);
00050 
00051        ++l->count;
00052 }
00053 
00054 
00055 ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
00056 {
00057        zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
00058 
00059        tmp->next = l->head;
00060        tmp->prev = NULL;
00061        if (l->head) {
00062               l->head->prev = tmp;
00063        } else {
00064               l->tail = tmp;
00065        }
00066        l->head = tmp;
00067        memcpy(tmp->data, element, l->size);
00068 
00069        ++l->count;
00070 }
00071 
00072 
00073 #define DEL_LLIST_ELEMENT(current, l) \
00074                      if ((current)->prev) {\
00075                             (current)->prev->next = (current)->next;\
00076                      } else {\
00077                             (l)->head = (current)->next;\
00078                      }\
00079                      if ((current)->next) {\
00080                             (current)->next->prev = (current)->prev;\
00081                      } else {\
00082                             (l)->tail = (current)->prev;\
00083                      }\
00084                      if ((l)->dtor) {\
00085                             (l)->dtor((current)->data);\
00086                      }\
00087                      pefree((current), (l)->persistent);\
00088                      --l->count;
00089 
00090 
00091 ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
00092 {
00093        zend_llist_element *current=l->head;
00094        zend_llist_element *next;
00095 
00096        while (current) {
00097               next = current->next;
00098               if (compare(current->data, element)) {
00099                      DEL_LLIST_ELEMENT(current, l);
00100                      break;
00101               }
00102               current = next;
00103        }
00104 }
00105 
00106 
00107 ZEND_API void zend_llist_destroy(zend_llist *l)
00108 {
00109        zend_llist_element *current=l->head, *next;
00110        
00111        while (current) {
00112               next = current->next;
00113               if (l->dtor) {
00114                      l->dtor(current->data);
00115               }
00116               pefree(current, l->persistent);
00117               current = next;
00118        }
00119 
00120        l->count = 0;
00121 }
00122 
00123 
00124 ZEND_API void zend_llist_clean(zend_llist *l)
00125 {
00126        zend_llist_destroy(l);
00127        l->head = l->tail = NULL;
00128 }
00129 
00130 
00131 ZEND_API void *zend_llist_remove_tail(zend_llist *l)
00132 {
00133        zend_llist_element *old_tail;
00134        void *data;
00135 
00136        if ((old_tail = l->tail)) {
00137               if (old_tail->prev) {
00138                      old_tail->prev->next = NULL;
00139               } else {
00140                      l->head = NULL;
00141               }
00142         
00143               data = old_tail->data;
00144 
00145               l->tail = old_tail->prev;
00146               if (l->dtor) {
00147                      l->dtor(data);
00148               }
00149               pefree(old_tail, l->persistent);
00150 
00151               --l->count;
00152 
00153               return data;
00154        }
00155 
00156        return NULL;
00157 }
00158 
00159 
00160 ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
00161 {
00162        zend_llist_element *ptr;
00163 
00164        zend_llist_init(dst, src->size, src->dtor, src->persistent);
00165        ptr = src->head;
00166        while (ptr) {
00167               zend_llist_add_element(dst, ptr->data);
00168               ptr = ptr->next;
00169        }
00170 }
00171 
00172 
00173 ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
00174 {
00175        zend_llist_element *element, *next;
00176 
00177        element=l->head;
00178        while (element) {
00179               next = element->next;
00180               if (func(element->data)) {
00181                      DEL_LLIST_ELEMENT(element, l);
00182               }
00183               element = next;
00184        }
00185 }
00186 
00187 
00188 ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
00189 {
00190        zend_llist_element *element;
00191 
00192        for (element=l->head; element; element=element->next) {
00193               func(element->data TSRMLS_CC);
00194        }
00195 }
00196 
00197 ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
00198 {
00199        size_t i;
00200 
00201        zend_llist_element **elements;
00202        zend_llist_element *element, **ptr;
00203 
00204        if (l->count <= 0) {
00205               return;
00206        }
00207 
00208        elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
00209 
00210        ptr = &elements[0];
00211 
00212        for (element=l->head; element; element=element->next) {
00213               *ptr++ = element;
00214        }
00215 
00216        zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
00217 
00218        l->head = elements[0];
00219        elements[0]->prev = NULL;
00220 
00221        for (i = 1; i < l->count; i++) {
00222               elements[i]->prev = elements[i-1];
00223               elements[i-1]->next = elements[i];
00224        }
00225        elements[i-1]->next = NULL;
00226        l->tail = elements[i-1];
00227        efree(elements);
00228 }
00229 
00230 
00231 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC)
00232 {
00233        zend_llist_element *element;
00234 
00235        for (element=l->head; element; element=element->next) {
00236               func(element->data, arg TSRMLS_CC);
00237        }
00238 }
00239 
00240 
00241 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...)
00242 {
00243        zend_llist_element *element;
00244        va_list args;
00245 
00246        va_start(args, num_args);
00247        for (element=l->head; element; element=element->next) {
00248               func(element->data, num_args, args TSRMLS_CC);
00249        }
00250        va_end(args);
00251 }
00252 
00253 
00254 ZEND_API int zend_llist_count(zend_llist *l)
00255 {
00256        return l->count;
00257 }
00258 
00259 
00260 ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
00261 {
00262        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
00263 
00264        *current = l->head;
00265        if (*current) {
00266               return (*current)->data;
00267        } else {
00268               return NULL;
00269        }
00270 }
00271 
00272 
00273 ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
00274 {
00275        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
00276 
00277        *current = l->tail;
00278        if (*current) {
00279               return (*current)->data;
00280        } else {
00281               return NULL;
00282        }
00283 }
00284 
00285 
00286 ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
00287 {
00288        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
00289 
00290        if (*current) {
00291               *current = (*current)->next;
00292               if (*current) {
00293                      return (*current)->data;
00294               }
00295        }
00296        return NULL;
00297 }
00298 
00299 
00300 ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
00301 {
00302        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
00303 
00304        if (*current) {
00305               *current = (*current)->prev;
00306               if (*current) {
00307                      return (*current)->data;
00308               }
00309        }
00310        return NULL;
00311 }
00312 
00313 /*
00314  * Local variables:
00315  * tab-width: 4
00316  * c-basic-offset: 4
00317  * indent-tabs-mode: t
00318  * End:
00319  */