/*
   +----------------------------------------------------------------------+
   | Zend Engine                                                          |
   +----------------------------------------------------------------------+
   | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
   +----------------------------------------------------------------------+
   | This source file is subject to version 2.00 of the Zend license,     |
   | that is bundled with this package in the file LICENSE, and is        | 
   | available through the world-wide-web at the following url:           |
   | http://www.zend.com/license/2_00.txt.                                |
   | If you did not receive a copy of the Zend license and are unable to  |
   | obtain it through the world-wide-web, please send a note to          |
   | license@zend.com so we can mail you a copy immediately.              |
   +----------------------------------------------------------------------+
   | Authors: Andi Gutmans <andi@zend.com>                                |
   |          Zeev Suraski <zeev@zend.com>                                |
   +----------------------------------------------------------------------+
*/

/* $Id: zend_llist.c,v 1.1.1.1 2012/02/21 23:47:52 misho Exp $ */

#include "zend.h"
#include "zend_llist.h"
#include "zend_qsort.h"

#if SUHOSIN_PATCH
#ifdef ZTS
static MUTEX_T zend_llist_dprot_mx_reader;
static MUTEX_T zend_llist_dprot_mx_writer;
static unsigned int zend_llist_dprot_reader;
#endif
static unsigned int zend_llist_dprot_counter;
static unsigned int zend_llist_dprot_curmax;
static llist_dtor_func_t *zend_llist_dprot_table = NULL;

static void zend_llist_dprot_begin_read()
{
#ifdef ZTS
	tsrm_mutex_lock(zend_llist_dprot_mx_reader);
	if ((++(zend_llist_dprot_reader)) == 1) {
		tsrm_mutex_lock(zend_llist_dprot_mx_writer);
	}
	tsrm_mutex_unlock(zend_llist_dprot_mx_reader);
#endif
}

static void zend_llist_dprot_end_read()
{
#ifdef ZTS
	tsrm_mutex_lock(zend_llist_dprot_mx_reader);
	if ((--(zend_llist_dprot_reader)) == 0) {
		tsrm_mutex_unlock(zend_llist_dprot_mx_writer);
	}
	tsrm_mutex_unlock(zend_llist_dprot_mx_reader);
#endif
}

static void zend_llist_dprot_begin_write()
{
#ifdef ZTS
	tsrm_mutex_lock(zend_llist_dprot_mx_writer);
#endif
}

static void zend_llist_dprot_end_write()
{
#ifdef ZTS
	tsrm_mutex_unlock(zend_llist_dprot_mx_writer);
#endif
}

/*ZEND_API void zend_llist_dprot_dtor()
{
#ifdef ZTS
	tsrm_mutex_free(zend_llist_dprot_mx_reader);
	tsrm_mutex_free(zend_llist_dprot_mx_writer);
#endif	
	free(zend_llist_dprot_table);
}*/

