wcalc  2.5
About: Wcalc is a natural-expression command-line calculator.
  Fossies Dox: wcalc-2.5.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

list.c
Go to the documentation of this file.
1 #ifdef HAVE_CONFIG_H
2 # include "config.h"
3 #endif
4 
5 /* System Headers */
6 #include <stdlib.h> /* for free() */
7 #include <string.h> /* for memset() */
8 
9 /* Internal Headers */
10 #include "list.h"
11 
12 /* structures for constructing the list */
13 struct _listheader {
14  struct _listheader *next;
15  void *payload;
17 };
18 
19 struct _list {
20  struct _listheader *head;
21  struct _listheader *tail;
22  unsigned long len;
23  struct _list *pool_next;
24  struct _list *pool_prev;
25 };
26 
28  struct _listheader *cur;
30 };
31 
32 struct cleanup {
33  struct cleanup *next;
34  void *data;
35 };
36 
37 static List lPool = NULL;
38 static List lPoolUsed = NULL;
39 static unsigned long long lPoolSize = 0; /* for exponential growth */
40 static struct cleanup *lCleanupPool = NULL;
41 static inline List get_l(void);
42 static void fill_l_pool(void);
43 
44 static struct _listheader *lhPool = NULL;
45 static unsigned long long lhPoolSize = 0; /* for exponential growth */
46 static struct cleanup *lhCleanupPool = NULL;
47 static inline struct _listheader *get_lh(void);
48 static void fill_lh_pool(void);
49 static void poolReturn(struct _listheader *lh);
50 
51 /* This sets up the memory pool(s) */
52 void lists_init(void)
53 { /*{{{ */
54  fill_lh_pool();
55  fill_l_pool();
56 } /*}}} */
57 
58 /* This clean up the memory pool(s) */
59 void lists_cleanup(void)
60 { /*{{{ */
61  struct cleanup *freec;
62 
63  while (lhCleanupPool != NULL) {
64  freec = lhCleanupPool;
65  struct _listheader *freeme = freec->data;
67  free(freeme);
68  free(freec);
69  }
70  while (lCleanupPool != NULL) {
71  freec = lCleanupPool;
72  List freeme = freec->data;
74  free(freeme);
75  free(freec);
76  }
77 } /*}}} */
78 
79 /* This returns a struct to the pool */
80 void poolReturn(struct _listheader *lh)
81 { /*{{{ */
82  memset(lh, 0, sizeof(struct _listheader));
83  lh->pool_next = lhPool;
84  lhPool = lh;
85 } /*}}} */
86 
87 /* This fills the list header memory pool with 1024 items (or doubles the pool
88  * size) */
89 static void fill_lh_pool(void)
90 { /*{{{ */
91  struct _listheader *tlist;
92  struct _listheader *temp;
93  struct cleanup *ch;
94  size_t newobjcount;
95  size_t i;
96 
97  newobjcount = (lhPoolSize == 0) ? 1024 : lhPoolSize;
98  tlist = calloc(newobjcount, sizeof(struct _listheader));
99  ch = calloc(1, sizeof(struct cleanup));
100  ch->data = tlist;
101  ch->next = lhCleanupPool;
102  lhCleanupPool = ch;
103  for (i = 0; i < newobjcount; ++i) {
104  temp = &(tlist[i]);
105  temp->pool_next = lhPool;
106  lhPool = temp;
107  }
108  lhPoolSize += newobjcount;
109 } /*}}} */
110 
111 /* This fills the list item memory pool with 2 items (or doubles the pool
112  * size) */
113 static void fill_l_pool(void)
114 { /*{{{ */
115  size_t i, newobjcount;
116  List temp;
117  List tlist;
118  struct cleanup *ch;
119 
120  newobjcount = (lPoolSize == 0) ? 2 : lPoolSize;
121  tlist = calloc(newobjcount, sizeof(struct _list));
122  ch = calloc(1, sizeof(struct cleanup));
123  ch->data = tlist;
124  ch->next = lCleanupPool;
125  lCleanupPool = ch;
126  for (i = 0; i < newobjcount; ++i) {
127  temp = &(tlist[i]);
128  temp->pool_next = lPool;
129  lPool = temp;
130  }
131  lPoolSize += newobjcount;
132 } /*}}} */
133 
134 /* This frees up the memory allocated by the list */
135 void freeList(List *lst)
136 { /*{{{ */
137  List thelist;
138 
139  if (!lst) {
140  return;
141  }
142 
143  thelist = *lst;
144  if (!thelist) {
145  return;
146  }
147 
148  while (thelist->len > 0 && thelist->head != NULL) {
149  struct _listheader *h = thelist->head;
150 
151  thelist->head = h->next;
152  thelist->len--;
153  poolReturn(h);
154  }
155  if (lPoolUsed == thelist) {
156  lPoolUsed = thelist->pool_next;
157  }
158  if (thelist->pool_next) {
159  thelist->pool_next->pool_prev = thelist->pool_prev;
160  }
161  if (thelist->pool_prev) {
162  thelist->pool_prev->pool_next = thelist->pool_next;
163  }
164  thelist->pool_next = lPool;
165  thelist->pool_prev = NULL;
166  lPool = thelist;
167  *lst = NULL;
168 } /*}}} */
169 
170 /* this fetches a new list header from the pool */
171 static inline struct _listheader *get_lh(void) /*{{{ */
172 {
173  struct _listheader *lh;
174 
175  if (NULL == lhPool) {
176  fill_lh_pool();
177  }
178  lh = lhPool;
179  lhPool = lh->pool_next;
180  lh->pool_next = NULL;
181  return lh;
182 } /*}}} */
183 
184 /* this fetches a new list from the pool */
185 static inline List get_l(void)
186 { /*{{{ */
187  List l;
188 
189  if (NULL == lPool) {
190  fill_l_pool();
191  }
192  l = lPool;
193  lPool = l->pool_next;
194  l->pool_next = lPoolUsed;
195  if (lPoolUsed) {
196  lPoolUsed->pool_prev = l;
197  }
198  lPoolUsed = l;
199  lPoolUsed->pool_prev = NULL;
200  return l;
201 } /*}}} */
202 
203 /* This adds "addme" to the end of the list */
204 void addToList(List *lst,
205  void *addme)
206 { /*{{{ */
207  List list;
208  struct _listheader *pl;
209 
210  pl = get_lh();
211  pl->payload = addme;
212  pl->next = NULL;
213  if (!lst) {
214  return;
215  }
216  list = *lst;
217  if (!list) {
218  list = *lst = get_l();
219  list->tail = list->head = pl;
220  list->len = 1;
221  } else {
222  if (list->tail) {
223  list->tail->next = pl;
224  list->tail = pl;
225  list->len++;
226  } else {
227  list->tail = list->head = pl;
228  list->len = 1;
229  }
230  }
231 } /*}}} */
232 
233 /* This adds "addme" to the head of the list */
234 void addToListHead(List *lst,
235  void *addme)
236 { /*{{{ */
237  List list;
238  struct _listheader *pl;
239 
240  pl = get_lh();
241  pl->payload = addme;
242  pl->next = NULL;
243  if (!lst) {
244  return;
245  }
246  list = *lst;
247  if (!list) {
248  list = *lst = get_l();
249  list->tail = list->head = pl;
250  list->len = 1;
251  } else {
252  if (list->head) {
253  pl->next = list->head;
254  list->head = pl;
255  list->len++;
256  } else {
257  list->tail = list->head = pl;
258  list->len = 1;
259  }
260  }
261 } /*}}} */
262 
263 /* This removes the front of the list from the list and returns it */
264 void *getHeadOfList(List list)
265 { /*{{{ */
266  void *payload;
267  struct _listheader *pl;
268 
269  if (!list || !list->head) {
270  return NULL;
271  }
272  payload = list->head->payload;
273  pl = list->head;
274  list->head = list->head->next;
275  poolReturn(pl);
276  list->len--;
277  if (list->len == 0) {
278  list->head = list->tail = NULL;
279  }
280  return payload;
281 } /*}}} */
282 
283 /* This returns the n'th element of the list, as if the list was an array */
285  size_t n)
286 { /*{{{ */
287  struct _listheader *pl;
288  size_t counter;
289 
290  if (!list || !list->head || (list->len <= n)) {
291  return NULL;
292  }
293  pl = list->head;
294  for (counter = 1; counter <= n; counter++) {
295  if (pl->next == NULL) {
296  return NULL;
297  }
298  pl = pl->next;
299  }
300  return pl->payload;
301 } /*}}} */
302 
303 /* This returns the n'th element of the list, as if the list was an array,
304  * and removes it from the list */
305 void *getListElement(List list,
306  size_t n)
307 { /*{{{ */
308  struct _listheader *pl;
309  void *payload = NULL;
310  struct _listheader *returnme;
311 
312  if (!list || !list->head || (list->len <= n)) {
313  return NULL;
314  }
315  pl = list->head;
316  if (n > 0) {
317  size_t counter;
318  for (counter = 1; counter < n; counter++) {
319  if (pl->next == NULL) {
320  return NULL;
321  }
322  pl = pl->next;
323  }
324  if (pl->next) {
325  payload = pl->next->payload;
326  returnme = pl->next;
327  pl->next = pl->next->next;
328  poolReturn(returnme);
329  }
330  } else {
331  payload = pl->payload;
332  returnme = pl;
333  list->head = pl->next;
334  if (list->tail == returnme) {
335  list->tail = NULL;
336  }
337  }
338  list->len--;
339  return payload;
340 } /*}}} */
341 
342 /* This returns the head of the list */
343 inline void *peekAheadInList(List list)
344 { /*{{{ */
345  if (list && list->head) {
346  return list->head->payload;
347  }
348  return NULL;
349 } /*}}} */
350 
351 /* This tells you how many items there are in the list */
352 inline size_t listLen(List list)
353 { /*{{{ */
354  if (list) {
355  return list->len;
356  } else {
357  return 0;
358  }
359 } /*}}} */
360 
361 /* This returns a list iterator to a list */
363 { /*{{{ */
364  ListIterator li;
365 
366  if (!list) {
367  return NULL;
368  }
369  li = malloc(sizeof(struct _list_iterator));
370  li->cur = list->head;
371  li->l = list;
372  return li;
373 } /*}}} */
374 
375 /* This returns the value of the current element in the list Iterator */
377 { /*{{{ */
378  if (!li || !(li->cur)) {
379  return NULL;
380  }
381  return li->cur->payload;
382 } /*}}} */
383 
384 /* This iterates a list iterator */
386 { /*{{{ */
387  void *payload;
388 
389  if (!li || !(li->cur)) {
390  return NULL;
391  }
392  payload = li->cur->payload;
393  li->cur = li->cur->next;
394  return payload;
395 } /*}}} */
396 
397 /* This sets the iterator back to the beginning */
399 { /*{{{ */
400  if (li) {
401  li->cur = li->l->head;
402  }
403 } /*}}} */
404 
405 /* This frees up a list iterator */
407 { /*{{{ */
408  if (li) {
409  free(li);
410  }
411 } /*}}} */
412 
413 /* This searches the list for a specific value, and removes it */
415  void *item)
416 { /*{{{*/
417  struct _listheader *pl;
418 
419  if (!list || !list->head) {
420  return;
421  }
422  pl = list->head;
423  if (pl->payload == item) {
424  if (list->head == list->tail) {
425  list->head = list->tail = NULL;
426  list->len = 0;
427  } else {
428  list->len--;
429  list->head = list->head->next;
430  }
431  poolReturn(pl);
432  } else {
433  while (pl->next && pl->next != list->tail) {
434  if (pl->next->payload == item) {
435  break;
436  }
437  if (pl->next->next == NULL) {
438  return;
439  }
440  pl = pl->next;
441  }
442  if (pl->next && (pl->next->payload == item)) {
443  struct _listheader *returnme = pl->next;
444  pl->next = pl->next->next;
445  poolReturn(returnme);
446  }
447  }
448 } /*}}}*/
449 
450 /* vim:set expandtab: */
getHeadOfList
void * getHeadOfList(List list)
Definition: list.c:264
listLen
size_t listLen(List list)
Definition: list.c:352
_list_iterator
Definition: list.c:27
peekAheadInList
void * peekAheadInList(List list)
Definition: list.c:343
_list_iterator::cur
struct _listheader * cur
Definition: list.c:28
addToListHead
void addToListHead(List *lst, void *addme)
Definition: list.c:234
lPoolUsed
static List lPoolUsed
Definition: list.c:38
lists_cleanup
void lists_cleanup(void)
Definition: list.c:59
peekListElement
void * peekListElement(List list, size_t n)
Definition: list.c:284
lPool
static List lPool
Definition: list.c:37
cleanup::data
void * data
Definition: list.c:34
lhCleanupPool
static struct cleanup * lhCleanupPool
Definition: list.c:46
free
void free(void *)
fill_l_pool
static void fill_l_pool(void)
Definition: list.c:113
getListIterator
ListIterator getListIterator(List list)
Definition: list.c:362
lhPool
static struct _listheader * lhPool
Definition: list.c:44
_list::head
struct _listheader * head
Definition: list.c:20
addToList
void addToList(List *lst, void *addme)
Definition: list.c:204
get_l
static List get_l(void)
Definition: list.c:185
cleanup
Definition: list.c:32
_list
Definition: list.c:19
fill_lh_pool
static void fill_lh_pool(void)
Definition: list.c:89
lists_init
void lists_init(void)
Definition: list.c:52
cleanup::next
struct cleanup * next
Definition: list.c:33
freeList
void freeList(List *lst)
Definition: list.c:135
_listheader::next
struct _listheader * next
Definition: list.c:14
lCleanupPool
static struct cleanup * lCleanupPool
Definition: list.c:40
poolReturn
static void poolReturn(struct _listheader *lh)
Definition: list.c:80
getListElement
void * getListElement(List list, size_t n)
Definition: list.c:305
_listheader::pool_next
struct _listheader * pool_next
Definition: list.c:16
malloc
void * malloc(size_t)
resetListIterator
void resetListIterator(ListIterator li)
Definition: list.c:398
freeListIterator
void freeListIterator(ListIterator li)
Definition: list.c:406
lPoolSize
static unsigned long long lPoolSize
Definition: list.c:39
_list::len
unsigned long len
Definition: list.c:22
_list_iterator::l
List l
Definition: list.c:29
_list::pool_next
struct _list * pool_next
Definition: list.c:23
_listheader
Definition: list.c:13
currentListElement
void * currentListElement(ListIterator li)
Definition: list.c:376
lhPoolSize
static unsigned long long lhPoolSize
Definition: list.c:45
get_lh
static struct _listheader * get_lh(void)
Definition: list.c:171
_list::pool_prev
struct _list * pool_prev
Definition: list.c:24
list.h
_listheader::payload
void * payload
Definition: list.c:15
removeFromList
void removeFromList(List list, void *item)
Definition: list.c:414
nextListElement
void * nextListElement(ListIterator li)
Definition: list.c:385
_list::tail
struct _listheader * tail
Definition: list.c:21