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

1.1     ! misho       1: /*
        !             2:    +----------------------------------------------------------------------+
        !             3:    | Zend Engine                                                          |
        !             4:    +----------------------------------------------------------------------+
        !             5:    | Copyright (c) 1998-2012 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: zend_llist.c 321634 2012-01-01 13:15:04Z felipe $ */
        !            21: 
        !            22: #include "zend.h"
        !            23: #include "zend_llist.h"
        !            24: #include "zend_qsort.h"
        !            25: 
        !            26: #if SUHOSIN_PATCH
        !            27: #ifdef ZTS
        !            28: static MUTEX_T zend_llist_dprot_mx_reader;
        !            29: static MUTEX_T zend_llist_dprot_mx_writer;
        !            30: static unsigned int zend_llist_dprot_reader;
        !            31: #endif
        !            32: static unsigned int zend_llist_dprot_counter;
        !            33: static unsigned int zend_llist_dprot_curmax;
        !            34: static llist_dtor_func_t *zend_llist_dprot_table = NULL;
        !            35: 
        !            36: static void zend_llist_dprot_begin_read()
        !            37: {
        !            38: #ifdef ZTS
        !            39:        tsrm_mutex_lock(zend_llist_dprot_mx_reader);
        !            40:        if ((++(zend_llist_dprot_reader)) == 1) {
        !            41:                tsrm_mutex_lock(zend_llist_dprot_mx_writer);
        !            42:        }
        !            43:        tsrm_mutex_unlock(zend_llist_dprot_mx_reader);
        !            44: #endif
        !            45: }
        !            46: 
        !            47: static void zend_llist_dprot_end_read()
        !            48: {
        !            49: #ifdef ZTS
        !            50:        tsrm_mutex_lock(zend_llist_dprot_mx_reader);
        !            51:        if ((--(zend_llist_dprot_reader)) == 0) {
        !            52:                tsrm_mutex_unlock(zend_llist_dprot_mx_writer);
        !            53:        }
        !            54:        tsrm_mutex_unlock(zend_llist_dprot_mx_reader);
        !            55: #endif
        !            56: }
        !            57: 
        !            58: static void zend_llist_dprot_begin_write()
        !            59: {
        !            60: #ifdef ZTS
        !            61:        tsrm_mutex_lock(zend_llist_dprot_mx_writer);
        !            62: #endif
        !            63: }
        !            64: 
        !            65: static void zend_llist_dprot_end_write()
        !            66: {
        !            67: #ifdef ZTS
        !            68:        tsrm_mutex_unlock(zend_llist_dprot_mx_writer);
        !            69: #endif
        !            70: }
        !            71: 
        !            72: /*ZEND_API void zend_llist_dprot_dtor()
        !            73: {
        !            74: #ifdef ZTS
        !            75:        tsrm_mutex_free(zend_llist_dprot_mx_reader);
        !            76:        tsrm_mutex_free(zend_llist_dprot_mx_writer);
        !            77: #endif 
        !            78:        free(zend_llist_dprot_table);
        !            79: }*/
        !            80: 
        !            81: static void zend_llist_add_destructor(llist_dtor_func_t pDestructor)
        !            82: {
        !            83:        int left, right, mid;
        !            84:        zend_bool found = 0;
        !            85:        unsigned long value;
        !            86:        
        !            87:        if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR) {
        !            88:                return;
        !            89:        }
        !            90:        
        !            91:        if (zend_llist_dprot_table == NULL) {
        !            92: #ifdef ZTS
        !            93:                zend_llist_dprot_mx_reader = tsrm_mutex_alloc();
        !            94:                zend_llist_dprot_mx_writer = tsrm_mutex_alloc();
        !            95:                zend_llist_dprot_reader = 0;
        !            96: #endif 
        !            97:                zend_llist_dprot_counter = 0;
        !            98:                zend_llist_dprot_curmax = 256;
        !            99:                zend_llist_dprot_table = (llist_dtor_func_t *) malloc(256 * sizeof(llist_dtor_func_t));
        !           100:        }
        !           101:        
        !           102:        zend_llist_dprot_begin_write();
        !           103: 
        !           104:        if (zend_llist_dprot_counter == 0) {
        !           105:                zend_llist_dprot_counter++;
        !           106:                zend_llist_dprot_table[0] = pDestructor;
        !           107:        } else {
        !           108:                value = (unsigned long) pDestructor;
        !           109:                left = 0;
        !           110:                right = zend_llist_dprot_counter-1;
        !           111:                mid = 0;
        !           112:                
        !           113:                while (left < right) {
        !           114:                        mid = (right - left) >> 1;
        !           115:                        mid += left;
        !           116:                        if ((unsigned long)zend_llist_dprot_table[mid] == value) {
        !           117:                                found = 1;
        !           118:                                break;
        !           119:                        }
        !           120:                        if (value < (unsigned long)zend_llist_dprot_table[mid]) {
        !           121:                                right = mid-1;
        !           122:                        } else {
        !           123:                                left = mid+1;
        !           124:                        }
        !           125:                }
        !           126:                if ((unsigned long)zend_llist_dprot_table[left] == value) {
        !           127:                        found = 1;
        !           128:                }
        !           129:                
        !           130:                if (!found) {
        !           131:                
        !           132:                        if (zend_llist_dprot_counter >= zend_llist_dprot_curmax) {
        !           133:                                zend_llist_dprot_curmax += 256;
        !           134:                                zend_llist_dprot_table = (llist_dtor_func_t *) realloc(zend_llist_dprot_table, zend_llist_dprot_curmax * sizeof(llist_dtor_func_t));
        !           135:                        }
        !           136:                        
        !           137:                        if ((unsigned long)zend_llist_dprot_table[left] < value) {
        !           138:                                memmove(zend_llist_dprot_table+left+2, zend_llist_dprot_table+left+1, (zend_llist_dprot_counter-left-1)*sizeof(llist_dtor_func_t));
        !           139:                                zend_llist_dprot_table[left+1] = pDestructor;
        !           140:                        } else {
        !           141:                                memmove(zend_llist_dprot_table+left+1, zend_llist_dprot_table+left, (zend_llist_dprot_counter-left)*sizeof(llist_dtor_func_t));
        !           142:                                zend_llist_dprot_table[left] = pDestructor;
        !           143:                        }
        !           144: 
        !           145:                        zend_llist_dprot_counter++;
        !           146:                }
        !           147:        }
        !           148:        
        !           149:        zend_llist_dprot_end_write();
        !           150: }
        !           151: 
        !           152: static void zend_llist_check_destructor(llist_dtor_func_t pDestructor)
        !           153: {
        !           154:        unsigned long value;
        !           155:        
        !           156:        if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR) {
        !           157:                return;
        !           158:        }
        !           159: 
        !           160:        zend_llist_dprot_begin_read();
        !           161:        
        !           162:        if (zend_llist_dprot_counter > 0) {
        !           163:                int left, right, mid;
        !           164:                zend_bool found = 0;
        !           165:        
        !           166:                value = (unsigned long) pDestructor;
        !           167:                left = 0;
        !           168:                right = zend_llist_dprot_counter-1;
        !           169:                
        !           170:                while (left < right) {
        !           171:                        mid = (right - left) >> 1;
        !           172:                        mid += left;
        !           173:                        if ((unsigned long)zend_llist_dprot_table[mid] == value) {
        !           174:                                found = 1;
        !           175:                                break;
        !           176:                        }
        !           177:                        if (value < (unsigned long)zend_llist_dprot_table[mid]) {
        !           178:                                right = mid-1;
        !           179:                        } else {
        !           180:                                left = mid+1;
        !           181:                        }
        !           182:                }
        !           183:                if ((unsigned long)zend_llist_dprot_table[left] == value) {
        !           184:                        found = 1;
        !           185:                }
        !           186:                
        !           187:                if (!found) {
        !           188:                        zend_llist_dprot_end_read();
        !           189:                
        !           190:                        zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown llist destructor");
        !           191:                        if (SUHOSIN_CONFIG(SUHOSIN_LL_IGNORE_INVALID_DESTRUCTOR) == 0) {
        !           192:                                _exit(1);
        !           193:                        }
        !           194:                        return;
        !           195:                }
        !           196:        
        !           197:        } else {
        !           198:                zend_llist_dprot_end_read();
        !           199:        
        !           200:                zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown llist destructor");
        !           201:                if (SUHOSIN_CONFIG(SUHOSIN_LL_IGNORE_INVALID_DESTRUCTOR) == 0) {
        !           202:                        _exit(1);
        !           203:                }
        !           204:                return;         
        !           205:        }
        !           206:        
        !           207:        zend_llist_dprot_end_read();
        !           208: }
        !           209: #else
        !           210: #define zend_llist_add_destructor(pDestructor) do {} while(0)
        !           211: #define zend_llist_check_destructor(pDestructor) do {} while(0)
        !           212: #endif
        !           213: 
        !           214: ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
        !           215: {
        !           216:        l->head  = NULL;
        !           217:        l->tail  = NULL;
        !           218:        l->count = 0;
        !           219:        l->size  = size;
        !           220:        l->dtor  = dtor;
        !           221:        zend_llist_add_destructor(dtor);
        !           222:        l->persistent = persistent;
        !           223: }
        !           224: 
        !           225: 
        !           226: ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
        !           227: {
        !           228:        zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
        !           229: 
        !           230:        tmp->prev = l->tail;
        !           231:        tmp->next = NULL;
        !           232:        if (l->tail) {
        !           233:                l->tail->next = tmp;
        !           234:        } else {
        !           235:                l->head = tmp;
        !           236:        }
        !           237:        l->tail = tmp;
        !           238:        memcpy(tmp->data, element, l->size);
        !           239: 
        !           240:        ++l->count;
        !           241: }
        !           242: 
        !           243: 
        !           244: ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
        !           245: {
        !           246:        zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
        !           247: 
        !           248:        tmp->next = l->head;
        !           249:        tmp->prev = NULL;
        !           250:        if (l->head) {
        !           251:                l->head->prev = tmp;
        !           252:        } else {
        !           253:                l->tail = tmp;
        !           254:        }
        !           255:        l->head = tmp;
        !           256:        memcpy(tmp->data, element, l->size);
        !           257: 
        !           258:        ++l->count;
        !           259: }
        !           260: 
        !           261: 
        !           262: #define DEL_LLIST_ELEMENT(current, l) \
        !           263:                        if ((current)->prev) {\
        !           264:                                (current)->prev->next = (current)->next;\
        !           265:                        } else {\
        !           266:                                (l)->head = (current)->next;\
        !           267:                        }\
        !           268:                        if ((current)->next) {\
        !           269:                                (current)->next->prev = (current)->prev;\
        !           270:                        } else {\
        !           271:                                (l)->tail = (current)->prev;\
        !           272:                        }\
        !           273:                        zend_llist_check_destructor((l)->dtor); \
        !           274:                        if ((l)->dtor) {\
        !           275:                                (l)->dtor((current)->data);\
        !           276:                        }\
        !           277:                        pefree((current), (l)->persistent);\
        !           278:                        --l->count;
        !           279: 
        !           280: 
        !           281: ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
        !           282: {
        !           283:        zend_llist_element *current=l->head;
        !           284:        zend_llist_element *next;
        !           285: 
        !           286:        while (current) {
        !           287:                next = current->next;
        !           288:                if (compare(current->data, element)) {
        !           289:                        DEL_LLIST_ELEMENT(current, l);
        !           290:                        break;
        !           291:                }
        !           292:                current = next;
        !           293:        }
        !           294: }
        !           295: 
        !           296: 
        !           297: ZEND_API void zend_llist_destroy(zend_llist *l)
        !           298: {
        !           299:        zend_llist_element *current=l->head, *next;
        !           300:        
        !           301:        zend_llist_check_destructor(l->dtor);
        !           302:        while (current) {
        !           303:                next = current->next;
        !           304:                if (l->dtor) {
        !           305:                        l->dtor(current->data);
        !           306:                }
        !           307:                pefree(current, l->persistent);
        !           308:                current = next;
        !           309:        }
        !           310: 
        !           311:        l->count = 0;
        !           312: }
        !           313: 
        !           314: 
        !           315: ZEND_API void zend_llist_clean(zend_llist *l)
        !           316: {
        !           317:        zend_llist_destroy(l);
        !           318:        l->head = l->tail = NULL;
        !           319: }
        !           320: 
        !           321: 
        !           322: ZEND_API void *zend_llist_remove_tail(zend_llist *l)
        !           323: {
        !           324:        zend_llist_element *old_tail;
        !           325:        void *data;
        !           326: 
        !           327:        zend_llist_check_destructor((l)->dtor);
        !           328:        if ((old_tail = l->tail)) {
        !           329:                if (old_tail->prev) {
        !           330:                        old_tail->prev->next = NULL;
        !           331:                } else {
        !           332:                        l->head = NULL;
        !           333:                }
        !           334:         
        !           335:                data = old_tail->data;
        !           336: 
        !           337:                l->tail = old_tail->prev;
        !           338:                if (l->dtor) {
        !           339:                        l->dtor(data);
        !           340:                }
        !           341:                pefree(old_tail, l->persistent);
        !           342: 
        !           343:                --l->count;
        !           344: 
        !           345:                return data;
        !           346:        }
        !           347: 
        !           348:        return NULL;
        !           349: }
        !           350: 
        !           351: 
        !           352: ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
        !           353: {
        !           354:        zend_llist_element *ptr;
        !           355: 
        !           356:        zend_llist_init(dst, src->size, src->dtor, src->persistent);
        !           357:        ptr = src->head;
        !           358:        while (ptr) {
        !           359:                zend_llist_add_element(dst, ptr->data);
        !           360:                ptr = ptr->next;
        !           361:        }
        !           362: }
        !           363: 
        !           364: 
        !           365: ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
        !           366: {
        !           367:        zend_llist_element *element, *next;
        !           368: 
        !           369:        element=l->head;
        !           370:        while (element) {
        !           371:                next = element->next;
        !           372:                if (func(element->data)) {
        !           373:                        DEL_LLIST_ELEMENT(element, l);
        !           374:                }
        !           375:                element = next;
        !           376:        }
        !           377: }
        !           378: 
        !           379: 
        !           380: ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
        !           381: {
        !           382:        zend_llist_element *element;
        !           383: 
        !           384:        for (element=l->head; element; element=element->next) {
        !           385:                func(element->data TSRMLS_CC);
        !           386:        }
        !           387: }
        !           388: 
        !           389: ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
        !           390: {
        !           391:        size_t i;
        !           392: 
        !           393:        zend_llist_element **elements;
        !           394:        zend_llist_element *element, **ptr;
        !           395: 
        !           396:        if (l->count <= 0) {
        !           397:                return;
        !           398:        }
        !           399: 
        !           400:        elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
        !           401: 
        !           402:        ptr = &elements[0];
        !           403: 
        !           404:        for (element=l->head; element; element=element->next) {
        !           405:                *ptr++ = element;
        !           406:        }
        !           407: 
        !           408:        zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
        !           409: 
        !           410:        l->head = elements[0];
        !           411:        elements[0]->prev = NULL;
        !           412: 
        !           413:        for (i = 1; i < l->count; i++) {
        !           414:                elements[i]->prev = elements[i-1];
        !           415:                elements[i-1]->next = elements[i];
        !           416:        }
        !           417:        elements[i-1]->next = NULL;
        !           418:        l->tail = elements[i-1];
        !           419:        efree(elements);
        !           420: }
        !           421: 
        !           422: 
        !           423: ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC)
        !           424: {
        !           425:        zend_llist_element *element;
        !           426: 
        !           427:        for (element=l->head; element; element=element->next) {
        !           428:                func(element->data, arg TSRMLS_CC);
        !           429:        }
        !           430: }
        !           431: 
        !           432: 
        !           433: ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...)
        !           434: {
        !           435:        zend_llist_element *element;
        !           436:        va_list args;
        !           437: 
        !           438:        va_start(args, num_args);
        !           439:        for (element=l->head; element; element=element->next) {
        !           440:                func(element->data, num_args, args TSRMLS_CC);
        !           441:        }
        !           442:        va_end(args);
        !           443: }
        !           444: 
        !           445: 
        !           446: ZEND_API int zend_llist_count(zend_llist *l)
        !           447: {
        !           448:        return l->count;
        !           449: }
        !           450: 
        !           451: 
        !           452: ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
        !           453: {
        !           454:        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
        !           455: 
        !           456:        *current = l->head;
        !           457:        if (*current) {
        !           458:                return (*current)->data;
        !           459:        } else {
        !           460:                return NULL;
        !           461:        }
        !           462: }
        !           463: 
        !           464: 
        !           465: ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
        !           466: {
        !           467:        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
        !           468: 
        !           469:        *current = l->tail;
        !           470:        if (*current) {
        !           471:                return (*current)->data;
        !           472:        } else {
        !           473:                return NULL;
        !           474:        }
        !           475: }
        !           476: 
        !           477: 
        !           478: ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
        !           479: {
        !           480:        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
        !           481: 
        !           482:        if (*current) {
        !           483:                *current = (*current)->next;
        !           484:                if (*current) {
        !           485:                        return (*current)->data;
        !           486:                }
        !           487:        }
        !           488:        return NULL;
        !           489: }
        !           490: 
        !           491: 
        !           492: ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
        !           493: {
        !           494:        zend_llist_position *current = pos ? pos : &l->traverse_ptr;
        !           495: 
        !           496:        if (*current) {
        !           497:                *current = (*current)->prev;
        !           498:                if (*current) {
        !           499:                        return (*current)->data;
        !           500:                }
        !           501:        }
        !           502:        return NULL;
        !           503: }
        !           504: 
        !           505: /*
        !           506:  * Local variables:
        !           507:  * tab-width: 4
        !           508:  * c-basic-offset: 4
        !           509:  * indent-tabs-mode: t
        !           510:  * End:
        !           511:  */

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