static void zend_llist_add_destructor(llist_dtor_func_t pDestructor)
{
	int left, right, mid;
	zend_bool found = 0;
	unsigned long value;
	
	if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR) {
		return;
	}
	
	if (zend_llist_dprot_table == NULL) {
#ifdef ZTS
		zend_llist_dprot_mx_reader = tsrm_mutex_alloc();
		zend_llist_dprot_mx_writer = tsrm_mutex_alloc();
		zend_llist_dprot_reader = 0;
#endif	
		zend_llist_dprot_counter = 0;
		zend_llist_dprot_curmax = 256;
		zend_llist_dprot_table = (llist_dtor_func_t *) malloc(256 * sizeof(llist_dtor_func_t));
	}
	
	zend_llist_dprot_begin_write();

	if (zend_llist_dprot_counter == 0) {
		zend_llist_dprot_counter++;
		zend_llist_dprot_table[0] = pDestructor;
	} else {
		value = (unsigned long) pDestructor;
		left = 0;
		right = zend_llist_dprot_counter-1;
		mid = 0;
		
		while (left < right) {
			mid = (right - left) >> 1;
			mid += left;
			if ((unsigned long)zend_llist_dprot_table[mid] == value) {
				found = 1;
				break;
			}
			if (value < (unsigned long)zend_llist_dprot_table[mid]) {
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		if ((unsigned long)zend_llist_dprot_table[left] == value) {
			found = 1;
		}
		
		if (!found) {
		
			if (zend_llist_dprot_counter >= zend_llist_dprot_curmax) {
				zend_llist_dprot_curmax += 256;
				zend_llist_dprot_table = (llist_dtor_func_t *) realloc(zend_llist_dprot_table, zend_llist_dprot_curmax * sizeof(llist_dtor_func_t));
			}
			
			if ((unsigned long)zend_llist_dprot_table[left] < value) {
				memmove(zend_llist_dprot_table+left+2, zend_llist_dprot_table+left+1, (zend_llist_dprot_counter-left-1)*sizeof(llist_dtor_func_t));
				zend_llist_dprot_table[left+1] = pDestructor;
			} else {
				memmove(zend_llist_dprot_table+left+1, zend_llist_dprot_table+left, (zend_llist_dprot_counter-left)*sizeof(llist_dtor_func_t));
				zend_llist_dprot_table[left] = pDestructor;
			}

			zend_llist_dprot_counter++;
		}
	}
	
	zend_llist_dprot_end_write();
}

static void zend_llist_check_destructor(llist_dtor_func_t pDestructor)
{
	unsigned long value;
	
	if (pDestructor == NULL || pDestructor == ZVAL_PTR_DTOR) {
		return;
	}

	zend_llist_dprot_begin_read();
	
	if (zend_llist_dprot_counter > 0) {
		int left, right, mid;
		zend_bool found = 0;
	
		value = (unsigned long) pDestructor;
		left = 0;
		right = zend_llist_dprot_counter-1;
		
		while (left < right) {
			mid = (right - left) >> 1;
			mid += left;
			if ((unsigned long)zend_llist_dprot_table[mid] == value) {
				found = 1;
				break;
			}
			if (value < (unsigned long)zend_llist_dprot_table[mid]) {
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		if ((unsigned long)zend_llist_dprot_table[left] == value) {
			found = 1;
		}
		
		if (!found) {
			zend_llist_dprot_end_read();
		
		        zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown llist destructor");
			if (SUHOSIN_CONFIG(SUHOSIN_LL_IGNORE_INVALID_DESTRUCTOR) == 0) {
			        _exit(1);
		        }
			return;
		}
	
	} else {
		zend_llist_dprot_end_read();
	
	        zend_suhosin_log(S_MEMORY, "possible memory corruption detected - unknown llist destructor");
		if (SUHOSIN_CONFIG(SUHOSIN_LL_IGNORE_INVALID_DESTRUCTOR) == 0) {
		        _exit(1);
	        }
		return;	        
	}
	
	zend_llist_dprot_end_read();
}
#else
#define zend_llist_add_destructor(pDestructor) do {} while(0)
#define zend_llist_check_destructor(pDestructor) do {} while(0)
#endif

ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
{
	l->head  = NULL;
	l->tail  = NULL;
	l->count = 0;
	l->size  = size;
	l->dtor  = dtor;
	zend_llist_add_destructor(dtor);
	l->persistent = persistent;
}


ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
{
	zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

	tmp->prev = l->tail;
	tmp->next = NULL;
	if (l->tail) {
		l->tail->next = tmp;
	} else {
		l->head = tmp;
	}
	l->tail = tmp;
	memcpy(tmp->data, element, l->size);

	++l->count;
}


ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
{
	zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

	tmp->next = l->head;
	tmp->prev = NULL;
	if (l->head) {
		l->head->prev = tmp;
	} else {
		l->tail = tmp;
	}
	l->head = tmp;
	memcpy(tmp->data, element, l->size);

	++l->count;
}


#define DEL_LLIST_ELEMENT(current, l) \
			if ((current)->prev) {\
				(current)->prev->next = (current)->next;\
			} else {\
				(l)->head = (current)->next;\
			}\
			if ((current)->next) {\
				(current)->next->prev = (current)->prev;\
			} else {\
				(l)->tail = (current)->prev;\
			}\
			zend_llist_check_destructor((l)->dtor); \
			if ((l)->dtor) {\
				(l)->dtor((current)->data);\
			}\
			pefree((current), (l)->persistent);\
			--l->count;


ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
{
	zend_llist_element *current=l->head;
	zend_llist_element *next;

	while (current) {
		next = current->next;
		if (compare(current->data, element)) {
			DEL_LLIST_ELEMENT(current, l);
			break;
		}
		current = next;
	}
}


ZEND_API void zend_llist_destroy(zend_llist *l)
{
	zend_llist_element *current=l->head, *next;
	
	zend_llist_check_destructor(l->dtor);
	while (current) {
		next = current->next;
		if (l->dtor) {
			l->dtor(current->data);
		}
		pefree(current, l->persistent);
		current = next;
	}

	l->count = 0;
}


ZEND_API void zend_llist_clean(zend_llist *l)
{
	zend_llist_destroy(l);
	l->head = l->tail = NULL;
}


ZEND_API void *zend_llist_remove_tail(zend_llist *l)
{
	zend_llist_element *old_tail;
	void *data;

	zend_llist_check_destructor((l)->dtor);
	if ((old_tail = l->tail)) {
		if (old_tail->prev) {
			old_tail->prev->next = NULL;
		} else {
			l->head = NULL;
		}
        
		data = old_tail->data;

		l->tail = old_tail->prev;
		if (l->dtor) {
			l->dtor(data);
		}
		pefree(old_tail, l->persistent);

		--l->count;

		return data;
	}

	return NULL;
}


ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
{
	zend_llist_element *ptr;

	zend_llist_init(dst, src->size, src->dtor, src->persistent);
	ptr = src->head;
	while (ptr) {
		zend_llist_add_element(dst, ptr->data);
		ptr = ptr->next;
	}
}


ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
{
	zend_llist_element *element, *next;

	element=l->head;
	while (element) {
		next = element->next;
		if (func(element->data)) {
			DEL_LLIST_ELEMENT(element, l);
		}
		element = next;
	}
}


ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
{
	zend_llist_element *element;

	for (element=l->head; element; element=element->next) {
		func(element->data TSRMLS_CC);
	}
}

ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
{
	size_t i;

	zend_llist_element **elements;
	zend_llist_element *element, **ptr;

	if (l->count <= 0) {
		return;
	}

	elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));

	ptr = &elements[0];

	for (element=l->head; element; element=element->next) {
		*ptr++ = element;
	}

	zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);

	l->head = elements[0];
	elements[0]->prev = NULL;

	for (i = 1; i < l->count; i++) {
		elements[i]->prev = elements[i-1];
		elements[i-1]->next = elements[i];
	}
	elements[i-1]->next = NULL;
	l->tail = elements[i-1];
	efree(elements);
}


ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC)
{
	zend_llist_element *element;

	for (element=l->head; element; element=element->next) {
		func(element->data, arg TSRMLS_CC);
	}
}


ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...)
{
	zend_llist_element *element;
	va_list args;

	va_start(args, num_args);
	for (element=l->head; element; element=element->next) {
		func(element->data, num_args, args TSRMLS_CC);
	}
	va_end(args);
}


ZEND_API int zend_llist_count(zend_llist *l)
{
	return l->count;
}


ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
{
	zend_llist_position *current = pos ? pos : &l->traverse_ptr;

	*current = l->head;
	if (*current) {
		return (*current)->data;
	} else {
		return NULL;
	}
}


ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
{
	zend_llist_position *current = pos ? pos : &l->traverse_ptr;

	*current = l->tail;
	if (*current) {
		return (*current)->data;
	} else {
		return NULL;
	}
}


ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
{
	zend_llist_position *current = pos ? pos : &l->traverse_ptr;

	if (*current) {
		*current = (*current)->next;
		if (*current) {
			return (*current)->data;
		}
	}
	return NULL;
}


ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
{
	zend_llist_position *current = pos ? pos : &l->traverse_ptr;

	if (*current) {
		*current = (*current)->prev;
		if (*current) {
			return (*current)->data;
		}
	}
	return NULL;
}

/*
 * Local variables:
 * tab-width: 4
 * c-basic-offset: 4
 * indent-tabs-mode: t
 * End:
 */