| 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 |
|
|---|
