6
\$\begingroup\$

I wrote this code for a dynamic stack and would like to know what would be better if done differently.

It can increase memory by a percentage and/or fixed value when needed. It can also be set to not increase automatically at all, so slots are only allocated by the user.

The stack is just a structure holding any data type, so it can change what kind of data is stored without deallocating memory.

Header definitions

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define MINIMUM_ELEMENT_SIZE (1)
#define MULTIPLIER (1.00)
#define EXPANSION_AMOUNT (8)

typedef struct {
    void *content;
    size_t element_size;
    size_t count;
    size_t slots;
    float multiplier;
    size_t expansion_amount;
} Stack;

Some inline functions to do very simple things

static inline void *memory_from_position(Stack *stack, size_t position) __attribute__((always_inline));
static inline size_t required_memory_for_slots(Stack *stack, size_t n_slots) __attribute__((always_inline));
static inline size_t how_many_slots_can_fit(size_t memory_size, size_t slot_size) __attribute__((always_inline));
static inline size_t available_slots(Stack *stack) __attribute__((always_inline));

//Return memory address based on position supplied, starts at 0, no error
//checking, caller must be sure the position is in range
static inline void *memory_from_position(Stack *stack, size_t position)
{
    return stack->content + stack->element_size * position;
}

//Return how much memory n_slots would occupy
static inline size_t required_memory_for_slots(Stack *stack, size_t n_slots)
{
    return stack->element_size * n_slots;
}

//Return how many slots can fit into memory
static inline size_t how_many_slots_can_fit(size_t memory_size, size_t slot_size)
{
    return memory_size / slot_size;
}

//Return how many slots there are left
static inline size_t available_slots(Stack *stack)
{
    return stack->slots - stack->count;
}

Main functions

//Allocate and initialize stack
Stack *new_stack(size_t element_size)
{
    if(element_size < MINIMUM_ELEMENT_SIZE){
        return NULL;
    }

    Stack *temp = malloc(sizeof(Stack));
    if(temp == NULL){
        return NULL;
    }

    temp->content = NULL;
    temp->element_size = element_size;
    temp->count = 0;
    temp->slots = 0;
    temp->multiplier = MULTIPLIER;
    temp->expansion_amount = EXPANSION_AMOUNT;

    return temp;
}

void delete_stack(Stack *stack)
{
    free(stack->content);
    free(stack);
}

//Keep stack structure, free contents
void release_stack_resources(Stack *stack)
{
    free(stack->content);
    clear_stack(stack);
    stack->content = NULL;
    stack->slots = 0;
}

void clear_stack(Stack *stack)
{
    stack->count = 0;
}

//Use an already allocated stack to hold a new data type, keep old multiplier and
//expansion amount, a few bytes may become unusable until a memory operation
//is performed, always succeed
void repurpose_stack(Stack *stack, size_t new_element_size)
{
    //Calculate available memory    
    size_t available_memory = required_memory_for_slots(stack, stack->slots);

    //Update slots count and stack
    clear_stack(stack); 
    stack->slots = how_many_slots_can_fit(available_memory, new_element_size);
    stack->element_size = new_element_size;
}

//Return multiplier set, must be positive
float set_stack_multiplier(Stack *stack, float new_multiplier)
{
    if(new_multiplier >= 0){
        stack->multiplier = new_multiplier;
    }

    return stack->multiplier;
}

//Can be set to 0
void set_stack_expansion_amount(Stack *stack, size_t expansion_amount)
{
    stack->expansion_amount = expansion_amount;
}

//Allocate memory for more slots and return new memory location
void *add_slots(Stack *stack, size_t new_slots)
{
    void *temp = realloc(stack->content, required_memory_for_slots(stack, stack->slots + new_slots));
    if(temp == NULL){
        return NULL;
    }

    stack->content = temp;
    stack->slots += new_slots;

    return temp;
}

//Remove slots whether they are empty or not, if the number is greater than
//the amount of slots, it removes all. Return pointer to stack or NULL
Stack *remove_slots(Stack *stack, size_t amount)
{
    //Handle special case of removing all slots
    if(amount >= stack->slots){
        release_stack_resources(stack);      
        return stack;        
    }

    //Regular usage
    size_t slots_to_keep = stack->slots - amount;

    void *temp = realloc(stack->content, required_memory_for_slots(stack, slots_to_keep));
    if(temp == NULL){
        return NULL;
    }

    //Update stack info
    stack->content = temp;
    stack->slots = slots_to_keep;

    //Set back count if its overflowing
    if(stack->count > stack->slots){
        stack->count = stack->slots;
    }

    return stack;
}

//Expand stack memory by a percentage or fixed amount, whichever is greater
static void *expand_stack_memory(Stack *stack)
{
    //If both multiplier and expansion amount evaluate to 0 slots, the stack cannot expand
    //automatically, then a call to add_slots must be made to enable the stack to work
    size_t new_slots = (float)stack->slots * stack->multiplier;
    if(new_slots < stack->expansion_amount){
        new_slots = stack->expansion_amount;
    }
    if(new_slots == 0){
        return NULL;
    }

    return add_slots(stack, new_slots);
}

