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