/* 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;
    size_t size;
    size_t iter;
    void **array;
};

/******************************************************************************/
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;
}

/******************************************************************************/
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);
}

/******************************************************************************/
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)];
}