Graphviz 13.0.0~dev.20241220.2304
Loading...
Searching...
No Matches
fPQ.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/* Priority Queue Code for shortest path in graph */
12
13#include "config.h"
14#include <assert.h>
15#include <util/alloc.h>
16
17#include <ortho/fPQ.h>
18
19static snode** pq;
20static int PQcnt;
21static snode guard;
22static int PQsize;
23
24void
25PQgen(int sz)
26{
27 if (!pq) {
28 pq = gv_calloc(sz + 1, sizeof(snode*));
29 pq[0] = &guard;
30 PQsize = sz;
31 }
32 PQcnt = 0;
33}
34
35void
36PQfree(void)
37{
38 free (pq);
39 pq = NULL;
40 PQcnt = 0;
41}
42
43void
44PQinit(void)
45{
46 PQcnt = 0;
47}
48
49void
50PQcheck (void)
51{
52 int i;
53
54 for (i = 1; i <= PQcnt; i++) {
55 if (N_IDX(pq[i]) != i) {
56 assert (0);
57 }
58 }
59}
60
61void
63{
64 snode* x = pq[k];
65 int v = x->n_val;
66 int next = k/2;
67 snode* n;
68
69 while (N_VAL(n = pq[next]) < v) {
70 pq[k] = n;
71 N_IDX(n) = k;
72 k = next;
73 next /= 2;
74 }
75 pq[k] = x;
76 N_IDX(x) = k;
77}
78
79int
81{
82 if (PQcnt == PQsize) {
83 agerrorf("Heap overflow\n");
84 return 1;
85 }
86 PQcnt++;
87 pq[PQcnt] = np;
89 PQcheck();
90 return 0;
91}
92
93void
95{
96 snode* x = pq[k];
97 int v = N_VAL(x);
98 int lim = PQcnt/2;
99 snode* n;
100 int j;
101
102 while (k <= lim) {
103 j = k+k;
104 n = pq[j];
105 if (j < PQcnt) {
106 if (N_VAL(n) < N_VAL(pq[j+1])) {
107 j++;
108 n = pq[j];
109 }
110 }
111 if (v >= N_VAL(n)) break;
112 pq[k] = n;
113 N_IDX(n) = k;
114 k = j;
115 }
116 pq[k] = x;
117 N_IDX(x) = k;
118}
119
120snode*
122{
123 snode* n;
124
125 if (PQcnt) {
126 n = pq[1];
127 pq[1] = pq[PQcnt];
128 PQcnt--;
129 if (PQcnt) PQdownheap (1);
130 PQcheck();
131 return n;
132 }
133 else return 0;
134}
135
136void
137PQupdate (snode* n, int d)
138{
139 N_VAL(n) = d;
140 PQupheap (n->n_idx);
141 PQcheck();
142}
143
144void
146{
147 int i;
148 snode* n;
149
150 fprintf (stderr, "Q: ");
151 for (i = 1; i <= PQcnt; i++) {
152 n = pq[i];
153 fprintf (stderr, "%d(%d:%d) ",
154 n->index, N_IDX(n), N_VAL(n));
155 }
156 fprintf (stderr, "\n");
157}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static snode guard
Definition fPQ.c:21
void PQinit(void)
Definition fPQ.c:44
void PQdownheap(int k)
Definition fPQ.c:94
static snode ** pq
Definition fPQ.c:19
void PQcheck(void)
Definition fPQ.c:50
void PQgen(int sz)
Definition fPQ.c:25
void PQfree(void)
Definition fPQ.c:36
snode * PQremove(void)
Definition fPQ.c:121
static int PQsize
Definition fPQ.c:22
int PQ_insert(snode *np)
Definition fPQ.c:80
void PQupheap(int k)
Definition fPQ.c:62
void PQprint(void)
Definition fPQ.c:145
void PQupdate(snode *n, int d)
Definition fPQ.c:137
static int PQcnt
Definition fPQ.c:20
void free(void *)
node NULL
Definition grammar.y:163
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define N_IDX(pq, n)
#define N_VAL(pq, n)
snode priority queue for shortPath in sgraph
Definition heap.c:19
a node of search graph sgraph, is created as a border segment between two adjusted cells of type cell...
Definition sgraph.h:26
int n_idx
Definition sgraph.h:27
int index
Definition sgraph.h:38
int n_val
Definition sgraph.h:27