1 /* stack.c -- Stack routines for Khepera
2 * Created: Wed Nov 9 19:40:00 1994 by faith@dict.org
3 * Copyright 1994, 1995, 2002 Rickard E. Faith (faith@dict.org)
4 * Copyright 2002-2008 Aleksey Cheusov (vle@gmx.net)
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 * \section{Stack Routines}
26 *
27 * \intro The stack routines provide support for a general stack of
28 * pointers to "void". Because of the simplicity of the stack object, no
29 * statistics are maintained. (Althought the list routines can also be used
30 * as a stack, the stack implemented here is more efficient.)
31 *
32 */
33
34 #include "maaP.h"
35
36 typedef struct data {
37 const void *datum;
38 struct data *prev;
39 } *dataType;
40
41 typedef struct stack {
42 struct data *data;
43 } *stackType;
44
45 /* \doc |stk_create| initializes a stack object. */
46
stk_create(void)47 stk_Stack stk_create(void)
48 {
49 stackType s;
50
51 s = xmalloc(sizeof(struct stack));
52 s->data = NULL;
53
54 return s;
55 }
56
57 /* \doc |stk_destroy| destroys all memory associated with the |stack|. The
58 memory used by data is \emph{not} freed---this memory is the
59 responsibility of the user. */
60
stk_destroy(stk_Stack stack)61 void stk_destroy(stk_Stack stack)
62 {
63 while (!stk_isempty(stack)){
64 stk_pop(stack);
65 }
66 xfree(stack); /* terminal */
67 }
68
69 /* \doc |stk_push| places |datum| on the top of the |stack|. */
70
stk_push(stk_Stack stack,void * datum)71 void stk_push(stk_Stack stack, void *datum)
72 {
73 stackType s = (stackType)stack;
74 dataType d = (dataType)malloc(sizeof(struct data));
75
76 d->datum = datum;
77 d->prev = s->data;
78 s->data = d;
79 }
80
81 /* \doc |stk_pop| removes the top of the |stack| and returns the pointer.
82 If the |stack| is empty, |stk_pop| returns "NULL". */
83
stk_pop(stk_Stack stack)84 void *stk_pop(stk_Stack stack)
85 {
86 stackType s = (stackType)stack;
87 void *datum = NULL;
88
89 if (s->data) {
90 dataType old = s->data;
91
92 datum = __UNCONST(old->datum); /* Discard const */
93 s->data = s->data->prev;
94
95 free(old);
96 }
97
98 return datum;
99 }
100
101 /* \doc |stk_isempty| return 1 if |stack| is empty, or 0 otherwise.
102 */
103
stk_isempty(stk_Stack stack)104 int stk_isempty(stk_Stack stack)
105 {
106 stackType s = (stackType)stack;
107
108 if (s->data) {
109 return 0;
110 }else{
111 return 1;
112 }
113 }
114
115 /* \doc |stk_top| returns a pointer to the datum on the top of the |stack|,
116 but does \emph{not} remove this datum from the |stack|. If the |stack|
117 is empty, |stk_pop| returns "NULL". */
118
stk_top(stk_Stack stack)119 void *stk_top(stk_Stack stack)
120 {
121 stackType s = (stackType)stack;
122
123 if (s->data)
124 return __UNCONST(s->data->datum); /* Discard const */
125
126 return NULL;
127 }
128