Graphviz  2.41.20170921.2350
heap.c
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 
15 #include "render.h"
16 #include <stdio.h>
17 
18 #include "mem.h"
19 #include "hedges.h"
20 #include "heap.h"
21 
22 
23 static Halfedge *PQhash;
24 static int PQhashsize;
25 static int PQcount;
26 static int PQmin;
27 
28 static int PQbucket(Halfedge * he)
29 {
30  int bucket;
31  double b;
32 
33  b = (he->ystar - ymin) / deltay * PQhashsize;
34  if (b < 0)
35  bucket = 0;
36  else if (b >= PQhashsize)
37  bucket = PQhashsize - 1;
38  else
39  bucket = b;
40  if (bucket < PQmin)
41  PQmin = bucket;
42  return (bucket);
43 }
44 
45 void PQinsert(Halfedge * he, Site * v, double offset)
46 {
47  Halfedge *last, *next;
48 
49  he->vertex = v;
50  ref(v);
51  he->ystar = v->coord.y + offset;
52  last = &PQhash[PQbucket(he)];
53  while ((next = last->PQnext) != (struct Halfedge *) NULL &&
54  (he->ystar > next->ystar ||
55  (he->ystar == next->ystar
56  && v->coord.x > next->vertex->coord.x))) {
57  last = next;
58  }
59  he->PQnext = last->PQnext;
60  last->PQnext = he;
61  PQcount += 1;
62 }
63 
64 void PQdelete(Halfedge * he)
65 {
66  Halfedge *last;
67 
68  if (he->vertex != (Site *) NULL) {
69  last = &PQhash[PQbucket(he)];
70  while (last->PQnext != he)
71  last = last->PQnext;
72  last->PQnext = he->PQnext;
73  PQcount -= 1;
74  deref(he->vertex);
75  he->vertex = (Site *) NULL;
76  }
77 }
78 
79 
80 int PQempty(void)
81 {
82  return (PQcount == 0);
83 }
84 
85 
87 {
88  Point answer;
89 
90  while (PQhash[PQmin].PQnext == (struct Halfedge *) NULL) {
91  PQmin += 1;
92  }
93  answer.x = PQhash[PQmin].PQnext->vertex->coord.x;
94  answer.y = PQhash[PQmin].PQnext->ystar;
95  return (answer);
96 }
97 
99 {
100  Halfedge *curr;
101 
102  curr = PQhash[PQmin].PQnext;
103  PQhash[PQmin].PQnext = curr->PQnext;
104  PQcount -= 1;
105  return (curr);
106 }
107 
108 void PQcleanup(void)
109 {
110  free(PQhash);
111  PQhash = NULL;
112 }
113 
114 void PQinitialize(void)
115 {
116  int i;
117 
118  PQcount = 0;
119  PQmin = 0;
120  PQhashsize = 4 * sqrt_nsites;
121  if (PQhash == NULL)
122  PQhash = N_GNEW(PQhashsize, Halfedge);
123  for (i = 0; i < PQhashsize; i += 1)
124  PQhash[i].PQnext = (Halfedge *) NULL;
125 }
126 
127 static void PQdumphe(Halfedge * p)
128 {
129  printf(" [%p] %p %p %d %d %d %d %f\n",
130  p, p->ELleft, p->ELright, p->ELedge->edgenbr,
131  p->ELrefcnt, p->ELpm, (p->vertex ? p->vertex->sitenbr : -1),
132  p->ystar);
133 }
134 
135 void PQdump(void)
136 {
137  int i;
138  Halfedge *p;
139 
140  for (i = 0; i < PQhashsize; i += 1) {
141  printf("[%d]\n", i);
142  p = PQhash[i].PQnext;
143  while (p != NULL) {
144  PQdumphe(p);
145  p = p->PQnext;
146  }
147  }
148 
149 }
struct Halfedge * PQnext
Definition: hedges.h:33
Edge * ELedge
Definition: hedges.h:28
int PQempty(void)
Definition: heap.c:80
int edgenbr
Definition: edges.h:29
double y
Definition: geometry.h:27
void PQdelete(Halfedge *he)
Definition: heap.c:64
char ELpm
Definition: hedges.h:30
Definition: site.h:26
void PQcleanup(void)
Definition: heap.c:108
struct Halfedge * ELleft
Definition: hedges.h:27
void PQinitialize(void)
Definition: heap.c:114
double x
Definition: geometry.h:27
double ymin
Definition: geometry.c:20
void PQinsert(Halfedge *he, Site *v, double offset)
Definition: heap.c:45
void PQdump(void)
Definition: heap.c:135
double deltay
Definition: geometry.c:21
int sqrt_nsites
Definition: geometry.c:25
int ELrefcnt
Definition: hedges.h:29
Point PQ_min(void)
Definition: heap.c:86
Halfedge * PQextractmin(void)
Definition: heap.c:98
#define NULL
Definition: logic.h:39
Site * vertex
Definition: hedges.h:31
void deref(Site *v)
Definition: site.c:63
void ref(Site *v)
Definition: site.c:70
Definition: geometry.h:26
double ystar
Definition: hedges.h:32
struct Halfedge * ELright
Definition: hedges.h:27
Point coord
Definition: site.h:27
int sitenbr
Definition: site.h:28
#define N_GNEW(n, t)
Definition: agxbuf.c:20