wiimote-quiz/stack.c at master · bsl/wiimote-quiz · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdlib.h>
#include <stdbool.h>

#include "stack.h"

/* - - - - - - - - - - - - - - - - - - - - */

struct stack {
  int size;
  int avail;
  void **ps;
};

/* - - - - - - - - - - - - - - - - - - - - */

static void stack_resize(stack_t s);
static void stack_grow(stack_t s);
static void stack_shrink(stack_t s);

/* - - - - - - - - - - - - - - - - - - - - */

stack_t
stack_new()
{
  stack_t s = malloc(sizeof(*s));
  if (s != NULL) {
    s->size = 0;
    s->avail = 0;
    s->ps = NULL;
  }
  return s;
}

bool
stack_is_empty(stack_t s)
{
  return s->size == 0;
}

void
stack_push(stack_t s, void *p)
{
  if (s->size + 1 > s->avail) {
    stack_grow(s);
  }
  s->ps[s->size] = p;
  s->size++;
}

void *
stack_pop(stack_t s)
{
  s->size--;
  void *p = s->ps[s->size];
  if (s->size < s->avail/2) {
    stack_shrink(s);
  }
  return p;
}

void
stack_free(stack_t s)
{
  if (s->ps) {
    free(s->ps);
  }
  free(s);
}

static void
stack_resize(stack_t s)
{
  s->ps = realloc(s->ps, sizeof(void *)*s->avail);
}

static void
stack_grow(stack_t s)
{
  s->avail = s->avail == 0 ? 1 : s->avail*2;
  stack_resize(s);
}

static void
stack_shrink(stack_t s)
{
  s->avail /= 2;
  stack_resize(s);
}