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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to zend_llist.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend