1 /* stack - a dynamically resizing stack
2 * Copyright (c) 2001 Michael B. Allen <mballen@erols.com>
3 *
4 * The MIT License
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25 #include <sd/stack.h>
26 #include <stdlib.h>
27 #include <limits.h>
28 #include <assert.h>
29
30 #include <sd/malloc.h>
31
32 #define SD_STACK_INIT_SIZE 32
33
34 struct __sd_stack {
35 size_t max;
36 size_t sp;
37 size_t size;
38 size_t iter;
39 void **array;
40 };
41
42 /******************************************************************************/
sd_stack_new(size_t max)43 sd_stack_t* sd_stack_new(size_t max)
44 {
45 sd_stack_t* this;
46
47 this = sd_calloc(1, sizeof(sd_stack_t));
48 this->max = max == 0 ? INT_MAX : max;
49 this->size = SD_STACK_INIT_SIZE;
50 this->sp = 0;
51 this->array = sd_calloc(this->size, sizeof(*this->array));
52
53 return this;
54 }
55
56 /******************************************************************************/
sd_stack_delete(sd_stack_t * this,void (* free_data_fn)(void *))57 void sd_stack_delete(sd_stack_t* this, void (*free_data_fn)(void *))
58 {
59 if (!this)
60 return;
61
62 sd_stack_clear(this, free_data_fn);
63
64 free(this->array);
65 free(this);
66 }
67
68 /******************************************************************************/
sd_stack_get_nelem(const sd_stack_t * this)69 size_t sd_stack_get_nelem(const sd_stack_t* this)
70 {
71 return this ? this->sp : -1;
72 }
73
74 /******************************************************************************/
sd_stack_clear(sd_stack_t * this,void (* free_data_fn)(void *))75 void sd_stack_clear(sd_stack_t* this, void (*free_data_fn)(void *))
76 {
77 if (!this)
78 return;
79
80 if (free_data_fn) {
81 while (this->sp > 0) {
82 free_data_fn(this->array[--(this->sp)]);
83 }
84 }
85 }
86
87 /******************************************************************************/
sd_stack_begin(sd_stack_t * this)88 void* sd_stack_begin(sd_stack_t* this)
89 {
90 if (!this)
91 return NULL;
92
93 this->iter = 0;
94 return this->array[this->iter];
95 }
96
97 /******************************************************************************/
sd_stack_next(sd_stack_t * this)98 void* sd_stack_next(sd_stack_t* this)
99 {
100 if (this && this->iter < this->sp)
101 return this->array[this->iter++];
102
103 return NULL;
104 }
105
106 /******************************************************************************/
sd_stack_end(sd_stack_t * this)107 void* sd_stack_end(sd_stack_t* this)
108 {
109 return sd_stack_peek(this);
110 }
111
112 /******************************************************************************/
sd_stack_peek(sd_stack_t * this)113 void* sd_stack_peek(sd_stack_t* this)
114 {
115 if (!this || !this->sp)
116 return NULL;
117
118 return this->array[this->sp - 1];
119 }
120
121 /******************************************************************************/
sd_stack_push(sd_stack_t * this,void * data)122 int sd_stack_push(sd_stack_t* this, void *data)
123 {
124 if (this == NULL)
125 return -1;
126
127 if (this->sp == this->size) {
128 size_t new_size;
129
130 if (this->size == this->max)
131 return -1;
132
133 if (this->size * 2 > this->max) {
134 new_size = this->max;
135 } else {
136 new_size = this->size * 2;
137 }
138
139 this->size = new_size;
140 this->array = sd_realloc(this->array, sizeof(*this->array) * this->size);
141 }
142
143 assert(this->sp <= this->size);
144 this->array[this->sp++] = data;
145 return 0;
146 }
147
148 /******************************************************************************/
sd_stack_pop(sd_stack_t * this)149 void* sd_stack_pop(sd_stack_t* this)
150 {
151 if (this == NULL || this->sp == 0)
152 return NULL;
153
154 if (this->size >= SD_STACK_INIT_SIZE * 4 && this->sp < this->size / 4) {
155 size_t new_size = this->size / 2;
156
157 this->size = new_size;
158 this->array = sd_realloc(this->array, sizeof(*this->array) * this->size);
159 }
160
161 assert(this->sp > 0 && this->sp <= this->size);
162 return this->array[--(this->sp)];
163 }
164
165