repos_ecs/其他2015后/日志库/log4cproj_c/Log4C/sd/stack.c

/* stack - a dynamically resizing stack
* Copyright (c) 2001 Michael B. Allen <mballen@erols.com>
*
* The MIT License
* 
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
* 
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/ 

#include "sd/stack.h"
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#include "sd/malloc.h"

#define SD_STACK_INIT_SIZE 32

struct __sd_stack {
	size_t max;					// 堆栈的能分配的最大长度;
	size_t sp;					// push的个数,实际堆栈元素;
	size_t size;				// 当前堆栈分配的大小;
	size_t iter;				// 迭代索引;
	void **array;				// 堆栈区;
};

/************************************************************************/
/*  函数：sd_stack_new[6/14/2016 ItCivilian];
/*  描述：分配最大max长度的堆栈;
/*  参数：;
/*  	[IN] max：堆栈的最大值;
/*  返回：返回堆栈指针;
/*  注意：;
/*  示例：;
/************************************************************************/
sd_stack_t* sd_stack_new(size_t max)
{
	sd_stack_t* ptrThis;

	ptrThis        = (sd_stack_t*)sd_calloc(1, sizeof(sd_stack_t));
	ptrThis->max   = max == 0 ? INT_MAX : max;
	ptrThis->size  = SD_STACK_INIT_SIZE;
	ptrThis->sp    = 0;
	ptrThis->array = (void **)sd_calloc(ptrThis->size, sizeof(*ptrThis->array));

	return ptrThis;
}

/************************************************************************/
/*  函数：sd_stack_delete[6/14/2016 ItCivilian];
/*  描述：删除指定的堆栈;
/*  参数：;
/*  	[IN] ptrThis：要删除的堆栈指针;
/*  	[IN] free_data_fn：回调函数指针;
/*  返回：void;
/*  注意：;
/*  示例：;
/************************************************************************/
void sd_stack_delete(sd_stack_t* ptrThis, void (*free_data_fn)(void *))
{
	if (!ptrThis)
		return;

	sd_stack_clear(ptrThis, free_data_fn);

	free(ptrThis->array);
	free(ptrThis);
}

/************************************************************************/
/*  函数：[6/14/2016 ItCivilian];
/*  描述：获取堆栈元素个数;
/*  参数：;
/*  	[IN] ptrThis：堆栈;
/*  返回：void;
/*  注意：;
/*  示例：;
/************************************************************************/
size_t sd_stack_get_nelem(const sd_stack_t* ptrThis)
{
	return ptrThis ? ptrThis->sp : -1;
}

/******************************************************************************/
void sd_stack_clear(sd_stack_t* ptrThis, void (*free_data_fn)(void *))
{
	if (!ptrThis)
		return;

	if (free_data_fn) {
		while (ptrThis->sp > 0) {
			free_data_fn(ptrThis->array[--(ptrThis->sp)]);
		}
	}
}

/******************************************************************************/
void* sd_stack_begin(sd_stack_t* ptrThis)
{
	if (!ptrThis)
		return NULL;

	ptrThis->iter = 0;
	return ptrThis->array[ptrThis->iter];
}

/******************************************************************************/
void* sd_stack_next(sd_stack_t* ptrThis)
{
	if (ptrThis && ptrThis->iter < ptrThis->sp) 
		return ptrThis->array[ptrThis->iter++];

	return NULL;
}

/******************************************************************************/
void* sd_stack_end(sd_stack_t* ptrThis)
{
	return sd_stack_peek(ptrThis);
}

/******************************************************************************/
void* sd_stack_peek(sd_stack_t* ptrThis)
{
	if (!ptrThis || !ptrThis->sp) 
		return NULL;

	return ptrThis->array[ptrThis->sp - 1];
}

/******************************************************************************/
int sd_stack_push(sd_stack_t* ptrThis, void *data)
{
	if (ptrThis == NULL)
		return -1;

	if (ptrThis->sp == ptrThis->size) {
		size_t new_size;

		if (ptrThis->size == ptrThis->max)
			return -1;

		if (ptrThis->size * 2 > ptrThis->max) 
		{
			new_size = ptrThis->max;
		} 
		else 
		{
			new_size = ptrThis->size * 2;
		}

		ptrThis->size = new_size;
		ptrThis->array = (void **)sd_realloc(ptrThis->array, sizeof(*ptrThis->array) * ptrThis->size);
	}

	assert(ptrThis->sp <= ptrThis->size);
	ptrThis->array[ptrThis->sp++] = data;
	return 0;
}

/******************************************************************************/
void* sd_stack_pop(sd_stack_t* ptrThis)
{
	if (ptrThis == NULL || ptrThis->sp == 0) 
		return NULL;

	if (ptrThis->size >= SD_STACK_INIT_SIZE * 4 && ptrThis->sp < ptrThis->size / 4) {
		size_t new_size = ptrThis->size / 2;

		ptrThis->size = new_size;
		ptrThis->array = (void **)sd_realloc(ptrThis->array, sizeof(*ptrThis->array) * ptrThis->size);
	}

	assert(ptrThis->sp > 0 && ptrThis->sp <= ptrThis->size);
	return ptrThis->array[--(ptrThis->sp)];
}