//Element must have size identical to element_size or stack will break
void *push(Stack *stack, void *element)
{
    //Check if there's space, try to allocate more if there isn't
    if(available_slots(stack) == 0 && expand_stack_memory(stack) == NULL){
        return NULL;
    }

    //Copy element to stack and return its location
    return memcpy(memory_from_position(stack, stack->count++), element, stack->element_size);
}

void *pop(Stack *stack)
{
    return (stack->count > 0) ? memory_from_position(stack, --stack->count) : NULL;
}

//Look what element is at n_levels deep without removing it, 0 being the top element
void *peek(Stack *stack, size_t n_levels)
{
    if(n_levels >= stack->count){
        return NULL;
    }

    return memory_from_position(stack, stack->count - 1 - n_levels);
}

//Shrink allocated memory to fit current elements, return stack or NULL
Stack *shrink_stack_to_fit(Stack *stack)
{
    size_t remove_total = stack->slots - stack->count;
    return (remove_total > 0) ? remove_slots(stack, remove_total) : stack;
}

//Might be useful for printing all data or collecting it without removing
void stack_iterate(Stack *stack, void(*callback)(void*))
{
    for(size_t i = 0; i < stack->count; ++i){
        callback(memory_from_position(stack, stack->count - 1 - i));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Looks professional. Good job. \$\endgroup\$ – Fiddling Bits Dec 26 '13 at 0:31
4
\$\begingroup\$

Why add the parentheses in your macro constants? This provides no benefit and may cause typos to compile (e.g. (fabs MULTIPLIER - 5) / EXPANSION_AMOUNT; when you meant to write fabs(MULTIPLIER - 5) / EXPANSION_AMOUNT;).

Remove __attribute__((always_inline)). Compilers these days are very good at optimizing, and overriding their decisions will almost never lead to better code. With these functions, the compiler will almost always inline them anyway, but there may be rare occasions when it determines that it is faster to produce code with function calls.

Your new_stack function is odd to me; it doesn't allocate content, and in fact allocates an object on the heap whose size is known at runtime when it may be more appropriate to allocate it on the stack! I'd pass it more parameters than just element_size, and have a separate init_stack function that initializes a stack that is passed in by reference in case the stack structure is allocated on the stack instead of the heap.

Actually, I would rename all of the functions in this library; since C has no namespaces, function names in a library ought to have library-specific names: stack_new, stack_push, stack_pop, etc.

You may want slots to be a derived value instead of a primary value, and instead store the size of the buffer in bytes. As it is,

Stack* s = new_stack(10);
add_slots(s, 10);
printf("Slots: %d\n", s->slots);
repurpose_stack(s, 15);
repurpose_stack(s, 10);
printf("Slots: %d\n" s->slots);
repurpose_stack(s, 91);
repurpose_stack(s, 10);
printf("Slots: %d\n" s->slots);

will print out "10\n9\n0\n", not "10\n10\n10\n".

I recommend adding an assertion to remove_slots:

assert(amount <= stack->slots);

It is a programming error to remove more slots than actually exist in the data structure. This will be compiled out when optimizing, but may help find bugs while debugging.

Similarly, consider adding assertions in push and pop that check bounds.

\$\endgroup\$
2
\$\begingroup\$

Very Nice.
Only small stuff

  1. Why (float) in size_t new_slots = (float)stack->slots * stack->multiplier;?

  2. Given sizeof size_t may not equal sizeof float, suggest grouping like types in struct

    typedef struct {
        void *content;
        size_t element_size;
        ...
        size_t expansion_amount;
        float multiplier;
    } Stack;
    
  3. Since new_stack() may return NULL, note the other main functions are not protected from dereferencing NULL. Protection is not a hard requirement here - more about design philosophy about should main level routine have NULL protection? Your call.

  4. Minor: Could use a float in the define to emphasize the value will be used as a float.
    #define MULTIPLIER (1.00f)

  5. (I assume your header is at global scope.) Since typedef struct { ... } Stack is only used by an application as a pointer, could use an anonymous pointer to insure information hiding.

  6. The defines may be useful to an application as defaults parameters. There, they could appear at global scope, so use less generic names.

    #define Stack_MINIMUM_ELEMENT_SIZE (1)
    #define Stack_MULTIPLIER (1.0f)
    #define Stack_EXPANSION_AMOUNT (8)
    
\$\endgroup\$
1
\$\begingroup\$

Your code looks nice. I only have two comments.

Firstly, both peek and pop give the caller access to locations on the stack, rather than copying stack data back to a variable in the caller's scope. This is not robust as the caller could easily stack something else and thereby overwrite these locations.

Secondly, my usual refrain of adding const to function parameters where possible.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.