source: trunk/Jgraph/list.c @ 419

Last change on this file since 419 was 418, checked in by Nicholas Riley, 12 years ago

Jgraph 8.3 from http://www.cs.utk.edu/~plank/plank/jgraph/jgraph.tar.gz

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