Bug Summary

File:Tree.c
Location:line 909, column 11
Description:Dereference of null pointer

Annotated Source Code

1/*
2
3Copyright 1990, 1994, 1998 The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25 * Copyright 1989 Prentice Hall
26 *
27 * Permission to use, copy, modify, and distribute this software for any
28 * purpose and without fee is hereby granted, provided that the above
29 * copyright notice appear in all copies and that both the copyright notice
30 * and this permission notice appear in supporting documentation.
31 *
32 * Prentice Hall and the authors disclaim all warranties with regard
33 * to this software, including all implied warranties of merchantability and
34 * fitness. In no event shall Prentice Hall or the authors be liable
35 * for any special, indirect or cosequential damages or any damages whatsoever
36 * resulting from loss of use, data or profits, whether in an action of
37 * contract, negligence or other tortious action, arising out of or in
38 * connection with the use or performance of this software.
39 *
40 * Authors: Jim Fulton, MIT X Consortium,
41 * based on a version by Douglas Young, Prentice Hall
42 *
43 * This widget is based on the Tree widget described on pages 397-419 of
44 * Douglas Young's book "The X Window System, Programming and Applications
45 * with Xt OSF/Motif Edition." The layout code has been rewritten to use
46 * additional blank space to make the structure of the graph easier to see
47 * as well as to support vertical trees.
48 */
49
50#ifdef HAVE_CONFIG_H1
51#include <config.h>
52#endif
53#include <X11/IntrinsicP.h>
54#include <X11/StringDefs.h>
55#include <X11/Xaw/XawInit.h>
56#include <X11/Xaw/Cardinals.h>
57#include <X11/Xaw/TreeP.h>
58#include "Private.h"
59
60#define IsHorizontal(tw)((tw)->tree.gravity == 4 || (tw)->tree.gravity == 6) ((tw)->tree.gravity == WestGravity4 || \
61 (tw)->tree.gravity == EastGravity6)
62
63/*
64 * Class Methods
65 */
66static void XawTreeChangeManaged(Widget);
67static void XawTreeClassInitialize(void);
68static void XawTreeConstraintDestroy(Widget);
69static void XawTreeConstraintInitialize(Widget, Widget, ArgList, Cardinal*);
70static Boolean XawTreeConstraintSetValues(Widget, Widget, Widget,
71 ArgList, Cardinal*);
72static void XawTreeDestroy(Widget);
73static XtGeometryResult XawTreeGeometryManager(Widget, XtWidgetGeometry*,
74 XtWidgetGeometry*);
75static void XawTreeInitialize(Widget, Widget, ArgList, Cardinal*);
76static XtGeometryResult XawTreeQueryGeometry(Widget, XtWidgetGeometry*,
77 XtWidgetGeometry*);
78static void XawTreeRedisplay(Widget, XEvent*, Region);
79static Boolean XawTreeSetValues(Widget, Widget, Widget, ArgList, Cardinal*);
80
81/*
82 * Prototypes
83 */
84static void arrange_subtree(TreeWidget, Widget, int, int, int);
85static void check_gravity(TreeWidget, XtGravity);
86static void compute_bounding_box_subtree(TreeWidget, Widget, int);
87static void delete_node(Widget, Widget);
88static GC get_tree_gc(TreeWidget);
89static void initialize_dimensions(Dimension**, int*, int);
90static void insert_node(Widget, Widget);
91static void layout_tree(TreeWidget, Boolint);
92static void set_positions(TreeWidget, Widget, int);
93static void set_tree_size(TreeWidget, Boolint, unsigned int, unsigned int);
94
95/*
96 * Initialization
97 */
98
99/*
100 * resources of the tree itself
101 */
102static XtResource resources[] = {
103 { XtNautoReconfigure"autoReconfigure", XtCAutoReconfigure"AutoReconfigure", XtRBoolean((char*)&XtStrings[1561]), sizeof (Boolean),
104 XtOffsetOf(TreeRec, tree.auto_reconfigure)__builtin_offsetof(TreeRec, tree.auto_reconfigure), XtRImmediate((char*)&XtStrings[1695]),
105 (XtPointer) FALSE0 },
106 { XtNhSpace((char*)&XtStrings[251]), XtCHSpace((char*)&XtStrings[1058]), XtRDimension((char*)&XtStrings[1618]), sizeof (Dimension),
107 XtOffsetOf(TreeRec, tree.hpad)__builtin_offsetof(TreeRec, tree.hpad), XtRImmediate((char*)&XtStrings[1695]), (XtPointer) 0 },
108 { XtNvSpace((char*)&XtStrings[865]), XtCVSpace((char*)&XtStrings[1503]), XtRDimension((char*)&XtStrings[1618]), sizeof (Dimension),
109 XtOffsetOf(TreeRec, tree.vpad)__builtin_offsetof(TreeRec, tree.vpad), XtRImmediate((char*)&XtStrings[1695]), (XtPointer) 0 },
110 { XtNforeground((char*)&XtStrings[214]), XtCForeground((char*)&XtStrings[1022]), XtRPixel((char*)&XtStrings[1754]), sizeof (Pixel),
111 XtOffsetOf(TreeRec, tree.foreground)__builtin_offsetof(TreeRec, tree.foreground), XtRString((char*)&XtStrings[1797]),
112 XtDefaultForeground"XtDefaultForeground"},
113 { XtNlineWidth"lineWidth", XtCLineWidth"LineWidth", XtRDimension((char*)&XtStrings[1618]), sizeof (Dimension),
114 XtOffsetOf(TreeRec, tree.line_width)__builtin_offsetof(TreeRec, tree.line_width), XtRImmediate((char*)&XtStrings[1695]), (XtPointer) 0 },
115 { XtNgravity"gravity", XtCGravity"Gravity", XtRGravity((char*)&XtStrings[2042]), sizeof (XtGravity),
116 XtOffsetOf(TreeRec, tree.gravity)__builtin_offsetof(TreeRec, tree.gravity), XtRImmediate((char*)&XtStrings[1695]),
117 (XtPointer) WestGravity4 },
118#ifndef OLDXAW1
119 { XawNdisplayList, XawCDisplayList, XawRDisplayList, sizeof(XawDisplayList*),
120 XtOffsetOf(TreeRec, tree.display_list)__builtin_offsetof(TreeRec, tree.display_list), XtRImmediate((char*)&XtStrings[1695]),
121 NULL((void*)0) },
122#endif
123};
124
125
126/*
127 * resources that are attached to all children of the tree
128 */
129static XtResource treeConstraintResources[] = {
130 { XtNtreeParent"treeParent", XtCTreeParent"TreeParent", XtRWidget((char*)&XtStrings[1865]), sizeof (Widget),
131 XtOffsetOf(TreeConstraintsRec, tree.parent)__builtin_offsetof(TreeConstraintsRec, tree.parent), XtRImmediate((char*)&XtStrings[1695]), NULL((void*)0) },
132 { XtNtreeGC"treeGC", XtCTreeGC"TreeGC", XtRGC"GC", sizeof(GC),
133 XtOffsetOf(TreeConstraintsRec, tree.gc)__builtin_offsetof(TreeConstraintsRec, tree.gc), XtRImmediate((char*)&XtStrings[1695]), NULL((void*)0) },
134};
135
136
137TreeClassRec treeClassRec = {
138 {
139 /* core_class fields */
140 (WidgetClass) &constraintClassRec, /* superclass */
141 "Tree", /* class_name */
142 sizeof(TreeRec), /* widget_size */
143 XawTreeClassInitialize, /* class_init */
144 NULL((void*)0), /* class_part_init */
145 FALSE0, /* class_inited */
146 XawTreeInitialize, /* initialize */
147 NULL((void*)0), /* initialize_hook */
148 XtInheritRealize((XtRealizeProc) _XtInherit), /* realize */
149 NULL((void*)0), /* actions */
150 0, /* num_actions */
151 resources, /* resources */
152 XtNumber(resources)((Cardinal) (sizeof(resources) / sizeof(resources[0]))), /* num_resources */
153 NULLQUARK((XrmQuark) 0), /* xrm_class */
154 TRUE1, /* compress_motion */
155 TRUE1, /* compress_exposure */
156 TRUE1, /* compress_enterleave*/
157 TRUE1, /* visible_interest */
158 XawTreeDestroy, /* destroy */
159 NULL((void*)0), /* resize */
160 XawTreeRedisplay, /* expose */
161 XawTreeSetValues, /* set_values */
162 NULL((void*)0), /* set_values_hook */
163 XtInheritSetValuesAlmost((XtAlmostProc) _XtInherit), /* set_values_almost */
164 NULL((void*)0), /* get_values_hook */
165 NULL((void*)0), /* accept_focus */
166 XtVersion(11 * 1000 + 6), /* version */
167 NULL((void*)0), /* callback_private */
168 NULL((void*)0), /* tm_table */
169 XawTreeQueryGeometry, /* query_geometry */
170 NULL((void*)0), /* display_accelerator*/
171 NULL((void*)0), /* extension */
172 },
173 {
174 /* composite_class fields */
175 XawTreeGeometryManager, /* geometry_manager */
176 XawTreeChangeManaged, /* change_managed */
177 XtInheritInsertChild((XtWidgetProc) _XtInherit), /* insert_child */
178 XtInheritDeleteChild((XtWidgetProc) _XtInherit), /* delete_child */
179 NULL((void*)0), /* extension */
180 },
181 {
182 /* constraint_class fields */
183 treeConstraintResources, /* subresources */
184 XtNumber(treeConstraintResources)((Cardinal) (sizeof(treeConstraintResources) / sizeof(treeConstraintResources
[0]))), /* subresource_count */
185 sizeof(TreeConstraintsRec), /* constraint_size */
186 XawTreeConstraintInitialize, /* initialize */
187 XawTreeConstraintDestroy, /* destroy */
188 XawTreeConstraintSetValues, /* set_values */
189 NULL((void*)0), /* extension */
190 },
191 {
192 /* Tree class fields */
193 NULL((void*)0), /* ignore */
194 }
195};
196
197WidgetClass treeWidgetClass = (WidgetClass) &treeClassRec;
198
199
200/*****************************************************************************
201 * *
202 * tree utility routines *
203 * *
204 *****************************************************************************/
205
206static void
207initialize_dimensions(Dimension **listp, int *sizep, int n)
208{
209 int i;
210 Dimension *l;
211
212 if (!*listp) {
213 *listp = (Dimension *) XtCalloc ((unsigned int) n,
214 (unsigned int) sizeof(Dimension));
215 *sizep = ((*listp) ? n : 0);
216 return;
217 }
218 if (n > *sizep) {
219 *listp = (Dimension *) XtRealloc((char *) *listp,
220 (unsigned int) (n*sizeof(Dimension)));
221 if (!*listp) {
222 *sizep = 0;
223 return;
224 }
225 for (i = *sizep, l = (*listp) + i; i < n; i++, l++) *l = 0;
226 *sizep = n;
227 }
228 return;
229}
230
231static GC
232get_tree_gc(TreeWidget w)
233{
234 XtGCMask valuemask = GCBackground(1L<<3) | GCForeground(1L<<2);
235 XGCValues values;
236
237 values.background = w->core.background_pixel;
238 values.foreground = w->tree.foreground;
239 if (w->tree.line_width != 0) {
240 valuemask |= GCLineWidth(1L<<4);
241 values.line_width = w->tree.line_width;
242 }
243
244 return XtGetGC ((Widget) w, valuemask, &values);
245}
246
247static void
248insert_node(Widget parent, Widget node)
249{
250 TreeConstraints pc;
251 TreeConstraints nc = TREE_CONSTRAINT(node)((TreeConstraints)((node)->core.constraints));
252 int nindex;
253
254 nc->tree.parent = parent;
255
256 if (parent == NULL((void*)0)) return;
257
258 /*
259 * If there isn't more room in the children array,
260 * allocate additional space.
261 */
262 pc = TREE_CONSTRAINT(parent)((TreeConstraints)((parent)->core.constraints));
263 nindex = pc->tree.n_children;
264
265 if (pc->tree.n_children == pc->tree.max_children) {
266 pc->tree.max_children += (pc->tree.max_children / 2) + 2;
267 pc->tree.children = (WidgetList) XtRealloc ((char *)pc->tree.children,
268 (unsigned int)
269 ((pc->tree.max_children) *
270 sizeof(Widget)));
271 }
272
273 /*
274 * Add the sub_node in the next available slot and
275 * increment the counter.
276 */
277 pc->tree.children[nindex] = node;
278 pc->tree.n_children++;
279}
280
281static void
282delete_node(Widget parent, Widget node)
283{
284 TreeConstraints pc;
285 int pos, i;
286
287 /*
288 * Make sure the parent exists.
289 */
290 if (!parent) return;
291
292 pc = TREE_CONSTRAINT(parent)((TreeConstraints)((parent)->core.constraints));
293
294 /*
295 * Find the sub_node on its parent's list.
296 */
297 for (pos = 0; pos < pc->tree.n_children; pos++)
298 if (pc->tree.children[pos] == node) break;
299
300 if (pos == pc->tree.n_children) return;
301
302 /*
303 * Decrement the number of children
304 */
305 pc->tree.n_children--;
306
307 /*
308 * Fill in the gap left by the sub_node.
309 * Zero the last slot for good luck.
310 */
311 for (i = pos; i < pc->tree.n_children; i++)
312 pc->tree.children[i] = pc->tree.children[i+1];
313
314 pc->tree.children[pc->tree.n_children] = NULL((void*)0);
315}
316
317static void
318check_gravity(TreeWidget tw, XtGravity grav)
319{
320 switch (tw->tree.gravity) {
321 case WestGravity4: case NorthGravity2: case EastGravity6: case SouthGravity8:
322 break;
323 default:
324 tw->tree.gravity = grav;
325 break;
326 }
327}
328
329
330/*****************************************************************************
331 * *
332 * tree class methods *
333 * *
334 *****************************************************************************/
335
336static void
337XawTreeClassInitialize(void)
338{
339 XawInitializeWidgetSet();
340 XtAddConverter(XtRString((char*)&XtStrings[1797]), XtRGravity((char*)&XtStrings[2042]), XmuCvtStringToGravity, NULL((void*)0), 0);
341 XtSetTypeConverter(XtRGravity((char*)&XtStrings[2042]), XtRString((char*)&XtStrings[1797]), XmuCvtGravityToString,
342 NULL((void*)0), 0, XtCacheNone0x001, NULL((void*)0));
343}
344
345
346/*ARGSUSED*/
347static void
348XawTreeInitialize(Widget grequest, Widget gnew,
349 ArgList args, Cardinal *num_args)
350{
351 TreeWidget request = (TreeWidget) grequest, cnew = (TreeWidget) gnew;
352 Arg arglist[2];
353
354 /*
355 * Make sure the widget's width and height are
356 * greater than zero.
357 */
358 if (request->core.width <= 0) cnew->core.width = 5;
359 if (request->core.height <= 0) cnew->core.height = 5;
360
361 /*
362 * Set the padding according to the orientation
363 */
364 if (request->tree.hpad == 0 && request->tree.vpad == 0) {
365 if (IsHorizontal (request)((request)->tree.gravity == 4 || (request)->tree.gravity
== 6)) {
366 cnew->tree.hpad = TREE_HORIZONTAL_DEFAULT_SPACING20;
367 cnew->tree.vpad = TREE_VERTICAL_DEFAULT_SPACING6;
368 } else {
369 cnew->tree.hpad = TREE_VERTICAL_DEFAULT_SPACING6;
370 cnew->tree.vpad = TREE_HORIZONTAL_DEFAULT_SPACING20;
371 }
372 }
373
374 /*
375 * Create a graphics context for the connecting lines.
376 */
377 cnew->tree.gc = get_tree_gc (cnew);
378
379 /*
380 * Create the hidden root widget.
381 */
382 cnew->tree.tree_root = (Widget) NULL((void*)0);
383 XtSetArg(arglist[0], XtNwidth, 1)((void)( (arglist[0]).name = (((char*)&XtStrings[872])), (
arglist[0]).value = (XtArgVal)(1) ));
384 XtSetArg(arglist[1], XtNheight, 1)((void)( (arglist[1]).name = (((char*)&XtStrings[234])), (
arglist[1]).value = (XtArgVal)(1) ));
385 cnew->tree.tree_root = XtCreateWidget ("root", widgetClass, gnew,
386 arglist,TWO((Cardinal)2));
387
388 /*
389 * Allocate the array used to hold the widest values per depth
390 */
391 cnew->tree.largest = NULL((void*)0);
392 cnew->tree.n_largest = 0;
393 initialize_dimensions (&cnew->tree.largest, &cnew->tree.n_largest,
394 TREE_INITIAL_DEPTH10);
395
396 /*
397 * make sure that our gravity is one of the acceptable values
398 */
399 check_gravity (cnew, WestGravity4);
400}
401
402
403/* ARGSUSED */
404static void
405XawTreeConstraintInitialize(Widget request, Widget cnew,
406 ArgList args, Cardinal *num_args)
407{
408 TreeConstraints tc = TREE_CONSTRAINT(cnew)((TreeConstraints)((cnew)->core.constraints));
409 TreeWidget tw = (TreeWidget) cnew->core.parent;
410
411 /*
412 * Initialize the widget to have no sub-nodes.
413 */
414 tc->tree.n_children = 0;
415 tc->tree.max_children = 0;
416 tc->tree.children = (Widget *) NULL((void*)0);
417 tc->tree.x = tc->tree.y = 0;
418 tc->tree.bbsubwidth = 0;
419 tc->tree.bbsubheight = 0;
420
421
422 /*
423 * If this widget has a super-node, add it to that
424 * widget' sub-nodes list. Otherwise make it a sub-node of
425 * the tree_root widget.
426 */
427 if (tc->tree.parent)
428 insert_node (tc->tree.parent, cnew);
429 else if (tw->tree.tree_root)
430 insert_node (tw->tree.tree_root, cnew);
431}
432
433
434/* ARGSUSED */
435static Boolean
436XawTreeSetValues(Widget gcurrent, Widget grequest, Widget gnew,
437 ArgList args, Cardinal *num_args)
438{
439 TreeWidget current = (TreeWidget) gcurrent, cnew = (TreeWidget) gnew;
440 Boolean redraw = FALSE0;
441
442 /*
443 * If the foreground color has changed, redo the GC's
444 * and indicate a redraw.
445 */
446 if (cnew->tree.foreground != current->tree.foreground ||
447 cnew->core.background_pixel != current->core.background_pixel ||
448 cnew->tree.line_width != current->tree.line_width) {
449 XtReleaseGC (gnew, cnew->tree.gc);
450 cnew->tree.gc = get_tree_gc (cnew);
451 redraw = TRUE1;
452 }
453
454 /*
455 * If the minimum spacing has changed, recalculate the
456 * tree layout. layout_tree() does a redraw, so we don't
457 * need SetValues to do another one.
458 */
459 if (cnew->tree.gravity != current->tree.gravity) {
460 check_gravity (cnew, current->tree.gravity);
461 }
462
463 if (IsHorizontal(cnew)((cnew)->tree.gravity == 4 || (cnew)->tree.gravity == 6
) != IsHorizontal(current)((current)->tree.gravity == 4 || (current)->tree.gravity
== 6)) {
464 if (cnew->tree.vpad == current->tree.vpad &&
465 cnew->tree.hpad == current->tree.hpad) {
466 cnew->tree.vpad = current->tree.hpad;
467 cnew->tree.hpad = current->tree.vpad;
468 }
469 }
470
471 if (cnew->tree.vpad != current->tree.vpad ||
472 cnew->tree.hpad != current->tree.hpad ||
473 cnew->tree.gravity != current->tree.gravity) {
474 layout_tree (cnew, TRUE1);
475 redraw = FALSE0;
476 }
477 return redraw;
478}
479
480
481/* ARGSUSED */
482static Boolean
483XawTreeConstraintSetValues(Widget current, Widget request, Widget cnew,
484 ArgList args, Cardinal *num_args)
485{
486 TreeConstraints newc = TREE_CONSTRAINT(cnew)((TreeConstraints)((cnew)->core.constraints));
487 TreeConstraints curc = TREE_CONSTRAINT(current)((TreeConstraints)((current)->core.constraints));
488 TreeWidget tw = (TreeWidget) cnew->core.parent;
489
490 /*
491 * If the parent field has changed, remove the widget
492 * from the old widget's children list and add it to the
493 * new one.
494 */
495 if (curc->tree.parent != newc->tree.parent){
496 if (curc->tree.parent)
497 delete_node (curc->tree.parent, cnew);
498 if (newc->tree.parent)
499 insert_node(newc->tree.parent, cnew);
500
501 /*
502 * If the Tree widget has been realized,
503 * compute new layout.
504 */
505 if (XtIsRealized((Widget)tw)(XtWindowOfObject((Widget)tw) != 0L))
506 layout_tree (tw, FALSE0);
507 }
508 return False0;
509}
510
511
512static void
513XawTreeConstraintDestroy(Widget w)
514{
515 TreeConstraints tc = TREE_CONSTRAINT(w)((TreeConstraints)((w)->core.constraints));
516 TreeWidget tw = (TreeWidget) XtParent(w)((w)->core.parent);
517 int i;
518
519 /*
520 * Remove the widget from its parent's sub-nodes list and
521 * make all this widget's sub-nodes sub-nodes of the parent.
522 */
523
524 if (tw->tree.tree_root == w) {
525 if (tc->tree.n_children > 0)
526 tw->tree.tree_root = tc->tree.children[0];
527 else
528 tw->tree.tree_root = NULL((void*)0);
529 }
530
531 delete_node (tc->tree.parent, (Widget) w);
532 for (i = 0; i< tc->tree.n_children; i++)
533 insert_node (tc->tree.parent, tc->tree.children[i]);
534
535 layout_tree ((TreeWidget) (w->core.parent), FALSE0);
536}
537
538/* ARGSUSED */
539static XtGeometryResult
540XawTreeGeometryManager(Widget w, XtWidgetGeometry *request,
541 XtWidgetGeometry *reply)
542{
543
544 TreeWidget tw = (TreeWidget) w->core.parent;
545
546 /*
547 * No position changes allowed!.
548 */
549 if ((request->request_mode & CWX(1<<0) && request->x!=w->core.x)
550 ||(request->request_mode & CWY(1<<1) && request->y!=w->core.y))
551 return (XtGeometryNo);
552
553 /*
554 * Allow all resize requests.
555 */
556
557 if (request->request_mode & CWWidth(1<<2))
558 w->core.width = request->width;
559 if (request->request_mode & CWHeight(1<<3))
560 w->core.height = request->height;
561 if (request->request_mode & CWBorderWidth(1<<4))
562 w->core.border_width = request->border_width;
563
564 if (tw->tree.auto_reconfigure) layout_tree (tw, FALSE0);
565 return (XtGeometryYes);
566}
567
568static void
569XawTreeChangeManaged(Widget gw)
570{
571 layout_tree ((TreeWidget) gw, FALSE0);
572}
573
574
575static void
576XawTreeDestroy(Widget gw)
577{
578 TreeWidget w = (TreeWidget) gw;
579
580 XtReleaseGC (gw, w->tree.gc);
581 if (w->tree.largest) XtFree ((char *) w->tree.largest);
582}
583
584
585/* ARGSUSED */
586static void
587XawTreeRedisplay(Widget gw, XEvent *event, Region region)
588{
589 TreeWidget tw = (TreeWidget) gw;
590
591#ifndef OLDXAW1
592 if (tw->tree.display_list)
593 XawRunDisplayList(gw, tw->tree.display_list, event, region);
594#endif
595
596 /*
597 * If the Tree widget is visible, visit each managed child.
598 */
599 if (tw->core.visible) {
600 Cardinal i;
601 int j;
602 Display *dpy = XtDisplay (tw)(((tw)->core.screen)->display);
603 Window w = XtWindow (tw)((tw)->core.window);
604
605 for (i = 0; i < tw->composite.num_children; i++) {
606 Widget child = tw->composite.children[i];
607 TreeConstraints tc = TREE_CONSTRAINT(child)((TreeConstraints)((child)->core.constraints));
608
609 /*
610 * Don't draw lines from the fake tree_root.
611 */
612 if (child != tw->tree.tree_root && tc->tree.n_children) {
613 int srcx = child->core.x + child->core.border_width;
614 int srcy = child->core.y + child->core.border_width;
615
616 switch (tw->tree.gravity) {
617 case WestGravity4:
618 srcx += child->core.width + child->core.border_width;
619 /* fall through */
620 case EastGravity6:
621 srcy += child->core.height / 2;
622 break;
623
624 case NorthGravity2:
625 srcy += child->core.height + child->core.border_width;
626 /* fall through */
627 case SouthGravity8:
628 srcx += child->core.width / 2;
629 break;
630 }
631
632 for (j = 0; j < tc->tree.n_children; j++) {
633 Widget k = tc->tree.children[j];
634 GC gc = (tc->tree.gc ? tc->tree.gc : tw->tree.gc);
635
636 switch (tw->tree.gravity) {
637 case WestGravity4:
638 /*
639 * right center to left center
640 */
641 XDrawLine (dpy, w, gc, srcx, srcy,
642 (int) k->core.x,
643 (k->core.y + ((int) k->core.border_width) +
644 ((int) k->core.height) / 2));
645 break;
646
647 case NorthGravity2:
648 /*
649 * bottom center to top center
650 */
651 XDrawLine (dpy, w, gc, srcx, srcy,
652 (k->core.x + ((int) k->core.border_width) +
653 ((int) k->core.width) / 2),
654 (int) k->core.y);
655 break;
656
657 case EastGravity6:
658 /*
659 * left center to right center
660 */
661 XDrawLine (dpy, w, gc, srcx, srcy,
662 (k->core.x +
663 (((int) k->core.border_width) << 1) +
664 (int) k->core.width),
665 (k->core.y + ((int) k->core.border_width) +
666 ((int) k->core.height) / 2));
667 break;
668
669 case SouthGravity8:
670 /*
671 * top center to bottom center
672 */
673 XDrawLine (dpy, w, gc, srcx, srcy,
674 (k->core.x + ((int) k->core.border_width) +
675 ((int) k->core.width) / 2),
676 (k->core.y +
677 (((int) k->core.border_width) << 1) +
678 (int) k->core.height));
679 break;
680 }
681 }
682 }
683 }
684 }
685}
686
687static XtGeometryResult
688XawTreeQueryGeometry(Widget w, XtWidgetGeometry *intended,
689 XtWidgetGeometry *preferred)
690{
691 TreeWidget tw = (TreeWidget) w;
692
693 preferred->request_mode = (CWWidth(1<<2) | CWHeight(1<<3));
694 preferred->width = tw->tree.maxwidth;
695 preferred->height = tw->tree.maxheight;
696
697 if (((intended->request_mode & (CWWidth(1<<2) | CWHeight(1<<3))) ==
698 (CWWidth(1<<2) | CWHeight(1<<3))) &&
699 intended->width == preferred->width &&
700 intended->height == preferred->height)
701 return XtGeometryYes;
702 else if (preferred->width == w->core.width &&
703 preferred->height == w->core.height)
704 return XtGeometryNo;
705 else
706 return XtGeometryAlmost;
707}
708
709
710/*****************************************************************************
711 * *
712 * tree layout algorithm *
713 * *
714 * Each node in the tree is "shrink-wrapped" with a minimal bounding *
715 * rectangle, laid next to its siblings (with a small about of padding in *
716 * between) and then wrapped with their parent. Parents are centered about *
717 * their children (or vice versa if the parent is larger than the children). *
718 * *
719 *****************************************************************************/
720
721static void
722compute_bounding_box_subtree(TreeWidget tree, Widget w, int depth)
723{
724 TreeConstraints tc = TREE_CONSTRAINT(w)((TreeConstraints)((w)->core.constraints)); /* info attached to all kids */
725 int i;
726 Boolint horiz = IsHorizontal (tree)((tree)->tree.gravity == 4 || (tree)->tree.gravity == 6
);
727 Dimension newwidth, newheight;
728 Dimension bw2 = w->core.border_width * 2;
729
730 /*
731 * Set the max-size per level.
732 */
733 if (depth >= tree->tree.n_largest) {
734 initialize_dimensions (&tree->tree.largest,
735 &tree->tree.n_largest, depth + 1);
736 }
737 newwidth = ((horiz ? w->core.width : w->core.height) + bw2);
738 if (tree->tree.largest[depth] < newwidth)
739 tree->tree.largest[depth] = newwidth;
740
741
742 /*
743 * initialize
744 */
745 tc->tree.bbwidth = w->core.width + bw2;
746 tc->tree.bbheight = w->core.height + bw2;
747
748 if (tc->tree.n_children == 0) return;
749
750 /*
751 * Figure the size of the opposite dimension (vertical if tree is
752 * horizontal, else vice versa). The other dimension will be set
753 * in the second pass once we know the maximum dimensions.
754 */
755 newwidth = 0;
756 newheight = 0;
757 for (i = 0; i < tc->tree.n_children; i++) {
758 Widget child = tc->tree.children[i];
759 TreeConstraints cc = TREE_CONSTRAINT(child)((TreeConstraints)((child)->core.constraints));
760
761 compute_bounding_box_subtree (tree, child, depth + 1);
762
763 if (horiz) {
764 if (newwidth < cc->tree.bbwidth) newwidth = cc->tree.bbwidth;
765 newheight += tree->tree.vpad + cc->tree.bbheight;
766 } else {
767 if (newheight < cc->tree.bbheight) newheight = cc->tree.bbheight;
768 newwidth += tree->tree.hpad + cc->tree.bbwidth;
769 }
770 }
771
772
773 tc->tree.bbsubwidth = newwidth;
774 tc->tree.bbsubheight = newheight;
775
776 /*
777 * Now fit parent onto side (or top) of bounding box and correct for
778 * extra padding. Be careful of unsigned arithmetic.
779 */
780 if (horiz) {
781 tc->tree.bbwidth += tree->tree.hpad + newwidth;
782 newheight -= tree->tree.vpad;
783 if (newheight > tc->tree.bbheight) tc->tree.bbheight = newheight;
784 } else {
785 tc->tree.bbheight += tree->tree.vpad + newheight;
786 newwidth -= tree->tree.hpad;
787 if (newwidth > tc->tree.bbwidth) tc->tree.bbwidth = newwidth;
788 }
789}
790
791
792static void
793set_positions(TreeWidget tw, Widget w, int level)
794{
795 int i;
796
797 if (w) {
798 TreeConstraints tc = TREE_CONSTRAINT(w)((TreeConstraints)((w)->core.constraints));
799
800 if (level > 0) {
801 /*
802 * mirror if necessary
803 */
804 switch (tw->tree.gravity) {
805 case EastGravity6:
806 tc->tree.x = (((Position) tw->tree.maxwidth) -
807 ((Position) w->core.width) - tc->tree.x);
808 break;
809
810 case SouthGravity8:
811 tc->tree.y = (((Position) tw->tree.maxheight) -
812 ((Position) w->core.height) - tc->tree.y);
813 break;
814 }
815
816 /*
817 * Move the widget into position.
818 */
819 XtMoveWidget (w, tc->tree.x, tc->tree.y);
820 }
821
822 /*
823 * Set the positions of all children.
824 */
825 for (i = 0; i < tc->tree.n_children; i++)
826 set_positions (tw, tc->tree.children[i], level + 1);
827 }
828}
829
830
831static void
832arrange_subtree(TreeWidget tree, Widget w, int depth, int x, int y)
833{
834 TreeConstraints tc = TREE_CONSTRAINT(w)((TreeConstraints)((w)->core.constraints)); /* info attached to all kids */
835 TreeConstraints firstcc, lastcc;
836 int i;
837 int newx, newy;
838 Boolint horiz = IsHorizontal (tree)((tree)->tree.gravity == 4 || (tree)->tree.gravity == 6
);
839 Widget child = NULL((void*)0);
840 Dimension tmp;
841 Dimension bw2 = w->core.border_width * 2;
842 Boolint relayout = True1;
843
844
845 /*
846 * If no children, then just lay out where requested.
847 */
848 tc->tree.x = x;
849 tc->tree.y = y;
850
851 if (horiz) {
1
Taking true branch
852 int myh = (w->core.height + bw2);
853
854 if (myh > (int)tc->tree.bbsubheight) {
2
Taking false branch
855 y += (myh - (int)tc->tree.bbsubheight) / 2;
856 relayout = False0;
857 }
858 } else {
859 int myw = (w->core.width + bw2);
860
861 if (myw > (int)tc->tree.bbsubwidth) {
862 x += (myw - (int)tc->tree.bbsubwidth) / 2;
863 relayout = False0;
864 }
865 }
866
867 if ((tmp = ((Dimension) x) + tc->tree.bbwidth) > tree->tree.maxwidth)
3
Taking false branch
868 tree->tree.maxwidth = tmp;
869 if ((tmp = ((Dimension) y) + tc->tree.bbheight) > tree->tree.maxheight)
4
Taking false branch
870 tree->tree.maxheight = tmp;
871
872 if (tc->tree.n_children == 0) return;
5
Taking false branch
873
874
875 /*
876 * Have children, so walk down tree laying out children, then laying
877 * out parents.
878 */
879 if (horiz) {
6
Taking true branch
880 newx = x + tree->tree.largest[depth];
881 if (depth > 0) newx += tree->tree.hpad;
7
Assuming 'depth' is <= 0
8
Taking false branch
882 newy = y;
883 } else {
884 newx = x;
885 newy = y + tree->tree.largest[depth];
886 if (depth > 0) newy += tree->tree.vpad;
887 }
888
889 for (i = 0; i < tc->tree.n_children; i++) {
9
Loop condition is false. Execution continues on line 906
890 TreeConstraints cc;
891
892 child = tc->tree.children[i]; /* last value is used outside loop */
893 cc = TREE_CONSTRAINT(child)((TreeConstraints)((child)->core.constraints));
894
895 arrange_subtree (tree, child, depth + 1, newx, newy);
896 if (horiz) {
897 newy += tree->tree.vpad + cc->tree.bbheight;
898 } else {
899 newx += tree->tree.hpad + cc->tree.bbwidth;
900 }
901 }
902
903 /*
904 * now layout parent between first and last children
905 */
906 if (relayout) {
10
Taking true branch
907 Position adjusted;
908 firstcc = TREE_CONSTRAINT (tc->tree.children[0])((TreeConstraints)((tc->tree.children[0])->core.constraints
));
909 lastcc = TREE_CONSTRAINT (child)((TreeConstraints)((child)->core.constraints));
11
Within the expansion of the macro 'TREE_CONSTRAINT':
a
Dereference of null pointer
910
911 /* Adjustments are disallowed if they result in a position above
912 * or to the left of the originally requested position, because
913 * this could collide with the position of the previous sibling.
914 */
915 if (horiz) {
916 tc->tree.x = x;
917 adjusted = firstcc->tree.y +
918 ((lastcc->tree.y + (Position) child->core.height +
919 (Position) child->core.border_width * 2 -
920 firstcc->tree.y - (Position) w->core.height -
921 (Position) w->core.border_width * 2 + 1) / 2);
922 if (adjusted > tc->tree.y) tc->tree.y = adjusted;
923 } else {
924 adjusted = firstcc->tree.x +
925 ((lastcc->tree.x + (Position) child->core.width +
926 (Position) child->core.border_width * 2 -
927 firstcc->tree.x - (Position) w->core.width -
928 (Position) w->core.border_width * 2 + 1) / 2);
929 if (adjusted > tc->tree.x) tc->tree.x = adjusted;
930 tc->tree.y = y;
931 }
932 }
933}
934
935static void
936set_tree_size(TreeWidget tw, Boolint insetvalues,
937 unsigned int width, unsigned int height)
938{
939 if (insetvalues) {
940 tw->core.width = width;
941 tw->core.height = height;
942 } else {
943 Dimension replyWidth = 0, replyHeight = 0;
944 XtGeometryResult result = XtMakeResizeRequest ((Widget) tw,
945 width, height,
946 &replyWidth,
947 &replyHeight);
948 /*
949 * Accept any compromise.
950 */
951 if (result == XtGeometryAlmost)
952 XtMakeResizeRequest ((Widget) tw, replyWidth, replyHeight,
953 (Dimension *) NULL((void*)0), (Dimension *) NULL((void*)0));
954 }
955 return;
956}
957
958static void
959layout_tree(TreeWidget tw, Boolint insetvalues)
960{
961 int i;
962 Dimension *dp;
963
964 /*
965 * Do a depth-first search computing the width and height of the bounding
966 * box for the tree at that position (and below). Then, walk again using
967 * this information to layout the children at each level.
968 */
969
970 if (tw->tree.tree_root == NULL((void*)0))
971 return;
972
973 tw->tree.maxwidth = tw->tree.maxheight = 0;
974 for (i = 0, dp = tw->tree.largest; i < tw->tree.n_largest; i++, dp++)
975 *dp = 0;
976 initialize_dimensions (&tw->tree.largest, &tw->tree.n_largest,
977 tw->tree.n_largest);
978 compute_bounding_box_subtree (tw, tw->tree.tree_root, 0);
979
980 /*
981 * Second pass to do final layout. Each child's bounding box is stacked
982 * on top of (if horizontal, else next to) on top of its siblings. The
983 * parent is centered between the first and last children.
984 */
985 arrange_subtree (tw, tw->tree.tree_root, 0, 0, 0);
986
987 /*
988 * Move each widget into place.
989 */
990 set_tree_size (tw, insetvalues, tw->tree.maxwidth, tw->tree.maxheight);
991 set_positions (tw, tw->tree.tree_root, 0);
992
993 /*
994 * And redisplay.
995 */
996 if (XtIsRealized ((Widget) tw)(XtWindowOfObject((Widget) tw) != 0L)) {
997 XClearArea (XtDisplay(tw)(((tw)->core.screen)->display), XtWindow((Widget)tw)(((Widget)tw)->core.window), 0, 0, 0, 0, True1);
998 }
999}
1000
1001
1002
1003/*****************************************************************************
1004 * *
1005 * Public Routines *
1006 * *
1007 *****************************************************************************/
1008
1009void
1010XawTreeForceLayout(Widget tree)
1011{
1012 layout_tree ((TreeWidget) tree, FALSE0);
1013}
1014