source: trunk/Jgraph/prio_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: 1.5 KB
Line 
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
13/* Prio_insert inserts nodes into their proper places in priority lists.  It first
14 * checks for inserting into the head or tail, and then proceeds sequentially.
15 * Thus, it is worst case linear, but for most cases constant time (right). */
16
17void prio_insert(void *n, void *l, Boolean desc)
18{
19  Prio_list p, node = (Prio_list)n, list = (Prio_list)l;
20
21  /* Check nil and head of list */
22  if (first(list) == nil(list) || 
23      (!desc && first(list)->prio >= node->prio) ||
24      (desc  && first(list)->prio <= node->prio) ) {
25    node->blink = list;
26    node->flink = list->flink;
27    list->flink->blink = node;
28    list->flink = node;
29    return;
30  }
31  /* Check tail of list */
32  if ((desc  && last(list)->prio >= node->prio) ||
33      (!desc && last(list)->prio <= node->prio) ) {
34    node->flink = list;
35    node->blink = list->blink;
36    list->blink->flink = node;
37    list->blink = node;
38    return;
39  }
40  /* Check the rest of the list sequentially */
41  for(p = next(first(list));  ; p = next(p)) {
42    if (p == nil(list)) fprintf(stderr, "inserting into tail did not work\n");
43    if ((!desc && p->prio >= node->prio) ||
44        (desc  && p->prio <= node->prio)) {
45      node->flink = p;
46      node->blink = p->blink;
47      p->blink->flink = node;
48      p->blink = node;
49      return;
50    }
51  }
52}
53     
54
55 
Note: See TracBrowser for help on using the repository browser.