1 /*
2 * Copyright (c) 2014 Dave Vasilevsky <dave@vasilevsky.ca>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25 #include "stack.h"
26
27 #include <stdlib.h>
28
29 /* Ensure a capacity of cap */
sqfs_stack_capacity(sqfs_stack * s,size_t cap)30 static sqfs_err sqfs_stack_capacity(sqfs_stack *s, size_t cap) {
31 char *items;
32 if (cap <= s->capacity)
33 return SQFS_OK;
34
35 items = realloc(s->items, cap * s->value_size);
36 if (!items)
37 return SQFS_ERR;
38
39 s->items = items;
40 s->capacity = cap;
41 return SQFS_OK;
42 }
43
44 /* Calculate the next capacity to use */
45 #define CAPACITY_DEFAULT 8
46 #define CAPACITY_RATIO 3 / 2
sqfs_stack_next_capacity(size_t cap)47 static size_t sqfs_stack_next_capacity(size_t cap) {
48 size_t n;
49
50 if (cap == 0)
51 return CAPACITY_DEFAULT;
52
53 n = cap * CAPACITY_RATIO;
54 if (n <= cap)
55 return cap + 1;
56 return n;
57 }
58
59 /* Grow by one */
sqfs_stack_grow(sqfs_stack * s)60 static sqfs_err sqfs_stack_grow(sqfs_stack *s) {
61 if (s->size == s->capacity) {
62 sqfs_err err = sqfs_stack_capacity(s,
63 sqfs_stack_next_capacity(s->capacity));
64 if (err)
65 return err;
66 }
67 s->size++;
68 return SQFS_OK;
69 }
70
71
sqfs_stack_create(sqfs_stack * s,size_t vsize,size_t initial,sqfs_stack_free_t freer)72 sqfs_err sqfs_stack_create(sqfs_stack *s, size_t vsize, size_t initial,
73 sqfs_stack_free_t freer) {
74 s->value_size = vsize;
75 s->freer = freer;
76 s->items = NULL;
77 s->capacity = s->size = 0;
78 return sqfs_stack_capacity(s, initial);
79 }
80
sqfs_stack_init(sqfs_stack * s)81 void sqfs_stack_init(sqfs_stack *s) {
82 s->items = NULL;
83 s->capacity = 0;
84 }
85
sqfs_stack_destroy(sqfs_stack * s)86 void sqfs_stack_destroy(sqfs_stack *s) {
87 while (sqfs_stack_pop(s))
88 ; /* pass */
89 free(s->items);
90 sqfs_stack_init(s);
91 }
92
sqfs_stack_push(sqfs_stack * s,void * vout)93 sqfs_err sqfs_stack_push(sqfs_stack *s, void *vout) {
94 sqfs_err err = sqfs_stack_grow(s);
95 if (err)
96 return err;
97 return sqfs_stack_top(s, vout);
98 }
99
sqfs_stack_pop(sqfs_stack * s)100 bool sqfs_stack_pop(sqfs_stack *s) {
101 void *v;
102
103 if (s->size == 0)
104 return false;
105
106 sqfs_stack_top(s, &v);
107 if (s->freer)
108 s->freer(v);
109 s->size--;
110 return true;
111 }
112
sqfs_stack_size(sqfs_stack * s)113 size_t sqfs_stack_size(sqfs_stack *s) {
114 return s->size;
115 }
116
sqfs_stack_at(sqfs_stack * s,size_t i,void * vout)117 sqfs_err sqfs_stack_at(sqfs_stack *s, size_t i, void *vout) {
118 if (i >= s->size)
119 return SQFS_ERR;
120
121 *(void**)vout = s->items + i * s->value_size;
122 return SQFS_OK;
123 }
124
sqfs_stack_top(sqfs_stack * s,void * vout)125 sqfs_err sqfs_stack_top(sqfs_stack *s, void *vout) {
126 if (s->size == 0)
127 return SQFS_ERR;
128
129 return sqfs_stack_at(s, s->size - 1, vout);
130 }
131