patterncMinor
Dynamic stack in C - new version
Viewed 0 times
versionnewstackdynamic
Problem
Not long ago, I posted this dynamic stack for review. Now I wrote a new version, which is hopefully a better one.
Please take a look and let me know how I could improve performance and increase code quality.
It works by storing pointers to the content. If there's not enough memory, it will try to increase the allocated space.
header
c file
```
#include
#include "dynamic_stack.h"
#define MULTIPLIER 1.00 //Increase by 100% on every expansion
#define FIXED_EXPANSION 0 //Overrides multiplier
//Internal
//Must keep at least 1 slot or it will break
static int dstack_resize(Dynamic_Stack *stack, size_t new_slot_capacity)
{
size_t position = stack->position - stack->start;
void temp = realloc(stack->start, new_slot_capacity sizeof(void *));
if(temp == NULL)
return DSTACK_ERROR;
stack->start = temp;
stack->end = stack->start + new_slot_capacity;
//Put position back if needed
stack->position = (position start + position
: stack->end;
return DSTACK_SUCCESS;
}
#if FIXED_EXPANSION >= 1
static int expand(Dynamic_Stack *stack)
{
return dstack_resize(stack, stack->end - s
Please take a look and let me know how I could improve performance and increase code quality.
It works by storing pointers to the content. If there's not enough memory, it will try to increase the allocated space.
header
#ifndef DYNAMIC_STACK
#define DYNAMIC_STACK
#define DSTACK_SUCCESS 1
#define DSTACK_ERROR 0
//The stack just stores pointers
typedef struct Dynamic_Stack Dynamic_Stack;
struct Dynamic_Stack {
void **start; //Array of pointer to void
void **position;
void **end;
};
//Set up stack
int dstack_init(Dynamic_Stack *stack, size_t slots);
void dstack_free(Dynamic_Stack *stack);
void dstack_clear(Dynamic_Stack *stack);
int dstack_push(Dynamic_Stack *stack, void *new_element);
void *dstack_pop(Dynamic_Stack *stack);
//0 is the top of the stack
void *dstack_peek(Dynamic_Stack *stack, size_t levels);
int dstack_increase_capacity(Dynamic_Stack *stack, size_t new_slots);
int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total);
void dstack_shrink_to_fit(Dynamic_Stack *stack);
#endifc file
```
#include
#include "dynamic_stack.h"
#define MULTIPLIER 1.00 //Increase by 100% on every expansion
#define FIXED_EXPANSION 0 //Overrides multiplier
//Internal
//Must keep at least 1 slot or it will break
static int dstack_resize(Dynamic_Stack *stack, size_t new_slot_capacity)
{
size_t position = stack->position - stack->start;
void temp = realloc(stack->start, new_slot_capacity sizeof(void *));
if(temp == NULL)
return DSTACK_ERROR;
stack->start = temp;
stack->end = stack->start + new_slot_capacity;
//Put position back if needed
stack->position = (position start + position
: stack->end;
return DSTACK_SUCCESS;
}
#if FIXED_EXPANSION >= 1
static int expand(Dynamic_Stack *stack)
{
return dstack_resize(stack, stack->end - s
Solution
Regarding performance: as the major operations (push and pop) are O(1) and you wrote them in a straightforward way, it is hard to optimize them in a way which would not be annulled (or even reversed in effect) by compiler or CPU optimizations.
OTOH, it is also hard to envision a situation where program performance would even be remotely depending on your stack code - as you are (in most cases) dealing with "something bigger than an int", every push/pop is accompanied by an operation on the data item which will very likely outweigh the stack operations by a factor.
(minor nitpick: in the pop-function you could and should use two operations to decrease the stackpointer and return the value a) to be symmetric to the code in push b) to save the programmer coming after you from needing to remember what *-- means exactly)
OTOH, it is also hard to envision a situation where program performance would even be remotely depending on your stack code - as you are (in most cases) dealing with "something bigger than an int", every push/pop is accompanied by an operation on the data item which will very likely outweigh the stack operations by a factor.
(minor nitpick: in the pop-function you could and should use two operations to decrease the stackpointer and return the value a) to be symmetric to the code in push b) to save the programmer coming after you from needing to remember what *-- means exactly)
Context
StackExchange Code Review Q#39075, answer score: 2
Revisions (0)
No revisions yet.