Skip to content

Instantly share code, notes, and snippets.

@longkai

longkai/stack.c

Last active Dec 11, 2016
Embed
What would you like to do?
A simple dynamic stack written in C.
#include <stdio.h>
#include "stack.h"
#define STACK_SIZE 5 // or larger, e.g. 1024 ptrs
#define PTR_SIZE sizeof(uintptr_t)
static void err_sys(const char *msg);
void stack_init(Stack *s) {
s->elements = malloc(STACK_SIZE * PTR_SIZE);
if (!s->elements) {
err_sys("malloc");
}
s->len = 0;
s->cap = STACK_SIZE;
}
void stack_deinit(Stack *s) {
free(s->elements);
}
void push(Stack *s, const void *element) {
if (s->len == s->cap) {
// realloc...
const size_t new_size = s->len << 1;
void *tmp = realloc(s->elements, new_size * PTR_SIZE);
if (!tmp) {
err_sys("realloc");
}
s->elements = tmp;
s->cap = new_size;
}
// get rid of `arithmetic on a pointer to void` you need to change `void *` to `uintptr_t *`
uintptr_t *p = s->elements + s->len * PTR_SIZE;
*p = (uintptr_t) element;
s->len++;
}
void *peek(Stack *s) {
const uintptr_t *p = s->elements + (s->len - 1) * PTR_SIZE;
return (void *)(*p);
}
void *pop(Stack *s) {
void *res = peek(s);
s->len--;
// no need
//if (s->len <= (s->cap >> 2)) {
// // shrink
// const size_t new_size = s->cap >> 1;
// void *tmp = realloc(s->elements, new_size);
// if (!tmp) {
// printf("shrink fail\n");
// exit(EXIT_FAILURE);
// }
// s->elements = tmp;
// s->cap = new_size;
//}
return res;
}
// simple test
int main() {
const int len = 10;
Stack s;
stack_init(&s);
printf("stack input: ");
for (int i = 0; i < len; i++) {
int *p = (int *)malloc(sizeof(int));
if (!p) {
err_sys("malloc test input");
}
*p = i;
push(&s, p);
printf("%d ", i);
}
printf("\nstack output: ");
for (int i = 0; i < len; i++) {
int *p = (int *)pop(&s);
printf("%d ", *p);
free(p);
}
printf("\nlen: %zd, cap: %zd\n", s.len, s.cap);
stack_deinit(&s);
return EXIT_SUCCESS;
}
static void err_sys(const char *msg) {
const size_t buf_len = 255;
char buf[buf_len];
strerror_r(errno, buf, buf_len);
fprintf(stderr, "%s: %s", msg, buf);
exit(EXIT_FAILURE);
}
#include <stdlib.h>
#include <errno.h>
#include <string.h>
typedef struct {
size_t cap;
size_t len;
// we can only push pointer if we want some `generic` fashion...
// actully is a uintptr_t *
void *elements; // or void ** if you prefer
} Stack;
void stack_init(Stack *s);
void stack_deinit(Stack *s);
void push(Stack *s, const void *element);
void *peek(Stack *s);
void *pop(Stack *s);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment