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 | |
86 | Point PQ_min(void) |
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 | |
98 | Halfedge *(void) |
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 | } |
150 | |