1
2 /*** EDGELIST.C ***/
3
4 #include "vdefs.h"
5
6 int ELhashsize ;
7 Site * bottomsite ;
8 Freelist hfl ;
9 Halfedge * ELleftend, * ELrightend, **ELhash ;
10
11 int ntry, totalsearch ;
12
13 void
ELinitialize(void)14 ELinitialize(void)
15 {
16 int i ;
17
18 freeinit(&hfl, sizeof(Halfedge)) ;
19 ELhashsize = 2 * sqrt_nsites ;
20 ELhash = (Halfedge **)myalloc( sizeof(*ELhash) * ELhashsize) ;
21 for (i = 0 ; i < ELhashsize ; i++)
22 {
23 ELhash[i] = (Halfedge *)NULL ;
24 }
25 ELleftend = HEcreate((Edge *)NULL, 0) ;
26 ELrightend = HEcreate((Edge *)NULL, 0) ;
27 ELleftend->ELleft = (Halfedge *)NULL ;
28 ELleftend->ELright = ELrightend ;
29 ELrightend->ELleft = ELleftend ;
30 ELrightend->ELright = (Halfedge *)NULL ;
31 ELhash[0] = ELleftend ;
32 ELhash[ELhashsize-1] = ELrightend ;
33 }
34
35 Halfedge *
HEcreate(Edge * e,int pm)36 HEcreate(Edge * e, int pm)
37 {
38 Halfedge * answer ;
39
40 answer = (Halfedge *)getfree(&hfl) ;
41 answer->ELedge = e ;
42 answer->ELpm = pm ;
43 answer->PQnext = (Halfedge *)NULL ;
44 answer->vertex = (Site *)NULL ;
45 answer->ELrefcnt = 0 ;
46 return (answer) ;
47 }
48
49 void
ELinsert(Halfedge * lb,Halfedge * new)50 ELinsert(Halfedge * lb, Halfedge * new)
51 {
52 new->ELleft = lb ;
53 new->ELright = lb->ELright ;
54 (lb->ELright)->ELleft = new ;
55 lb->ELright = new ;
56 }
57
58 /* Get entry from hash table, pruning any deleted nodes */
59
60 Halfedge *
ELgethash(int b)61 ELgethash(int b)
62 {
63 Halfedge * he ;
64
65 if ((b < 0) || (b >= ELhashsize))
66 {
67 return ((Halfedge *)NULL) ;
68 }
69 he = ELhash[b] ;
70 if ((he == (Halfedge *)NULL) || (he->ELedge != (Edge *)DELETED))
71 {
72 return (he) ;
73 }
74 /* Hash table points to deleted half edge. Patch as necessary. */
75 ELhash[b] = (Halfedge *)NULL ;
76 if ((--(he->ELrefcnt)) == 0)
77 {
78 makefree((Freenode *)he, (Freelist *)&hfl) ;
79 }
80 return ((Halfedge *)NULL) ;
81 }
82
83 Halfedge *
ELleftbnd(Point * p)84 ELleftbnd(Point * p)
85 {
86 int i, bucket ;
87 Halfedge * he ;
88
89 /* Use hash table to get close to desired halfedge */
90 bucket = (p->x - xmin) / deltax * ELhashsize ;
91 if (bucket < 0)
92 {
93 bucket = 0 ;
94 }
95 if (bucket >= ELhashsize)
96 {
97 bucket = ELhashsize - 1 ;
98 }
99 he = ELgethash(bucket) ;
100 if (he == (Halfedge *)NULL)
101 {
102 for (i = 1 ; 1 ; i++)
103 {
104 if ((he = ELgethash(bucket-i)) != (Halfedge *)NULL)
105 {
106 break ;
107 }
108 if ((he = ELgethash(bucket+i)) != (Halfedge *)NULL)
109 {
110 break ;
111 }
112 }
113 totalsearch += i ;
114 }
115 ntry++ ;
116 /* Now search linear list of halfedges for the corect one */
117 if (he == ELleftend || (he != ELrightend && right_of(he,p)))
118 {
119 do {
120 he = he->ELright ;
121 } while (he != ELrightend && right_of(he,p)) ;
122 he = he->ELleft ;
123 }
124 else
125 {
126 do {
127 he = he->ELleft ;
128 } while (he != ELleftend && !right_of(he,p)) ;
129 }
130 /*** Update hash table and reference counts ***/
131 if ((bucket > 0) && (bucket < ELhashsize-1))
132 {
133 if (ELhash[bucket] != (Halfedge *)NULL)
134 {
135 (ELhash[bucket]->ELrefcnt)-- ;
136 }
137 ELhash[bucket] = he ;
138 (ELhash[bucket]->ELrefcnt)++ ;
139 }
140 return (he) ;
141 }
142
143 /*** This delete routine can't reclaim node, since pointers from hash
144 : table may be present.
145 ***/
146
147 void
ELdelete(Halfedge * he)148 ELdelete(Halfedge * he)
149 {
150 (he->ELleft)->ELright = he->ELright ;
151 (he->ELright)->ELleft = he->ELleft ;
152 he->ELedge = (Edge *)DELETED ;
153 }
154
155 Halfedge *
ELright(Halfedge * he)156 ELright(Halfedge * he)
157 {
158 return (he->ELright) ;
159 }
160
161 Halfedge *
ELleft(Halfedge * he)162 ELleft(Halfedge * he)
163 {
164 return (he->ELleft) ;
165 }
166
167 Site *
leftreg(Halfedge * he)168 leftreg(Halfedge * he)
169 {
170 if (he->ELedge == (Edge *)NULL)
171 {
172 return(bottomsite) ;
173 }
174 return (he->ELpm == le ? he->ELedge->reg[le] :
175 he->ELedge->reg[re]) ;
176 }
177
178 Site *
rightreg(Halfedge * he)179 rightreg(Halfedge * he)
180 {
181 if (he->ELedge == (Edge *)NULL)
182 {
183 return(bottomsite) ;
184 }
185 return (he->ELpm == le ? he->ELedge->reg[re] :
186 he->ELedge->reg[le]) ;
187 }
188
189