1 /*
2 $Log: list.c,v $
3 Revision 1.5 2003/07/14 13:36:58 ivo
4 use vrna_alloc() instead of malloc
5
6 Revision 1.4 2000/10/10 08:53:52 ivo
7 include dmalloc.h header if DMALLOC defined
8
9 Revision 1.4 2000/10/10 08:04:34 ivo
10 include dmalloc header id DMALLOC defined
11
12 Revision 1.3 1998/03/30 14:24:51 ivo
13 use RNA package utils.h
14
15 Revision 1.2 1997/10/09 19:01:50 steve
16 *** empty log message ***
17
18 Revision 1.1 1997/08/04 21:05:32 walter
19 Initial revision
20
21 */
22 /*
23 (C) 1991 Kendall Bennett.
24 */
25
26 #ifdef HAVE_CONFIG_H
27 #include "config.h"
28 #endif
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include "ViennaRNA/utils/basic.h"
33 #include "ViennaRNA/datastructures/lists.h"
34
35 #define PUBLIC
36 PUBLIC void *
lst_newnode(int size)37 lst_newnode (int size)
38 /****************************************************************************
39 *
40 * Function: lst_newnode
41 * Parameters: size - Amount of memory to allocate for node
42 * Returns: Pointer to the allocated node's user space.
43 *
44 * Description: Allocates the memory required for a node, adding a small
45 * header at the start of the node. We return a reference to
46 * the user space of the node, as if it had been allocated via
47 * malloc().
48 *
49 ****************************************************************************/
50 {
51 LST_BUCKET *node;
52
53 node = (LST_BUCKET *) vrna_alloc(size + sizeof (LST_BUCKET));
54
55 return LST_USERSPACE (node); /* Return pointer to user space */
56 }
57
58 PUBLIC void
lst_freenode(void * node)59 lst_freenode (void *node)
60 /****************************************************************************
61 *
62 * Function: lst_freenode
63 * Parameters: node - Node to free.
64 *
65 * Description: Frees a node previously allocated with lst_newnode().
66 *
67 ****************************************************************************/
68 {
69 free (LST_HEADER (node));
70 }
71
72 PUBLIC LIST *
lst_init(void)73 lst_init (void)
74 /****************************************************************************
75 *
76 * Function: lst_init
77 * Returns: Pointer to a newly created list.
78 *
79 * Description: Initialises a list and returns a pointer to it.
80 *
81 ****************************************************************************/
82 {
83 LIST *l;
84
85 if ((l = (LIST *) vrna_alloc(sizeof (LIST))) != NULL)
86 {
87 l->count = 0;
88 l->head = &(l->hz[0]);
89 l->z = &(l->hz[1]);
90 l->head->next = l->z->next = l->z;
91 }
92
93 return l;
94 }
95
96 PUBLIC void
lst_kill(LIST * l,void (* freeNode)(void * node))97 lst_kill (LIST * l, void (*freeNode) (void *node))
98 /****************************************************************************
99 *
100 * Function: lst_kill
101 * Parameters: l - List to kill
102 * freeNode - Pointer to user routine to free a node
103 *
104 * Description: Kills the list l, by deleting all of the elements contained
105 * within the list one by one and then deleting the list
106 * itself. Note that we call the user supplied routine
107 * (*freeNode)() to free each list node. This allows the user
108 * program to perform any extra processing needed to kill each
109 * node (if each node contains pointers to other items on the
110 * heap for example). If no extra processing is required, just
111 * pass the address of lst_freenode(), ie:
112 *
113 * lst_kill(myList,lst_freenode);
114 *
115 ****************************************************************************/
116 {
117 LST_BUCKET *n, *p;
118
119 n = l->head->next;
120 while (n != l->z)
121 { /* Free all nodes in list */
122 p = n;
123 n = n->next;
124 (*freeNode) (LST_USERSPACE (p));
125 }
126 free (l); /* Free the list itself */
127 }
128
129 PUBLIC void
lst_insertafter(LIST * l,void * node,void * after)130 lst_insertafter (LIST * l, void *node, void *after)
131 /****************************************************************************
132 *
133 * Function: lst_insertafter
134 * Parameters: l - List to insert node into
135 * node - Pointer to user space of node to insert
136 * after - Pointer to user space of node to insert node after
137 *
138 * Description: Inserts a new node into the list after the node 'after'. To
139 * insert a new node at the beginning of the list, user the
140 * macro LST_HEAD in place of 'after'. ie:
141 *
142 * lst_insertafter(mylist,node,LST_HEAD(mylist));
143 *
144 ****************************************************************************/
145 {
146 LST_BUCKET *n = LST_HEADER (node), *a = LST_HEADER (after);
147
148 n->next = a->next;
149 a->next = n;
150 l->count++;
151 }
152
153 PUBLIC void *
lst_deletenext(LIST * l,void * node)154 lst_deletenext (LIST * l, void *node)
155 /****************************************************************************
156 *
157 * Function: lst_deletenext
158 * Parameters: l - List to delete node from.
159 * node - Node to delete the next node from
160 * Returns: Pointer to the deleted node's userspace.
161 *
162 * Description: Removes the node AFTER 'node' from the list l.
163 *
164 ****************************************************************************/
165 {
166 LST_BUCKET *n = LST_HEADER (node);
167
168 node = LST_USERSPACE (n->next);
169 n->next = n->next->next;
170 l->count--;
171 return node;
172 }
173
174 PUBLIC void *
lst_first(LIST * l)175 lst_first (LIST * l)
176 /****************************************************************************
177 *
178 * Function: lst_first
179 * Parameters: l - List to obtain first node from
180 * Returns: Pointer to first node in list, NULL if list is empty.
181 *
182 * Description: Returns a pointer to the user space of the first node in
183 * the list. If the list is empty, we return NULL.
184 *
185 ****************************************************************************/
186 {
187 LST_BUCKET *n;
188
189 n = l->head->next;
190 return (n == l->z ? NULL : LST_USERSPACE (n));
191 }
192
193 PUBLIC void *
lst_next(void * prev)194 lst_next (void *prev)
195 /****************************************************************************
196 *
197 * Function: lst_next
198 * Parameters: prev - Previous node in list to obtain next node from
199 * Returns: Pointer to the next node in the list, NULL at end of list.
200 *
201 * Description: Returns a pointer to the user space of the next node in the
202 * list given a pointer to the user space of the previous node.
203 * If we have reached the end of the list, we return NULL. The
204 * end of the list is detected when the next pointer of a node
205 * points back to itself, as does the dummy last node's next
206 * pointer. This enables us to detect the end of the list
207 * without needed access to the list data structure itself.
208 *
209 * NOTE: We do no checking to ensure that 'prev' is NOT a
210 * NULL pointer.
211 *
212 ****************************************************************************/
213 {
214 LST_BUCKET *n = LST_HEADER (prev);
215
216 n = n->next;
217 return (n == n->next ? NULL : LST_USERSPACE (n));
218 }
219
220 /* Static globals required by merge() */
221
222 static LST_BUCKET *z;
223 static int (*cmp) (void *, void *);
224
225 static LST_BUCKET *
merge(LST_BUCKET * a,LST_BUCKET * b,LST_BUCKET ** end)226 merge (LST_BUCKET * a, LST_BUCKET * b, LST_BUCKET ** end)
227 /****************************************************************************
228 *
229 * Function: merge
230 * Parameters: a,b - Sublist's to merge
231 * Returns: Pointer to the merged sublists.
232 *
233 * Description: Merges two sorted lists of nodes together into a single
234 * sorted list.
235 *
236 ****************************************************************************/
237 {
238 LST_BUCKET *c;
239
240 /* Go through the lists, merging them together in sorted order */
241
242 c = z;
243 while (a != z && b != z)
244 {
245 if ((*cmp) (LST_USERSPACE (a), LST_USERSPACE (b)) <= 0)
246 {
247 c->next = a;
248 c = a;
249 a = a->next;
250 }
251 else
252 {
253 c->next = b;
254 c = b;
255 b = b->next;
256 }
257 };
258
259 /* If one of the lists is not exhausted, then re-attach it to the end
260 * of the newly merged list
261 */
262
263 if (a != z)
264 c->next = a;
265 if (b != z)
266 c->next = b;
267
268 /* Set *end to point to the end of the newly merged list */
269
270 while (c->next != z)
271 c = c->next;
272 *end = c;
273
274 /* Determine the start of the merged lists, and reset z to point to
275 * itself
276 */
277
278 c = z->next;
279 z->next = z;
280 return c;
281 }
282
283 PUBLIC void
lst_mergesort(LIST * l,int (* cmp_func)(void *,void *))284 lst_mergesort (LIST * l, int (*cmp_func) (void *, void *))
285 /****************************************************************************
286 *
287 * Function: lst_mergesort
288 * Parameters: l - List to merge sort
289 * cmp_func - Function to compare two user spaces
290 *
291 * Description: Mergesort's all the nodes in the list. 'cmp' must point to
292 * a comparison function that can compare the user spaces of
293 * two different nodes. 'cmp' should work the same as
294 * strcmp(), in terms of the values it returns.
295 *
296 ****************************************************************************/
297 {
298 int i, N;
299 LST_BUCKET *a, *b; /* Pointers to sublists to merge */
300 LST_BUCKET *c; /* Pointer to end of sorted sublists */
301 LST_BUCKET *head; /* Pointer to dummy head node for list */
302 LST_BUCKET *todo; /* Pointer to sublists yet to be sorted */
303 LST_BUCKET *t; /* Temporary */
304
305 /* Set up globals required by merge() and pointer to head */
306
307 z = l->z;
308 cmp = cmp_func;
309 head = l->head;
310
311 for (N = 1, a = z; a != head->next; N = N + N)
312 {
313 todo = head->next;
314 c = head;
315 while (todo != z)
316 {
317
318 /* Build first sublist to be merged, and splice from main list
319 */
320
321 a = t = todo;
322 for (i = 1; i < N; i++)
323 t = t->next;
324 b = t->next;
325 t->next = z;
326 t = b;
327
328 /* Build second sublist to be merged and splice from main list
329 */
330
331 for (i = 1; i < N; i++)
332 t = t->next;
333 todo = t->next;
334 t->next = z;
335
336 /* Merge the two sublists created, and set 'c' to point to the
337 * end of the newly merged sublists.
338 */
339
340 c->next = merge (a, b, &t);
341 c = t;
342 }
343 }
344 }
345
346 #ifdef LIST_TEST
347
348 /*---------------------------------------------------------------*/
349 /*---------------------------------------------------------------*/
350
351 /* Simple program to test the list routines */
352
353 typedef struct
354 {
355 char name[40];
356 int age;
357 }
358 REC;
359
360 /*---------------------------------------------------------------*/
361
362 int
my_cmp(REC * r1,REC * r2)363 my_cmp (REC * r1, REC * r2)
364 {
365 return strcmp (r1->name, r2->name);
366 }
367
368 /*---------------------------------------------------------------*/
369
370 void
main(void)371 main (void)
372 {
373 LIST *list;
374 int done = 0;
375 REC *rec;
376 char line[80];
377
378 list = lst_init ();
379
380 printf ("Type a list of names and ages. Empty line quits\n\n");
381
382 while (!done)
383 {
384 rec = lst_newnode (sizeof (REC));
385 gets (line);
386 if ((done = (line[0] == '\0')) != 1)
387 {
388 strcpy (rec->name, line);
389 gets (line);
390 rec->age = atoi (line);
391 lst_insertafter (list, rec, LST_HEAD (list));
392 }
393 };
394
395 printf ("\nThe list you typed in was:\n\n");
396
397 for (rec = lst_first (list); rec; rec = lst_next (rec))
398 printf ("Name: %s, Age: %d\n", rec->name, rec->age);
399
400 printf ("\nSorting the list...\n\n");
401
402 lst_mergesort (list, my_cmp);
403
404 for (rec = lst_first (list); rec; rec = lst_next (rec))
405 printf ("Name: %s, Age: %d\n", rec->name, rec->age);
406
407 lst_kill (list, lst_freenode);
408 }
409
410 /*---------------------------------------------------------------*/
411
412 #endif
413