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
31typedef struct {
32 PQTYPE* pq;
33 int PQcnt;
34 int PQsize;
35} PQ;
36#endif
37
38#ifdef PQ_CODE
39static void
40PQgen(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
48static void
49PQfree(PQ* pq, int freeAll)
50{
51 free (pq->pq);
52 if (freeAll) free (pq);
53}
54
55static void
56PQinit(PQ* pq)
57{
58 pq->PQcnt = 0;
59}
60
61#ifdef PQCHECK
62static int
63PQcheck (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
76static void
77PQupheap(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
95static int
96PQinsert(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
111static void
112PQdownheap (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
139static PQTYPE
140PQremove (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
157static void
158PQupdate (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
169static void
170PQprint (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
185