queue_impl.h
10.5 KB
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
/**
* \file scot/queue_impl.h
* \author Georg Steffers <georg@steffers.org>
* \brief Templates of functions for handling queues based on typesafe lists.
*
* The Macros here generate the implementation for the interface to queues
* based on typesafe linked lists.
* \anchor onlyfunc_queue
* \attention
* All documentation here does document the functions that are created by
* the macros, as the macros themself are pretty easy and all used the same.
* They are called with a type, that MUST be one word (use typedef if needed)
* and generates the function defined with their value.
*
* Copyright (C)2006 Georg Steffers <georg@steffers.org>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef QUEUE_IMPL_H
#define QUEUE_IMPL_H
#include <scot/list.h>
/**
* \internal
* \param type the datatype that this queue code should handle.
* \param a a variable holding a pointer to list_[type]_node_t.
*
* \pre Type must be a single word typename. If one wants
* to use e.g. lists of structs one has to use typedef
* to create a single word type name like this:
* typedef struct mystruct_t mystruct_t;
* a must be a valid pointer to a list_[type]_node_t.
* \returns \a a cast to a pointer of queue_[type]_node_t.
* \post None
*
* \brief Cast a pointer to queue_[type]_node_t.
*
* FIXME: I should check better the validity of \a a.
*/
#define QUEUE(type, a) (queue_ ## type ## _node_t *) (a)
extern const char *queue_err_msg[];
#ifdef GEN_LOCAL
# define STATIC static
#else
# define STATIC
#endif
/**
* \attention
* Only the generated function is explained here, for the reason look
* \ref onlyfunc_queue "here".
*
* \param anchor a pointer that should contain the list anchor.
* \pre GEN_LIST_NEW(type) has to be called previously.
* \return NULL on error, but only if no exceptions are used.
* If exceptions are used an exception is thrown on error.
* On success a pointer to the newly created list_anchor
* will be returned.
* \retval NULL if an error occurs and no exceptions are used.
* \retval !=NULL the pointer to the newly created list anchor.
* \post enough memory on the heap.
*
* \brief template for queue constructor.
*
* this simply calls list_[type]_new(), that must be generated previously
* by a call of GEN_LIST_NEW(type).
*/
#define GEN_QUEUE_NEW(type) \
STATIC \
queue_ ## type ## _node_t * \
queue_ ## type ## _new (queue_ ## type ## _node_t *anchor) \
{ \
return anchor = QUEUE (type, \
list_ ## type ## _new (LIST (type, anchor))); \
}
/**
* \attention
* Only the generated function is explained here, for the reason look
* \ref onlyfunc_queue "here".
*
* \param anchor a pointer that should contain the list anchor.
* \pre GEN_LIST_FREE(type) has to be called previously.
* \return Nothing
* \post The list is completely removed from the heap.
*
* \brief template for queue destructor.
*
* this simply calls list_[type]_free(), that must be generated previously
* by a call of GEN_LIST_FREE(type).
*/
#define GEN_QUEUE_FREE(type) \
STATIC \
void \
queue_ ## type ## _free (queue_ ## type ## _node_t *anchor) \
{ \
list_ ## type ## _free (LIST (type, anchor)); \
}
/**
* \attention
* Only the generated function is explained here, for the reason look
* \ref onlyfunc_queue "here".
*
* \param anchor a pointer that should contain the list anchor.
* \param e A pointer to a variable of the \a type, the
* list was created for.
* \pre GEN_LIST_LAST(type) and GEN_LIST_INSERT(type)
* has to be called previously.
* \return The inserted element \a e.
* \post Element \a e is enqueued in the queue pointed by
* \a anchor.
*
* \brief template for a function that enqueues a value into a queue.
*
* To add a value into a queue meens to put it at the end of the queue.
* That is done by getting the last node of the list and insert a value
* behind it.
*/
#define GEN_QUEUE_ENQUEUE(type) \
queue_ ## type ## _node_t * \
queue_ ## type ## _enqueue ( \
queue_ ## type ## _node_t *anchor, \
const type *e) \
{ \
return QUEUE (type, list_ ## type ## _insert ( \
list_ ## type ## _last (LIST (type, anchor)), e)); \
}
/**
* \attention
* Only the generated function is explained here, for the reason look
* \ref onlyfunc_queue "here".
*
* \param anchor a pointer that should contain the list anchor.
* \pre GEN_LIST_NEXT(type), GEN_LIST_RETRIVE(type)
* GEN_LIST_ISEMPTY(type) and GEN_LIST_DELETE(type)
* has to be called previously.
* \return The dequeued element.
* \post One Element is dequeued from the queue pointed to
* by \a anchor.
*
* \brief template for a function that dequeues a value from a queue.
*
* Dequeue means get and remove the first element from the queue.
* This is done here.
*/
#define GEN_QUEUE_DEQUEUE(type) \
STATIC \
type * \
queue_ ## type ## _dequeue (queue_ ## type ## _node_t *anchor) \
{ \
list_ ## type ## _node_t *next; \
const type *e; \
\
next = list_ ## type ## _next (LIST (type, anchor)); \
e = list_ ## type ## _retrive (next); \
\
if (! list_ ## type ## _isempty (next)) \
list_ ## type ## _delete (next); \
\
return (type *) e; \
}
/**
* \attention
* Only the generated function is explained here, for the reason look
* \ref onlyfunc_queue "here".
*
* \param anchor a pointer that should contain the list anchor.
* \pre GEN_LIST_NEXT(type) and GEN_LIST_RETRIVE(type)
* has to be called previously.
* \return The next element in the queue.
* \post None
*
* \brief get next element in the queue without dequeueing it.
*/
#define GEN_QUEUE_TOP(type) \
STATIC \
type * \
queue_ ## type ## _top ( \
queue_ ## type ## _node_t *anchor) \
{ \
return list_ ## type ## _retrive ( \
list_ ## type ## _next (LIST (type, anchor))); \
}
/**
* \param type the datatype that this list code should handle.
* \pre Type must be a single word typename. If one wants
* to use e.g. lists of structs one has to use typedef
* to create a single word type name like this:
* typedef struct mystruct_t mystruct_t;
* GEN_LIST_IMPL(type) should be called before this.
* \return Nothing
* \post The functions, struct and globals to handle queues
* based on typesave
* lists for the given datatype are generated within the
* calling build file.
*
* \brief this creates all functions, structs and globals needed for a
* queue based on typesafe list of a given \a type.
*
* In detail the following is created by this macro:\n
* \li <b>struct queue_[type]_node_t</b>: This is the structure a queue
* is constructed of. Practically this just contains an instance of a
* list_[type]_node_t, as queues are completely based on lists and does
* not add further information.
* \li all functions created by the macros defined within this file.
*/
#define GEN_QUEUE_IMPL(type) \
struct queue_ ## type ## _node_t \
{ \
struct list_ ## type ## _node_t list; \
}; \
\
GEN_QUEUE_NEW (type) \
GEN_QUEUE_FREE (type) \
GEN_QUEUE_ENQUEUE (type) \
GEN_QUEUE_DEQUEUE (type) \
GEN_QUEUE_TOP (type)
#endif /* QUEUE_IMPL_H */