1 /*
2 * DBlabel2.c --
3 *
4 * Label searching primitives.
5 *
6 * *********************************************************************
7 * * Copyright (C) 1985, 1990 Regents of the University of California. *
8 * * Permission to use, copy, modify, and distribute this *
9 * * software and its documentation for any purpose and without *
10 * * fee is hereby granted, provided that the above copyright *
11 * * notice appear in all copies. The University of California *
12 * * makes no representations about the suitability of this *
13 * * software for any purpose. It is provided "as is" without *
14 * * express or implied warranty. Export of this software outside *
15 * * of the United States of America may require an export license. *
16 * *********************************************************************
17 */
18
19 #ifndef lint
20 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/database/DBlabel2.c,v 1.3 2010/09/12 20:32:31 tim Exp $";
21 #endif /* not lint */
22
23 #include <stdio.h>
24 #include <string.h>
25
26 #include "utils/magic.h"
27 #include "utils/geometry.h"
28 #include "tiles/tile.h"
29 #include "utils/hash.h"
30 #include "database/database.h"
31 #include "database/databaseInt.h"
32 #include "utils/malloc.h"
33
34 /*
35 * The following structure is used to pass data between DBNearestLabel
36 * and its search function.
37 */
38 struct nldata
39 {
40 int nld_distance; /* Square of distance to nearest
41 * label seen so far.
42 */
43 Point *nld_point; /* Reference: find nearest label to this */
44 Rect *nld_labelArea; /* Fill in with area of nearest label */
45 char *nld_name; /* Fill in with name of nearest label */
46 bool nld_gotLabel; /* TRUE means some label was found */
47 };
48
49 /*
50 * The following structure is used to pass the arguments of
51 * DBSearchLabel down to the filter function.
52 */
53
54 #define MAXLABPATHSIZE 256
55
56 typedef struct {
57 char *labSrPattern; /* Pattern for matching. */
58 int (*labSrFunc)(); /* Function to apply to each label found */
59 ClientData labSrArg; /* Client data of caller */
60 } labSrStruct;
61
62 /* Forward declarations */
63
64 extern void DBTreeFindUse();
65
66 bool dbParseArray();
67
68 /*
69 * ----------------------------------------------------------------------------
70 *
71 * DBSearchLabel --
72 *
73 * Search for all occurrences of a point label matching the pattern in the
74 * region rect in the indicated cell and all of its children. On each label
75 * matching the pattern found in the area, the supplied procedure is invoked.
76 *
77 * The supplied procedure should be of the form
78 * int
79 * func(scx, label, tpath, cdarg)
80 * SearchContext *scx;
81 * Label *label;
82 * TerminalPath *tpath;
83 * ClientData cdarg;
84 * {
85 * }
86 *
87 * In the above, scx is a search context specifying the cell use whose
88 * def was found to contain the label, and label is a pointer to the
89 * Label structure itself. The transform specified in scx is from
90 * coordinates of the def of the cell containing the label to "root"
91 * coordinates. Func should normally return 0. If it returns 1 then
92 * the search is aborted.
93 *
94 * Results:
95 * If the search terminates normally, 0 is returned. 1 is
96 * returned if the search was aborted.
97 *
98 * Side effects:
99 * Applies the supplied procedure to each tile containing a label
100 * matching the pattern.
101 *
102 * WARNING: because of the way regex(3) works, it is possible to be
103 * searching for at most one pattern at a time.
104 *
105 * ----------------------------------------------------------------------------
106 */
107
108 int
DBSearchLabel(scx,mask,xMask,pattern,func,cdarg)109 DBSearchLabel(scx, mask, xMask, pattern, func, cdarg)
110 SearchContext *scx; /* Search context: specifies CellUse,
111 * transform to "root" coordinates, and
112 * an area to search.
113 */
114 TileTypeBitMask *mask; /* Only search for labels on these layers */
115 int xMask; /* Expansion state mask for searching. Cell
116 * uses are only considered to be expanded
117 * when their expand masks have all the bits
118 * of xMask set.
119 */
120 char *pattern; /* Pattern for which to search */
121 int (*func)(); /* Function to apply to each match */
122 ClientData cdarg; /* Argument to pass to function */
123 {
124 TerminalPath tpath;
125 int dbSrLabelFunc();
126 labSrStruct labsr;
127 char labSrStr[MAXLABPATHSIZE]; /* String buffer in which the full pathname
128 * of each label is assembled for handing
129 * to the filter function.
130 */
131
132 labsr.labSrPattern = pattern;
133 labsr.labSrFunc = func;
134 labsr.labSrArg = cdarg;
135 tpath.tp_first = tpath.tp_next = labSrStr;
136 tpath.tp_last = &(labSrStr[sizeof(labSrStr) - 2]);
137
138 if (DBTreeSrLabels(scx, mask, xMask, &tpath, TF_LABEL_ATTACH,
139 dbSrLabelFunc, (ClientData) &labsr))
140 return 1;
141 else return 0;
142 }
143
144 /*
145 * ----------------------------------------------------------------------------
146 *
147 * dbSrLabelFunc --
148 *
149 * Filter procedure applied to all labels by DBTreeSrLabels(). For
150 * each label that matches the pattern set by DBSearchLabel(), the
151 * filter function (*cdarg->lsa_func)() is applied.
152 *
153 * Results:
154 * Always return 0 to keep the search going.
155 *
156 * Side effects:
157 * Applies the supplied procedure to each label matching the pattern.
158 *
159 * ----------------------------------------------------------------------------
160 */
161
162 int
dbSrLabelFunc(scx,label,tpath,labsr)163 dbSrLabelFunc(scx, label, tpath, labsr)
164 SearchContext *scx; /* Contains pointer to use in which label
165 * occurred, and transform back to root
166 * coordinates.
167 */
168 Label *label; /* Label itself */
169 TerminalPath *tpath; /* Full pathname of the terminal */
170 labSrStruct *labsr; /* Information passed to this routine */
171 {
172 if (Match(labsr->labSrPattern, label->lab_text))
173 if ((*labsr->labSrFunc)(scx, label, tpath, labsr->labSrArg))
174 return 1;
175 return 0;
176 }
177
178 /*
179 * ----------------------------------------------------------------------------
180 *
181 * DBSrLabelLoc --
182 *
183 * This procedure finds the locations of all labels with a given
184 * hierarchical name. For each label found, a client-supplied
185 * search function is called. The search function has the form:
186 *
187 * int
188 * func(rect, name, label, cdarg)
189 * Rect *rect;
190 * char *name;
191 * Label *label;
192 * ClientData cdarg;
193 *
194 * Rect is the location of the label, in the coordinates of rootUse->cu_def,
195 * name is the label's hierarchical name (just the parameter passed to us),
196 * label is a pointer to the label, and cdarg is the client data passed in
197 * to us by the client. Note that there can be more than one label with the
198 * same name. Func should normally return 0. If it returns 1, then the
199 * search is aborted.
200 *
201 * Results:
202 * The return value is 0, unless func returned a non-zero value,
203 * in which case the return value is 1.
204 *
205 * Side effects:
206 * Whatever the search function does.
207 *
208 * ----------------------------------------------------------------------------
209 */
210
211 int
DBSrLabelLoc(rootUse,name,func,cdarg)212 DBSrLabelLoc(rootUse, name, func, cdarg)
213 CellUse *rootUse; /* Cell in which to search. */
214 char *name; /* A hierarchical label name consisting of zero or more
215 * use-ids followed by a label name (fields separated
216 * with slashes).
217 */
218 int (*func)(); /* Applied to each instance of the label name */
219 ClientData cdarg; /* Data to pass through to (*func)() */
220 {
221 CellDef *def;
222 SearchContext scx;
223 char *cp;
224 Label *lab;
225 char csave;
226 Rect r;
227
228 if (cp = strrchr(name, '/'))
229 {
230 csave = *cp;
231 *cp = '\0';
232 DBTreeFindUse(name, rootUse, &scx);
233 *cp = csave;
234 if (scx.scx_use == NULL)
235 return 0;
236 cp++;
237 }
238 else
239 {
240 scx.scx_use = rootUse;
241 scx.scx_trans = GeoIdentityTransform;
242 cp = name;
243 }
244
245 def = scx.scx_use->cu_def;
246 for (lab = def->cd_labels; lab; lab = lab->lab_next)
247 if (lab->lab_text[0] == *cp && strcmp(lab->lab_text, cp) == 0)
248 {
249 GeoTransRect(&scx.scx_trans, &lab->lab_rect, &r);
250 if ((*func)(&r, name, lab, cdarg))
251 return 1;
252 }
253
254 return 0;
255 }
256
257 /*
258 * ----------------------------------------------------------------------------
259 *
260 * DBTreeFindUse --
261 *
262 * This procedure finds the cell use with the given hierarchical name.
263 *
264 * Results:
265 * None.
266 *
267 * Side effects:
268 * Sets scx->scx_use to the cell use found, with scx->scx_trans
269 * and scx->scx_x, scx->scx_y also valid. If the cell was not
270 * found, leaves scx->scx_use set to NULL.
271 *
272 * ----------------------------------------------------------------------------
273 */
274
275 void
DBTreeFindUse(name,use,scx)276 DBTreeFindUse(name, use, scx)
277 char *name;
278 CellUse *use;
279 SearchContext *scx;
280 {
281 char *cp;
282 HashEntry *he;
283 CellDef *def;
284 char csave;
285
286 def = use->cu_def;
287 scx->scx_use = (CellUse *) NULL;
288 scx->scx_trans = GeoIdentityTransform;
289 scx->scx_x = scx->scx_y = 0;
290 while (*name)
291 {
292 /*
293 * Make sure that the cell whose children are being searched
294 * is read in from disk.
295 */
296 if ((def->cd_flags & CDAVAILABLE) == 0)
297 {
298 bool dereference = (def->cd_flags & CDDEREFERENCE) ? TRUE : FALSE;
299 (void) DBCellRead(def, (char *) NULL, TRUE, dereference, NULL);
300 }
301
302 cp = name;
303 he = HashLookOnly(&def->cd_idHash, name);
304 if (he == NULL || HashGetValue(he) == NULL)
305 {
306 /*
307 * Pull off the next component of path up to but not including
308 * any array subscripts.
309 * NOTE: This should check the array bounds and only remove
310 * array components that are expected, not array components
311 * embedded in the name.
312 */
313 for (; *cp && *cp != '[' && *cp != '/'; cp++)
314 /* Nothing */;
315 csave = *cp;
316 *cp = '\0';
317 he = HashLookOnly(&def->cd_idHash, name);
318 *cp = csave;
319 if (he == NULL || HashGetValue(he) == NULL)
320 return;
321 }
322 use = (CellUse *) HashGetValue(he);
323 def = use->cu_def;
324
325 /*
326 * Pull off array subscripts and build next stage in transform.
327 * Return NULL if the number of subscripts specified doesn't
328 * match the number that are implied by the array, if use is
329 * an array.
330 */
331 if (!dbParseArray(cp, use, scx))
332 {
333 /* Allow non-indexed match of array */
334 if (strcmp(name, use->cu_id)) return;
335 /* Check for both 1- and 2-dimensional arrays */
336 if (!dbParseArray("[0][0]", use, scx))
337 if (!dbParseArray("[0]", use, scx))
338 return;
339 break;
340 }
341 while (*cp && *cp++ != '/')
342 /* Nothing */;
343 name = cp;
344 }
345
346 /* Ensure that the leaf cell is read in */
347 def = use->cu_def;
348 if ((def->cd_flags & CDAVAILABLE) == 0)
349 {
350 bool dereference = (def->cd_flags & CDDEREFERENCE) ? TRUE : FALSE;
351 (void) DBCellRead(def, (char *) NULL, TRUE, dereference, NULL);
352 }
353
354 scx->scx_use = use;
355 }
356
357 /*
358 * ----------------------------------------------------------------------------
359 *
360 * dbParseArray --
361 *
362 * Pull off the array subscripts starting at 'cp' (there may be none),
363 * checking to ensure that there are the correct number for 'use' and that
364 * they are in range. Store these in scx->scx_x and scx->scx_y, and use them
365 * to update scx->scx_trans to be use->cu_trans (as adjusted for the indicated
366 * array element) followed by the old value of scx->scx_trans.
367 *
368 * Results:
369 * Returns TRUE on success, FALSE on error.
370 *
371 * Side effects:
372 * See above.
373 *
374 * ----------------------------------------------------------------------------
375 */
376
377 bool
dbParseArray(cp,use,scx)378 dbParseArray(cp, use, scx)
379 char *cp;
380 CellUse *use;
381 SearchContext *scx;
382 {
383 int xdelta, ydelta, i1, i2, indexCount;
384 Transform trans, trans2;
385
386 /*
387 * The transform stuff is a little tricky because if there
388 * was only one index given we don't know whether it's the
389 * x- or y-index. Make sure the number of indices specified
390 * matches the number of dimensions in an array, and that
391 * the indices are in range.
392 */
393 indexCount = 0;
394 if (*cp == '[')
395 {
396 if (sscanf(cp, "[%d][%d]", &i1, &i2) == 2)
397 {
398 indexCount = 2;
399 while (*cp++ != ']') /* Nothing */;
400 while (*cp++ != ']') /* Nothing */;
401 }
402 else if (sscanf(cp, "[%d,%d]", &i1, &i2) == 2)
403 {
404 indexCount = 2;
405 while (*cp++ != ']') /* Nothing */;
406 }
407 else if (sscanf(cp, "[%d]", &i1) == 1)
408 {
409 indexCount = 1;
410 while (*cp++ != ']') /* Nothing */;
411 }
412
413 if (indexCount && *cp != '\0' && *cp != '/')
414 return FALSE;
415 }
416
417 switch (indexCount)
418 {
419 case 0:
420 if (use->cu_xlo != use->cu_xhi || use->cu_ylo != use->cu_yhi)
421 return FALSE;
422 scx->scx_x = use->cu_xlo;
423 scx->scx_y = use->cu_ylo;
424 break;
425 case 1:
426 if (use->cu_xlo == use->cu_xhi)
427 {
428 scx->scx_x = use->cu_xlo;
429 scx->scx_y = i1;
430 }
431 else if (use->cu_ylo == use->cu_yhi)
432 {
433 scx->scx_x = i1;
434 scx->scx_y = use->cu_ylo;
435 }
436 else return FALSE;
437 break;
438 case 2:
439 if (use->cu_xlo == use->cu_xhi || use->cu_ylo == use->cu_yhi)
440 return FALSE;
441 scx->scx_y = i1;
442 scx->scx_x = i2;
443 break;
444 }
445
446 if (use->cu_xhi > use->cu_xlo)
447 {
448 if (scx->scx_x < use->cu_xlo || scx->scx_x > use->cu_xhi)
449 return FALSE;
450 xdelta = use->cu_xsep * (scx->scx_x - use->cu_xlo);
451 }
452 else
453 {
454 if (scx->scx_x > use->cu_xlo || scx->scx_x < use->cu_xhi)
455 return FALSE;
456 xdelta = use->cu_xsep * (use->cu_xlo - scx->scx_x);
457 }
458 if (use->cu_yhi > use->cu_ylo)
459 {
460 if (scx->scx_y < use->cu_ylo || scx->scx_y > use->cu_yhi)
461 return FALSE;
462 ydelta = use->cu_ysep * (scx->scx_y - use->cu_ylo);
463 }
464 else
465 {
466 if (scx->scx_y > use->cu_ylo || scx->scx_y < use->cu_yhi)
467 return FALSE;
468 ydelta = use->cu_ysep * (use->cu_ylo - scx->scx_y);
469 }
470
471 GeoTransTranslate(xdelta, ydelta, &use->cu_transform, &trans);
472 GeoTransTrans(&trans, &scx->scx_trans, &trans2);
473 scx->scx_trans = trans2;
474 return TRUE;
475 }
476
477 /*
478 * ----------------------------------------------------------------------------
479 *
480 * DBNearestLabel --
481 *
482 * This procedure finds the nearest label to a given point
483 * and returns its hierarchical name and location.
484 *
485 * Results:
486 * Area is searched in cellUse to find the nearest label
487 * to point. TRUE is returned if any label was found.
488 * If there is no label in the given area, FALSE is
489 * returned.
490 *
491 * Side effects:
492 * The parameter labelArea is filled in with the location of
493 * the label, if one was found. LabelName is filled in with
494 * the hierarchical name of the label.
495 *
496 * ----------------------------------------------------------------------------
497 */
498
499 bool
DBNearestLabel(cellUse,area,point,xMask,labelArea,labelName,length)500 DBNearestLabel(cellUse, area, point, xMask, labelArea, labelName, length)
501 CellUse *cellUse; /* Start search at this cell. */
502 Rect *area; /* Search this area of cellUse. */
503 Point *point; /* Find nearest label to this point. */
504 int xMask; /* Recursively search subcells as long
505 * as their expand masks, when anded with
506 * xMask, are equal to xMask. 0 means search
507 * all the way down through the hierarchy.
508 */
509 Rect *labelArea; /* To be filled in with area of closest
510 * label. NULL means ignore.
511 */
512 char *labelName; /* Fill this in with name of label, unless
513 * NULL.
514 */
515 int length; /* This gives the maximum number of chars
516 * that may be used in labelName, including
517 * the NULL character to terminate.
518 */
519 {
520 TerminalPath tPath, *tp;
521 SearchContext scx;
522 char *name;
523 struct nldata funcData;
524 extern int dbNearestLabelFunc();
525
526 /* Allocate space to generate a label name, and set up information
527 * for the DBTreeSrLabels call.
528 */
529
530 if (labelName == NULL) tp = NULL, name = NULL;
531 else
532 {
533 name = (char *) mallocMagic((unsigned) (length));
534 tPath.tp_first = name;
535 tPath.tp_next = name;
536 tPath.tp_last = name + length - 1;
537 tp = &tPath;
538 }
539 scx.scx_use = cellUse;
540 scx.scx_area = *area;
541 scx.scx_trans = GeoIdentityTransform;
542
543 funcData.nld_point = point;
544 funcData.nld_labelArea = labelArea;
545 funcData.nld_name = labelName;
546 funcData.nld_gotLabel = FALSE;
547
548 (void) DBTreeSrLabels(&scx, &DBAllTypeBits, xMask, tp, TF_LABEL_ATTACH,
549 dbNearestLabelFunc, (ClientData) &funcData);
550
551 if (name) freeMagic(name);
552
553 if (!funcData.nld_gotLabel) return FALSE;
554 else return TRUE;
555 }
556
557 /*
558 * ----------------------------------------------------------------------------
559 *
560 * dbNearestLabelFunc --
561 *
562 * This function is called by DBTreeSrLabels for each label
563 * found as part of DBNearestLabel.
564 *
565 * Results:
566 * Always returns 0 to continue the search.
567 *
568 * Side effects:
569 * If this is the closest label seen so far, update the information
570 * passed via funcData.
571 *
572 * ----------------------------------------------------------------------------
573 */
574
575 int
dbNearestLabelFunc(scx,label,tpath,funcData)576 dbNearestLabelFunc(scx, label, tpath, funcData)
577 SearchContext *scx; /* Describes state of search. */
578 Label *label; /* Label found. */
579 TerminalPath *tpath; /* Name of label. */
580 struct nldata *funcData; /* Parameters to DBNearestLabel (passed as
581 * ClientData).
582 */
583 {
584 int x, y, distance, left, used;
585 Rect area;
586 char *src, *dst;
587
588 GeoTransRect(&scx->scx_trans, &label->lab_rect, &area);
589 x = (area.r_xtop + area.r_xbot)/2 - funcData->nld_point->p_x;
590 y = (area.r_ytop + area.r_ybot)/2 - funcData->nld_point->p_y;
591 distance = x*x + y*y;
592 if ((funcData->nld_gotLabel) && (distance > funcData->nld_distance))
593 return 0;
594 funcData->nld_distance = distance;
595 funcData->nld_gotLabel = TRUE;
596
597 if (funcData->nld_labelArea != NULL)
598 *(funcData->nld_labelArea) = area;
599 if (funcData->nld_name != NULL)
600 {
601 left = tpath->tp_last - tpath->tp_next;
602 used = tpath->tp_next - tpath->tp_first;
603 (void) strncpy(funcData->nld_name, tpath->tp_first, used);
604 dst = funcData->nld_name + used;
605 src = label->lab_text;
606 for ( ; left > 0; left -= 1)
607 {
608 if (*src == 0) break;
609 *dst++ = *src++;
610 }
611 *dst = 0;
612 }
613
614 return 0;
615 }
616