Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
heap.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#include <common/render.h>
12#include <stdbool.h>
13
14#include <neatogen/hedges.h>
15#include <neatogen/heap.h>
16#include <util/alloc.h>
17
18struct pq {
21 int count;
22 int min;
23};
24
31static int clamp(int lower, double v, int upper) {
32 assert(upper >= lower);
33 if (v < lower) {
34 return lower;
35 }
36 if (v > upper) {
37 return upper;
38 }
39 return (int)v;
40}
41
42static int PQbucket(pq_t *pq, Halfedge *he) {
43 const double deltay = ymax - ymin;
44 const int bucket =
45 clamp(0, (he->ystar - ymin) / deltay * pq->hashsize, pq->hashsize - 1);
46 if (bucket < pq->min)
47 pq->min = bucket;
48 return bucket;
49}
50
52static bool gt(double a_y, double a_x, double b_y, double b_x) {
53 if (a_y > b_y) {
54 return true;
55 }
56 if (a_y < b_y) {
57 return false;
58 }
59 return a_x > b_x;
60}
61
62void PQinsert(pq_t *pq, Halfedge *he, Site *v, double offset) {
63 Halfedge *last, *next;
64
65 he->vertex = v;
66 he->ystar = v->coord.y + offset;
67 last = &pq->hash[PQbucket(pq, he)];
68 while ((next = last->PQnext) != NULL &&
69 gt(he->ystar, v->coord.x, next->ystar, next->vertex->coord.x)) {
70 last = next;
71 }
72 he->PQnext = last->PQnext;
73 last->PQnext = he;
74 ++pq->count;
75}
76
77void PQdelete(pq_t *pq, Halfedge *he) {
79
80 if (he->vertex != NULL) {
81 last = &pq->hash[PQbucket(pq, he)];
82 while (last->PQnext != he)
83 last = last->PQnext;
84 last->PQnext = he->PQnext;
85 --pq->count;
86 he->vertex = NULL;
87 }
88}
89
90bool PQempty(const pq_t *pq) {
91 return pq->count == 0;
92}
93
95 Point answer;
96
97 while (pq->hash[pq->min].PQnext == NULL) {
98 ++pq->min;
99 }
100 answer.x = pq->hash[pq->min].PQnext->vertex->coord.x;
101 answer.y = pq->hash[pq->min].PQnext->ystar;
102 return answer;
103}
104
106 Halfedge *curr = pq->hash[pq->min].PQnext;
107 pq->hash[pq->min].PQnext = curr->PQnext;
108 --pq->count;
109 return curr;
110}
111
113 if (pq != NULL) {
114 free(pq->hash);
115 }
116 free(pq);
117}
118
120 pq_t *pq = gv_alloc(sizeof(pq_t));
121 pq->hashsize = 4 * sqrt_nsites;
122 pq->hash = gv_calloc(pq->hashsize, sizeof(Halfedge));
123 return pq;
124}
static agxbuf last
last message
Definition agerror.c:29
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
double ymin
Definition geometry.c:15
int sqrt_nsites
Definition geometry.c:19
double ymax
Definition geometry.c:15
void free(void *)
node NULL
Definition grammar.y:181
Point PQ_min(pq_t *pq)
Definition heap.c:94
static bool gt(double a_y, double a_x, double b_y, double b_x)
a > b?
Definition heap.c:52
void PQcleanup(pq_t *pq)
Definition heap.c:112
static int PQbucket(pq_t *pq, Halfedge *he)
Definition heap.c:42
bool PQempty(const pq_t *pq)
Definition heap.c:90
void PQdelete(pq_t *pq, Halfedge *he)
Definition heap.c:77
static int clamp(int lower, double v, int upper)
Definition heap.c:31
pq_t * PQinitialize(void)
Definition heap.c:119
Halfedge * PQextractmin(pq_t *pq)
Definition heap.c:105
void PQinsert(pq_t *pq, Halfedge *he, Site *v, double offset)
Definition heap.c:62
double ystar
Definition hedges.h:28
struct Halfedge * PQnext
Definition hedges.h:29
Site * vertex
Definition hedges.h:27
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition site.h:23
Point coord
Definition site.h:24
Definition heap.c:18
int hashsize
total allocated backing storage elements
Definition heap.c:20
int count
occupancy
Definition heap.c:21
Halfedge * hash
backing storage
Definition heap.c:19
int min
index of minimum element
Definition heap.c:22