source: trunk/Jgraph/list.c

Last change on this file was 420, checked in by Nicholas Riley, 13 years ago

Jgraph: my changes - ANSIfication, few minor bug fixes; works on OS X 10.5 now

File size: 2.3 KB
Line 
1/*
2 * $Source: /tmp_mnt/n/fs/grad1/jsp/src/jgraph/RCS/list.c,v $
3 * $Revision: 8.3 $
4 * $Date: 92/11/30 11:42:25 $
5 * $Author: jsp $
6 */
7
8#include <stdio.h>    /* Basic includes and definitions */
9#include <stdlib.h>
10#include "list.h"
11
12#define boolean int
13#define TRUE 1
14#define FALSE 0
15
16
17/*---------------------------------------------------------------------*
18 * PROCEDURES FOR MANIPULATING DOUBLY LINKED LISTS
19 * Each list contains a sentinal node, so that     
20 * the first item in list l is l->flink.  If l is 
21 * empty, then l->flink = l->blink = l.           
22 * The sentinal contains extra information so that these operations
23 * can work on lists of any size and type.
24 * Memory management is done explicitly to avoid the slowness of
25 * malloc and free.  The node size and the free list are contained
26 * in the sentinal node.
27 *---------------------------------------------------------------------*/
28
29typedef struct int_list {  /* Information held in the sentinal node */
30  struct int_list *flink;
31  struct int_list *blink;
32  int size;
33  List free_list;
34} *Int_list;
35
36void insert(void *item, void *list)     /* Inserts to the end of a list */
37{
38  List last_node;
39
40  last_node = ((List)list)->blink;
41
42  ((List)list)->blink = item;
43  last_node->flink = item;
44  ((List)item)->blink = last_node;
45  ((List)item)->flink = list;
46}
47
48void delete_item(void *item)            /* Deletes an arbitrary iterm */
49{
50  ((List)item)->flink->blink = ((List)item)->blink;
51  ((List)item)->blink->flink = ((List)item)->flink;
52}
53
54List make_list(size)    /* Creates a new list */
55int size;
56{
57  Int_list l;
58
59  l = (Int_list) malloc(sizeof(struct int_list));
60  l->flink = l;
61  l->blink = l;
62  l->size = size;
63  l->free_list = (List) malloc (sizeof(struct list));
64  l->free_list->flink = l->free_list;
65  return (List) l;
66}
67 
68List get_node(void *list)   /* Allocates a node to be inserted into the list */
69{
70  Int_list l;
71  List to_return;
72
73  l = (Int_list) list;
74  if (l->free_list->flink == l->free_list) {
75    return (List) malloc(l->size);
76  } else {
77    to_return = l->free_list;
78    l->free_list = to_return->flink;
79    return to_return;
80  }
81}
82
83void free_node(void *node, void *list)    /* Deallocates a node from the list */
84{
85  Int_list l;
86 
87  l = (Int_list) list;
88  ((List)node)->flink = l->free_list;
89  l->free_list = node;
90}
Note: See TracBrowser for help on using the repository browser.