Annotation of embedaddon/php/Zend/zend_llist.c, revision 1.1.1.3

1.1       misho       1: /*
                      2:    +----------------------------------------------------------------------+
                      3:    | Zend Engine                                                          |
                      4:    +----------------------------------------------------------------------+
1.1.1.3 ! misho       5:    | Copyright (c) 1998-2013 Zend Technologies Ltd. (http://www.zend.com) |
1.1       misho       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: 
1.1.1.2   misho      20: /* $Id$ */
1.1       misho      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:        zend_llist_element *next;
                     95: 
                     96:        while (current) {
                     97:                next = current->next;
                     98:                if (compare(current->data, element)) {
                     99:                        DEL_LLIST_ELEMENT(current, l);
                    100:                        break;
                    101:                }
                    102:                current = next;
                    103:        }
                    104: }
                    105: 
                    106: 
                    107: ZEND_API void zend_llist_destroy(zend_llist *l)
                    108: {
                    109:        zend_llist_element *current=l->head, *next;
                    110:        
                    111:        while (current) {
                    112:                next = current->next;
                    113:                if (l->dtor) {
                    114:                        l->dtor(current->data);
                    115:                }
                    116:                pefree(current, l->persistent);
                    117:                current = next;
                    118:        }
                    119: 
                    120:        l->count = 0;
                    121: }
                    122: 
                    123: 
                    124: ZEND_API void zend_llist_clean(zend_llist *l)
                    125: {
                    126:        zend_llist_destroy(l);
                    127:        l->head = l->tail = NULL;
                    128: }
                    129: 
                    130: 
                    131: ZEND_API void *zend_llist_remove_tail(zend_llist *l)
                    132: {
                    133:        zend_llist_element *old_tail;
                    134:        void *data;
                    135: 
                    136:        if ((old_tail = l->tail)) {
                    137:                if (old_tail->prev) {
                    138:                        old_tail->prev->next = NULL;
                    139:                } else {
                    140:                        l->head = NULL;
                    141:                }
                    142:         
                    143:                data = old_tail->data;
                    144: 
                    145:                l->tail = old_tail->prev;
                    146:                if (l->dtor) {
                    147:                        l->dtor(data);
                    148:                }
                    149:                pefree(old_tail, l->persistent);
                    150: 
                    151:                --l->count;
                    152: 
                    153:                return data;
                    154:        }
                    155: 
                    156:        return NULL;
                    157: }
                    158: 
                    159: 
                    160: ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
                    161: {
                    162:        zend_llist_element *ptr;
                    163: 
                    164:        zend_llist_init(dst, src->size, src->dtor, src->persistent);
                    165:        ptr = src->head;
                    166:        while (ptr) {
                    167:                zend_llist_add_element(dst, ptr->data);
                    168:                ptr = ptr->next;
                    169:        }
                    170: }
                    171: 
                    172: 
                    173: ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
                    174: {
                    175:        zend_llist_element *element, *next;
                    176: 
                    177:        element=l->head;
                    178:        while (element) {
                    179:                next = element->next;
                    180:                if (func(element->data)) {
                    181:                        DEL_LLIST_ELEMENT(element, l);
                    182:                }
                    183:                element = next;
                    184:        }
                    185: }
                    186: 
                    187: 
                    188: ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
                    189: {
                    190:        zend_llist_element *element;
                    191: 
                    192:        for (element=l->head; element; element=element->next) {
                    193:                func(element->data TSRMLS_CC);
                    194:        }
                    195: }
                    196: 
                    197: ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
                    198: {
                    199:        size_t i;
                    200: 
                    201:        zend_llist_element **elements;
                    202:        zend_llist_element *element, **ptr;
                    203: 
                    204:        if (l->count <= 0) {
                    205:                return;
                    206:        }
                    207: 
                    208:        elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
                    209: 
                    210:        ptr = &elements[0];
                    211: 
                    212:        for (element=l->head; element; element=element->next) {
                    213:                *ptr++ = element;
                    214:        }
                    215: 
                    216:        zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
                    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 TSRMLS_DC)
                    232: {
                    233:        zend_llist_element *element;
                    234: 
                    235:        for (element=l->head; element; element=element->next) {
                    236:                func(element->data, arg TSRMLS_CC);
                    237:        }
                    238: }
                    239: 
                    240: 
                    241: ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, 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 TSRMLS_CC);
                    249:        }
                    250:        va_end(args);
                    251: }
                    252: 
                    253: 
                    254: ZEND_API int 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:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>