Graphviz  2.41.20170921.2350
fPQ.h
Go to the documentation of this file.
1 /* $Id$Revision: */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include <memory.h>
15 #include <stdio.h>
16 
17 /* Priority queue:
18  * To work, the following have to be defined before this file is
19  * included:
20  * - PQTYPE : type of object stored in the queue
21  * - PQVTYPE : type of priority value
22  * - N_VAL(pq,n) : macro for (negative) priority value of object n in pq
23  * - N_IDX(pq,n) : macro for integer index > 0 of n in pq
24  * - guard, type PQTYPE, with N_VAL(guard) == 0
25  *
26  * Priorities are stored as negative numbers, with the item with the least
27  * negative priority at the head (just after the guard).
28  */
29 
30 #ifdef PQ_TYPES
31 typedef struct {
32  PQTYPE* pq;
33  int PQcnt;
34  int PQsize;
35 } PQ;
36 #endif
37 
38 #ifdef PQ_CODE
39 static void
40 PQgen(PQ* pq, int sz, PQTYPE guard)
41 {
42  pq->pq = N_NEW(sz+1,PQTYPE);
43  pq->pq[0] = guard;
44  pq->PQsize = sz;
45  pq->PQcnt = 0;
46 }
47 
48 static void
49 PQfree(PQ* pq, int freeAll)
50 {
51  free (pq->pq);
52  if (freeAll) free (pq);
53 }
54 
55 static void
56 PQinit(PQ* pq)
57 {
58  pq->PQcnt = 0;
59 }
60 
61 #ifdef PQCHECK
62 static int
63 PQcheck (PQ* pq)
64 {
65  int i;
66 
67  for (i = 1; i <= pq->PQcnt; i++) {
68  if (N_IDX(pq,pq->pq[i]) != i) {
69  return 1;
70  }
71  }
72  return 0;
73 }
74 #endif
75 
76 static void
77 PQupheap(PQ* ppq, int k)
78 {
79  PQTYPE* pq = ppq->pq;
80  PQTYPE x = pq[k];
81  PQVTYPE v = N_VAL(ppq,x);
82  int next = k/2;
83  PQTYPE n;
84 
85  while (N_VAL(ppq,n = pq[next]) < v) {
86  pq[k] = n;
87  N_IDX(ppq,n) = k;
88  k = next;
89  next /= 2;
90  }
91  pq[k] = x;
92  N_IDX(ppq,x) = k;
93 }
94 
95 static int
96 PQinsert(PQ* pq, PQTYPE np)
97 {
98  if (pq->PQcnt == pq->PQsize) {
99  agerr (AGERR, "Heap overflow\n");
100  return (1);
101  }
102  pq->PQcnt++;
103  pq->pq[pq->PQcnt] = np;
104  PQupheap (pq, pq->PQcnt);
105 #ifdef PQCHECK
106  PQcheck(pq);
107 #endif
108  return 0;
109 }
110 
111 static void
112 PQdownheap (PQ* ppq, int k)
113 {
114  PQTYPE* pq = ppq->pq;
115  PQTYPE x = pq[k];
116  PQVTYPE v = N_VAL(ppq,x);
117  int lim = ppq->PQcnt/2;
118  PQTYPE n;
119  int j;
120 
121  while (k <= lim) {
122  j = k+k;
123  n = pq[j];
124  if (j < ppq->PQcnt) {
125  if (N_VAL(ppq,n) < N_VAL(ppq,pq[j+1])) {
126  j++;
127  n = pq[j];
128  }
129  }
130  if (v >= N_VAL(ppq,n)) break;
131  pq[k] = n;
132  N_IDX(ppq,n) = k;
133  k = j;
134  }
135  pq[k] = x;
136  N_IDX(ppq,x) = k;
137 }
138 
139 static PQTYPE
140 PQremove (PQ* pq)
141 {
142  PQTYPE n;
143 
144  if (pq->PQcnt) {
145  n = pq->pq[1];
146  pq->pq[1] = pq->pq[pq->PQcnt];
147  pq->PQcnt--;
148  if (pq->PQcnt) PQdownheap (pq, 1);
149 #ifdef PQCHECK
150  PQcheck(pq);
151 #endif
152  return n;
153  }
154  else return pq->pq[0];
155 }
156 
157 static void
158 PQupdate (PQ* pq, PQTYPE n, PQVTYPE d)
159 {
160  N_VAL(pq,n) = d;
161  PQupheap (pq, N_IDX(pq,n));
162 #ifdef PQCHECK
163  PQcheck(pq);
164 #endif
165 }
166 
167 #if DEBUG > 1
168 
169 static void
170 PQprint (PQ* pq)
171 {
172  int i;
173  PQTYPE n;
174 
175  fprintf (stderr, "Q: ");
176  for (i = 1; i <= pq->PQcnt; i++) {
177  n = pq->pq[i];
178  fprintf (stderr, "(%d:%f) ", N_IDX(pq,n), N_VAL(pq,n));
179  }
180  fprintf (stderr, "\n");
181 }
182 #endif
183 #endif
184 
Definition: cgraph.h:388
#define N_NEW(n, t)
Definition: memory.h:36
#define PQTYPE
Definition: multispline.c:1261
#define PQVTYPE
Definition: multispline.c:1262
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
void PQinsert(Halfedge *he, Site *v, double offset)
Definition: heap.c:45
#define N_IDX(pq, n)
Definition: multispline.c:1275
#define N_VAL(pq, n)
Definition: multispline.c:1274