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