source: trunk/Jgraph/list.c @ 420

Last change on this file since 420 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
RevLine 
[418]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 */
[420]9#include <stdlib.h>
[418]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
[420]36void insert(void *item, void *list)     /* Inserts to the end of a list */
[418]37{
38  List last_node;
39
[420]40  last_node = ((List)list)->blink;
[418]41
[420]42  ((List)list)->blink = item;
[418]43  last_node->flink = item;
[420]44  ((List)item)->blink = last_node;
45  ((List)item)->flink = list;
[418]46}
47
[420]48void delete_item(void *item)            /* Deletes an arbitrary iterm */
[418]49{
[420]50  ((List)item)->flink->blink = ((List)item)->blink;
51  ((List)item)->blink->flink = ((List)item)->flink;
[418]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 
[420]68List get_node(void *list)   /* Allocates a node to be inserted into the list */
[418]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
[420]83void free_node(void *node, void *list)    /* Deallocates a node from the list */
[418]84{
85  Int_list l;
86 
87  l = (Int_list) list;
[420]88  ((List)node)->flink = l->free_list;
[418]89  l->free_list = node;
90}
Note: See TracBrowser for help on using the repository browser.