1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
/*
* $Source: /tmp_mnt/n/fs/grad1/jsp/src/jgraph/RCS/prio_list.c,v $
* $Revision: 8.3 $
* $Date: 92/11/30 11:42:32 $
* $Author: jsp $
*/
#include "list.h"
#include "prio_list.h"
#include <stdio.h>
typedef int Boolean;
/* A prioirity list is any list with the first three fields being flink,
* blink and prio. Use the routines of list.c to do everything except
* insertion */
typedef struct prio_list {
struct prio_list *flink;
struct prio_list *blink;
int prio;
} *Prio_list;
/* Prio_insert inserts nodes into their proper places in priority lists. It first
* checks for inserting into the head or tail, and then proceeds sequentially.
* Thus, it is worst case linear, but for most cases constant time (right). */
prio_insert(node, list, desc)
Prio_list node;
Prio_list list;
Boolean desc;
{
Prio_list p;
/* Check nil and head of list */
if (first(list) == nil(list) ||
(!desc && first(list)->prio >= node->prio) ||
(desc && first(list)->prio <= node->prio) ) {
node->blink = list;
node->flink = list->flink;
list->flink->blink = node;
list->flink = node;
return;
}
/* Check tail of list */
if ((desc && last(list)->prio >= node->prio) ||
(!desc && last(list)->prio <= node->prio) ) {
node->flink = list;
node->blink = list->blink;
list->blink->flink = node;
list->blink = node;
return;
}
/* Check the rest of the list sequentially */
for(p = next(first(list)); ; p = next(p)) {
if (p == nil(list)) fprintf(stderr, "inserting into tail did not work\n");
if ((!desc && p->prio >= node->prio) ||
(desc && p->prio <= node->prio)) {
node->flink = p;
node->blink = p->blink;
p->blink->flink = node;
p->blink = node;
return;
}
}
}
|
