qLibc

qstack.c
Go to the documentation of this file.
1/******************************************************************************
2 * qLibc
3 *
4 * Copyright (c) 2010-2015 Seungyoung Kim.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 *****************************************************************************/
28
29/**
30 * @file qstack.c Stack implementation.
31 *
32 * qstack container is a stack implementation. It represents a
33 * last-in-first-out(LIFO). It extends qlist container that allow a linked-list
34 * to be treated as a stack.
35 *
36 * @code
37 * [Conceptional Data Structure Diagram]
38 *
39 * top bottom
40 * DATA PUSH/POP <==> [ C ][ B ][ A ]
41 * (positive index) 0 1 2
42 * (negative index) -3 -2 -1
43 * @endcode
44 *
45 * @code
46 * // create stack
47 * qstack_t *stack = qstack(QSTACK_THREADSAFE);
48 *
49 * // example: integer stack
50 * stack->pushint(stack, 1);
51 * stack->pushint(stack, 2);
52 * stack->pushint(stack, 3);
53 *
54 * printf("popint(): %d\n", stack->popint(stack));
55 * printf("popint(): %d\n", stack->popint(stack));
56 * printf("popint(): %d\n", stack->popint(stack));
57 *
58 * // example: string stack
59 * stack->pushstr(stack, "A string");
60 * stack->pushstr(stack, "B string");
61 * stack->pushstr(stack, "C string");
62 *
63 * char *str = stack->popstr(stack);
64 * printf("popstr(): %s\n", str);
65 * free(str);
66 * str = stack->popstr(stack);
67 * printf("popstr(): %s\n", str);
68 * free(str);
69 * str = stack->popstr(stack);
70 * printf("popstr(): %s\n", str);
71 * free(str);
72 *
73 * // example: object stack
74 * stack->push(stack, "A object", sizeof("A object"));
75 * stack->push(stack, "B object", sizeof("B object"));
76 * stack->push(stack, "C object", sizeof("C object"));
77 *
78 * void *obj = stack->pop(stack, NULL);
79 * printf("pop(): %s\n", (char*)obj);
80 * free(obj);
81 * str = stack->pop(stack, NULL);
82 * printf("pop(): %s\n", (char*)obj);
83 * free(obj);
84 * str = stack->pop(stack, NULL);
85 * printf("pop(): %s\n", (char*)obj);
86 * free(obj);
87 *
88 * // release
89 * stack->free(stack);
90 *
91 * [Output]
92 * popint(): 3
93 * popint(): 2
94 * popint(): 1
95 * popstr(): C string
96 * popstr(): B string
97 * popstr(): A string
98 * pop(): C object
99 * pop(): B object
100 * pop(): A object
101 * @endcode
102 */
103
104#include <stdio.h>
105#include <stdlib.h>
106#include <stdbool.h>
107#include <string.h>
108#include <errno.h>
109#include "qinternal.h"
110#include "containers/qstack.h"
111
112/**
113 * Create a new stack container
114 *
115 * @param options combination of initialization options.
116 *
117 * @return a pointer of malloced qstack_t container, otherwise returns NULL.
118 * @retval errno will be set in error condition.
119 * - ENOMEM : Memory allocation failure.
120 *
121 * @code
122 * qstack_t *stack = qstack(QSTACK_THREADSAFE);
123 * @endcode
124 *
125 * @note
126 * Available options:
127 * - QSTACK_THREADSAFE - make it thread-safe.
128 */
129qstack_t *qstack(int options) {
130 qstack_t *stack = (qstack_t *) malloc(sizeof(qstack_t));
131 if (stack == NULL) {
132 errno = ENOMEM;
133 return NULL;
134 }
135
136 memset((void *) stack, 0, sizeof(qstack_t));
137 stack->list = qlist(options);
138 if (stack->list == NULL) {
139 free(stack);
140 return NULL;
141 }
142
143 // methods
144 stack->setsize = qstack_setsize;
145
146 stack->push = qstack_push;
147 stack->pushstr = qstack_pushstr;
148 stack->pushint = qstack_pushint;
149
150 stack->pop = qstack_pop;
151 stack->popstr = qstack_popstr;
152 stack->popint = qstack_popint;
153 stack->popat = qstack_popat;
154
155 stack->get = qstack_get;
156 stack->getstr = qstack_getstr;
157 stack->getint = qstack_getint;
158 stack->getat = qstack_getat;
159
160 stack->size = qstack_size;
161 stack->clear = qstack_clear;
162 stack->debug = qstack_debug;
163 stack->free = qstack_free;
164
165 return stack;
166}
167
168/**
169 * qstack->setsize(): Sets maximum number of elements allowed in this
170 * stack.
171 *
172 * @param stack qstack container pointer.
173 * @param max maximum number of elements. 0 means no limit.
174 *
175 * @return previous maximum number.
176 */
177 size_t qstack_setsize(qstack_t *stack, size_t max) {
178 return stack->list->setsize(stack->list, max);
179}
180
181/**
182 * qstack->push(): Pushes an element onto the top of this stack.
183 *
184 * @param stack qstack container pointer.
185 * @param data a pointer which points data memory.
186 * @param size size of the data.
187 *
188 * @return true if successful, otherwise returns false.
189 * @retval errno will be set in error condition.
190 * - EINVAL : Invalid argument.
191 * - ENOBUFS : Stack full. Only happens when this stack has set to have
192 * limited number of elements)
193 * - ENOMEM : Memory allocation failure.
194 */
195 bool qstack_push(qstack_t *stack, const void *data, size_t size) {
196 return stack->list->addfirst(stack->list, data, size);
197}
198
199/**
200 * qstack->pushstr(): Pushes a string onto the top of this stack.
201 *
202 * @param stack qstack container pointer.
203 * @param data a pointer which points data memory.
204 * @param size size of the data.
205 *
206 * @return true if successful, otherwise returns false.
207 * @retval errno will be set in error condition.
208 * - EINVAL : Invalid argument.
209 * - ENOBUFS : Stack full. Only happens when this stack has set to have
210 * limited number of elements.
211 * - ENOMEM : Memory allocation failure.
212 */
213 bool qstack_pushstr(qstack_t *stack, const char *str) {
214 if (str == NULL) {
215 errno = EINVAL;
216 return false;
217 }
218 return stack->list->addfirst(stack->list, str, strlen(str) + 1);
219}
220
221/**
222 * qstack->pushint(): Pushes a integer onto the top of this stack.
223 *
224 * @param stack qstack container pointer.
225 * @param num integer data.
226 *
227 * @return true if successful, otherwise returns false.
228 * @retval errno will be set in error condition.
229 * - ENOBUFS : Stack full. Only happens when this stack has set to have
230 * limited number of elements.
231 * - ENOMEM : Memory allocation failure.
232 */
233 bool qstack_pushint(qstack_t *stack, int64_t num) {
234 return stack->list->addfirst(stack->list, &num, sizeof(num));
235}
236
237/**
238 * qstack->pop(): Removes a element at the top of this stack and returns
239 * that element.
240 *
241 * @param stack qstack container pointer.
242 * @param size if size is not NULL, element size will be stored.
243 *
244 * @return a pointer of malloced element, otherwise returns NULL.
245 * @retval errno will be set in error condition.
246 * - ENOENT : Stack is empty.
247 * - ENOMEM : Memory allocation failure.
248 */
249 void *qstack_pop(qstack_t *stack, size_t *size) {
250 return stack->list->popfirst(stack->list, size);
251}
252
253/**
254 * qstack->popstr(): Removes a element at the top of this stack and
255 * returns that element.
256 *
257 * @param stack qstack container pointer.
258 *
259 * @return a pointer of malloced string element, otherwise returns NULL.
260 * @retval errno will be set in error condition.
261 * - ENOENT : Stack is empty.
262 * - ENOMEM : Memory allocation failure.
263 *
264 * @note
265 * The string element should be pushed through pushstr().
266 */
267 char *qstack_popstr(qstack_t *stack) {
268 size_t strsize;
269 char *str = stack->list->popfirst(stack->list, &strsize);
270 if (str != NULL) {
271 str[strsize - 1] = '\0'; // just to make sure
272 }
273
274 return str;
275}
276
277/**
278 * qstack->popint(): Removes a integer at the top of this stack and
279 * returns that element.
280 *
281 * @param stack qstack container pointer.
282 *
283 * @return an integer value, otherwise returns 0.
284 * @retval errno will be set in error condition.
285 * - ENOENT : Stack is empty.
286 * - ENOMEM : Memory allocation failure.
287 *
288 * @note
289 * The integer element should be pushed through pushint().
290 */
291int64_t qstack_popint(qstack_t *stack) {
292 int64_t num = 0;
293 int64_t *pnum = stack->list->popfirst(stack->list, NULL);
294 if (pnum != NULL) {
295 num = *pnum;
296 free(pnum);
297 }
298
299 return num;
300}
301
302/**
303 * qstack->popat(): Returns and remove the element at the specified
304 * position in this stack.
305 *
306 * @param stack qstack container pointer.
307 * @param index index at which the specified element is to be inserted
308 * @param size if size is not NULL, element size will be stored.
309 *
310 * @return a pointer of malloced element, otherwise returns NULL.
311 * @retval errno will be set in error condition.
312 * - ERANGE : Index out of range.
313 * - ENOMEM : Memory allocation failure.
314 *
315 * @note
316 * Negative index can be used for addressing a element from the bottom in
317 * this stack. For example, index -1 will always pop a element which is pushed
318 * at very first time.
319 */
320 void *qstack_popat(qstack_t *stack, int index, size_t *size) {
321 return stack->list->popat(stack->list, index, size);
322}
323
324/**
325 * qstack->get(): Returns an element at the top of this stack without
326 * removing it.
327 *
328 * @param stack qstack container pointer.
329 * @param size if size is not NULL, element size will be stored.
330 * @param newmem whether or not to allocate memory for the element.
331 * @retval errno will be set in error condition.
332 * - ENOENT : Stack is empty.
333 * - ENOMEM : Memory allocation failure.
334 *
335 * @return a pointer of malloced element, otherwise returns NULL.
336 */
337 void *qstack_get(qstack_t *stack, size_t *size, bool newmem) {
338 return stack->list->getfirst(stack->list, size, newmem);
339}
340
341/**
342 * qstack->getstr(): Returns an string at the top of this stack without
343 * removing it.
344 *
345 * @param stack qstack container pointer.
346 *
347 * @return a pointer of malloced string element, otherwise returns NULL.
348 * @retval errno will be set in error condition.
349 * - ENOENT : Stack is empty.
350 * - ENOMEM : Memory allocation failure.
351 *
352 * @note
353 * The string element should be pushed through pushstr().
354 */
355 char *qstack_getstr(qstack_t *stack) {
356 size_t strsize;
357 char *str = stack->list->getfirst(stack->list, &strsize, true);
358 if (str != NULL) {
359 str[strsize - 1] = '\0'; // just to make sure
360 }
361
362 return str;
363}
364
365/**
366 * qstack->getint(): Returns an integer at the top of this stack without
367 * removing it.
368 *
369 * @param stack qstack container pointer.
370 *
371 * @return an integer value, otherwise returns 0.
372 * @retval errno will be set in error condition.
373 * - ENOENT : Stack is empty.
374 * - ENOMEM : Memory allocation failure.
375 *
376 * @note
377 * The integer element should be pushed through pushint().
378 */
379int64_t qstack_getint(qstack_t *stack) {
380 int64_t num = 0;
381 int64_t *pnum = stack->list->getfirst(stack->list, NULL, true);
382 if (pnum != NULL) {
383 num = *pnum;
384 free(pnum);
385 }
386
387 return num;
388}
389
390/**
391 * qstack->getat(): Returns an element at the specified position in this
392 * stack without removing it.
393 *
394 * @param stack qstack container pointer.
395 * @param index index at which the specified element is to be inserted
396 * @param size if size is not NULL, element size will be stored.
397 * @param newmem whether or not to allocate memory for the element.
398 *
399 * @return a pointer of element, otherwise returns NULL.
400 * @retval errno will be set in error condition.
401 * - ERANGE : Index out of range.
402 * - ENOMEM : Memory allocation failure.
403 *
404 * @note
405 * Negative index can be used for addressing a element from the bottom in this
406 * stack. For example, index -1 will always get a element which is pushed at
407 * very first time.
408 */
409 void *qstack_getat(qstack_t *stack, int index, size_t *size, bool newmem) {
410 return stack->list->getat(stack->list, index, size, newmem);
411}
412
413/**
414 * qstack->size(): Returns the number of elements in this stack.
415 *
416 * @param stack qstack container pointer.
417 *
418 * @return the number of elements in this stack.
419 */
420 size_t qstack_size(qstack_t *stack) {
421 return stack->list->size(stack->list);
422}
423
424/**
425 * qstack->clear(): Removes all of the elements from this stack.
426 *
427 * @param stack qstack container pointer.
428 */
429 void qstack_clear(qstack_t *stack) {
430 stack->list->clear(stack->list);
431}
432
433/**
434 * qstack->debug(): Print out stored elements for debugging purpose.
435 *
436 * @param stack qstack container pointer.
437 * @param out output stream FILE descriptor such like stdout, stderr.
438 *
439 * @return true if successful, otherwise returns false.
440 */
441 bool qstack_debug(qstack_t *stack, FILE *out) {
442 return stack->list->debug(stack->list, out);
443}
444
445/**
446 * qstack->free(): Free qstack_t
447 *
448 * @param stack qstack container pointer.
449 *
450 * @return always returns true.
451 */
452 void qstack_free(qstack_t *stack) {
453 stack->list->free(stack->list);
454 free(stack);
455}
qlist
qlist_t * qlist(int options)
Create new qlist_t linked-list container.
Definition qlist.c:124
qstack_popat
void * qstack_popat(qstack_t *stack, int index, size_t *size)
qstack->popat(): Returns and remove the element at the specified position in this stack.
Definition qstack.c:320
qstack_clear
void qstack_clear(qstack_t *stack)
qstack->clear(): Removes all of the elements from this stack.
Definition qstack.c:429
qstack_pushint
bool qstack_pushint(qstack_t *stack, int64_t num)
qstack->pushint(): Pushes a integer onto the top of this stack.
Definition qstack.c:233
qstack_setsize
size_t qstack_setsize(qstack_t *stack, size_t max)
qstack->setsize(): Sets maximum number of elements allowed in this stack.
Definition qstack.c:177
qstack_free
void qstack_free(qstack_t *stack)
qstack->free(): Free qstack_t
Definition qstack.c:452
qstack_popint
int64_t qstack_popint(qstack_t *stack)
qstack->popint(): Removes a integer at the top of this stack and returns that element.
Definition qstack.c:291
qstack_pushstr
bool qstack_pushstr(qstack_t *stack, const char *str)
qstack->pushstr(): Pushes a string onto the top of this stack.
Definition qstack.c:213
qstack_size
size_t qstack_size(qstack_t *stack)
qstack->size(): Returns the number of elements in this stack.
Definition qstack.c:420
qstack
qstack_t * qstack(int options)
Create a new stack container.
Definition qstack.c:129
qstack_pop
void * qstack_pop(qstack_t *stack, size_t *size)
qstack->pop(): Removes a element at the top of this stack and returns that element.
Definition qstack.c:249
qstack_get
void * qstack_get(qstack_t *stack, size_t *size, bool newmem)
qstack->get(): Returns an element at the top of this stack without removing it.
Definition qstack.c:337
qstack_getstr
char * qstack_getstr(qstack_t *stack)
qstack->getstr(): Returns an string at the top of this stack without removing it.
Definition qstack.c:355
qstack_getat
void * qstack_getat(qstack_t *stack, int index, size_t *size, bool newmem)
qstack->getat(): Returns an element at the specified position in this stack without removing it.
Definition qstack.c:409
qstack_popstr
char * qstack_popstr(qstack_t *stack)
qstack->popstr(): Removes a element at the top of this stack and returns that element.
Definition qstack.c:267
qstack_getint
int64_t qstack_getint(qstack_t *stack)
qstack->getint(): Returns an integer at the top of this stack without removing it.
Definition qstack.c:379
qstack_debug
bool qstack_debug(qstack_t *stack, FILE *out)
qstack->debug(): Print out stored elements for debugging purpose.
Definition qstack.c:441
qstack_push
bool qstack_push(qstack_t *stack, const void *data, size_t size)
qstack->push(): Pushes an element onto the top of this stack.
Definition qstack.c:195