Same problem probably. Lots of widgets in a ScrolledWindow on both Linux and Solaris. One more click and it freezes in a loop. Here are some traces. The common factor is _XmNewTravGraph:

Linux:

#0 0x002e7748 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#1 0x002e799e in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#2 0x002e827b in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#3 0x002e85d5 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#4 0x002e70a1 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#5 0x002e699a in _XmTraverseAway () from /usr/X11R6/lib/libXm.so.2
#6 0x002e3d57 in _XmNavigSetValues () from /usr/X11R6/lib/libXm.so.2
#7 0x002e1ad9 in XmSetProtocolHooks () from /usr/X11R6/lib/libXm.so.2
#8 0x001426f3 in XtSetSensitive () from /usr/X11R6/lib/libXt.so.6
#9 0x001426ac in XtSetSensitive () from /usr/X11R6/lib/libXt.so.6
#10 0x001426ac in XtSetSensitive () from /usr/X11R6/lib/libXt.so.6
#11 0x00142c33 in XtSetValues () from /usr/X11R6/lib/libXt.so.6
#12 0x082c3f42 in MotifButton::setSensitivity (this=0x96cc208) at ../../../../src/zc/impl_motif/motifInterface.C:3289
#13 0x082d9ca5 in MotifActionRepresentation::setAction (this=0x96cc208, action=0x0) at ../../../../src/zc/impl_motif/motifRepresentation.C:69
#14 0x081efee8 in InterfaceComponent::setAction (this=0x96cc1b0, action=0x0, clientData=0x0) at ../../../../src/zc/view_interface/interface.C:332
#15 0x08208a5d in MenuEntryView::setSensitive (this=0x96cc4c8, sensitive=false) at ../../../../src/zc/part_interface/Menu.C:577
#16 0x08207e04 in MenuEntry::setSensitive (this=0x96552e8, sensitive=false) at ../../../../src/zc/part_interface/Menu.C:340
#17 0x08203958 in InteractiveDocument::updateSelectionStates (this=0x9654fb0) at ../../../../src/zc/part_interface/InteractiveDocument.C:921
#18 0x0820381c in InteractiveDocument::updateMenuSystemStates (this=0x9654fb0) at ../../../../src/zc/part_interface/InteractiveDocument.C:893
#19 0x08201e4a in InteractiveDocument::unsetSelection (this=0x9654fb0, oldSelection=0xbed0c00)
at ../../../../src/zc/part_interface/InteractiveDocument.C:567
#20 0x081bab45 in InstanceModel::managerDeletedNotify () at ../../../../src/zc/util_base/environment.h:213
#21 0x081b72e1 in InstanceManager::~InstanceManager$base () at ../../../../src/zc/util_base/environment.h:213
#22 0x080c46b0 in NodeInstanceManager::~NodeInstanceManager$base () at /build/0/heatthoa/latest/vobs/recall_src/src/xc/Wa/WaRcsId.h:163
#23 0x080a9e2d in ~JobEditNodeManager (this=0xbed0890) at ../../../../src/zc/job_edit/JobEditNodeManager.C:351
#24 0x080abada in ~PageJobEditNodeManager (this=0xbed0890) at ../../../../src/zc/job_edit/JobEditNodeManager.C:777
#25 0x080c3afd in NodeDiplomat::~NodeDiplomat$base () at /build/0/heatthoa/latest/vobs/recall_src/src/xc/Wa/WaRcsId.h:163
#26 0x0807f9e2 in ~JobEditNode (this=0xbefacf0) at ../../../../src/zc/job_edit/JobEditNode.C:493
#27 0x08089588 in ~Node (this=0xbefacd8) at ../../../../src/zc/util_lang/Node.cxx:37
#28 0x08301b07 in TreeBase::deleteNode () at ../../../../src/xc/Wa/WaRcsId.h:163
#29 0x080847ca in JobEditNode::doDelete (this=0xbefacf0, s=@0xbfff94c0) at ../../../../src/zc/job_edit/JobEditNode.C:1599
#30 0x080aacdf in JobEditNodeManager::doDelete (this=0xbed0890) at ../../../../src/zc/job_edit/JobEditNodeManager.C:554
#31 0x081bf117 in InstanceModel::doDelete () at ../../../../src/zc/util_base/environment.h:213
#32 0x081c31b2 in InstanceTransfer::doDelete () at ../../../../src/zc/util_base/environment.h:213
#33 0x08201dc7 in InteractiveDocument::deleteItem (this=0x9654fb0) at ../../../../src/zc/part_interface/InteractiveDocument.C:547
#34 0x08205c56 in InteractiveDocument::deleteAction (this=0x9654fb0) at ../../../../src/zc/part_interface/InteractiveDocument.h:550
#35 0x081fe230 in DocumentAction::execute (this=0x9655650, inputComponent=0x96cc1b0) at ../../../../src/zc/part_interface/InteractiveDocument.C:267
#36 0x082d9c6c in MotifActionRepresentation::executeAction (this=0x96cc208) at ../../../../src/zc/impl_motif/motifRepresentation.C:55
#37 0x082c3502 in MotifButton::pressCallback (me=0x96cc208, cstruct=0xbfff9630) at ../../../../src/zc/impl_motif/motifInterface.C:3102
#38 0x0011e80d in XtCallCallbackList () from /usr/X11R6/lib/libXt.so.6
#39 0x0027360b in XmCreatePanedWindow () from /usr/X11R6/lib/libXm.so.2
#40 0x00152a3a in _XtMatchAtom () from /usr/X11R6/lib/libXt.so.6
#41 0x00153417 in _XtMatchAtom () from /usr/X11R6/lib/libXt.so.6
#42 0x0015354c in _XtTranslateEvent () from /usr/X11R6/lib/libXt.so.6
#43 0x0012b834 in XtDispatchEventToWidget () from /usr/X11R6/lib/libXt.so.6
#44 0x0012c378 in _XtOnGrabList () from /usr/X11R6/lib/libXt.so.6
#45 0x0012c52f in XtDispatchEvent () from /usr/X11R6/lib/libXt.so.6
#46 0x082b0a22 in MotifEnvironment::m_waitLoop (e=0x962f528) at ../../../../src/zc/impl_motif/motifEnvironment.C:1286
#47 0x082b0a5d in MotifEnvironment::wait (this=0x962f528) at ../../../../src/zc/impl_motif/motifEnvironment.C:1297
#48 0x08297bbd in MotifBuild::wait (this=0x962f518) at ../../../../src/zc/impl_motif/motifBuild.C:327
#49 0x081ee882 in InteractiveEnvironment::wait (this=0xbfff9960) at ../../../../src/zc/view_interface/interactiveEnvironment.C:154
#50 0x0806c952 in JobEditor::run (this=0xbfff9960) at ../../../../src/zc/job_edit/jobEdit.C:243
#51 0x0806cd33 in main (argc=2, argv=0xbfff9aa4) at ../../../../src/zc/job_edit/jobEdit.C:325

Another Linux example:

#0 0x00214cf0 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#1 0x002145f3 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#2 0x0021495c in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#3 0x0021527b in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#4 0x002155d5 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#5 0x002140a1 in _XmNewTravGraph () from /usr/X11R6/lib/libXm.so.2
#6 0x0021399a in _XmTraverseAway () from /usr/X11R6/lib/libXm.so.2
#7 0x0021107f in _XmValidateFocus () from /usr/X11R6/lib/libXm.so.2
#8 0x00213108 in _XmPrimitiveUnmap () from /usr/X11R6/lib/libXm.so.2
#9 0x00d66a3a in _XtMatchAtom () from /usr/X11R6/lib/libXt.so.6
#10 0x00d66f78 in _XtMatchAtom () from /usr/X11R6/lib/libXt.so.6
#11 0x00d67573 in _XtTranslateEvent () from /usr/X11R6/lib/libXt.so.6
#12 0x00d3f834 in XtDispatchEventToWidget () from /usr/X11R6/lib/libXt.so.6
#13 0x00d4020d in _XtOnGrabList () from /usr/X11R6/lib/libXt.so.6
#14 0x00d4052f in XtDispatchEvent () from /usr/X11R6/lib/libXt.so.6
#15 0x082b0a22 in MotifEnvironment::m_waitLoop (e=0x8e5a528) at ../../../../src/zc/impl_motif/motifEnvironment.C:1286
#16 0x082b0a5d in MotifEnvironment::wait (this=0x8e5a528) at ../../../../src/zc/impl_motif/motifEnvironment.C:1297
#17 0x08297bbd in MotifBuild::wait (this=0x8e5a518) at ../../../../src/zc/impl_motif/motifBuild.C:327
#18 0x081ee882 in InteractiveEnvironment::wait (this=0xbfffa560) at ../../../../src/zc/view_interface/interactiveEnvironment.C:154
#19 0x0806c952 in JobEditor::run (this=0xbfffa560) at ../../../../src/zc/job_edit/jobEdit.C:243
#20 0x0806cd33 in main (argc=2, argv=0xbfffa6a4) at ../../../../src/zc/job_edit/jobEdit.C:325

Solaris:

(dbx) where
[1] NodeDominates(0x246ea0c, 0x246ddf4, 0x246ea0c, 0xce, 0xff7b, 0x241), at 0xfd602f44
[2] Sort(0x14, 0x1, 0x4, 0x0, 0x246ea0c, 0x248787c), at 0xfd5fc6cc
[3] SortTabGraph(0x0, 0x1, 0xce, 0xffbedab4, 0xffbedab0, 0xce), at 0xfd5fc38c
[4] SortNodeList(0x0, 0x55, 0x246d950, 0xfeccd4, 0xbcb, 0x246cd80), at 0xfd5fc1c0
[5] _XmNewTravGraph(0xfeccd4, 0xfeccd4, 0x1fab7c0, 0x0, 0xfe4b00, 0x0), at 0xfd5fbd40
[6] _XmTraverseAway(0xfeccd4, 0x1fab7c0, 0x1, 0xfeccd4, 0x0, 0x1), at 0xfd6df43c
[7] _XmValidateFocus(0xfecc70, 0x1fab7c0, 0x0, 0xfef28280, 0xfd6df344, 0xfee500), at 0xfd6deb50
[8] HandleActions(0x0, 0xffbee1bc, 0xfece10, 0x1fab7c0, 0x174d89c, 0xfef28278), at 0xfeeef324
[9] HandleSimpleState(0x0, 0xfeed40, 0x0, 0x1, 0x0, 0x1), at 0xfeeee22c
[10] HandleComplexState(0x1fab7f8, 0x0, 0xfe9820, 0xfef22000, 0x1fab7f0, 0xffbedfec), at 0xfeef5edc
[11] _XtTranslateEvent(0xfef28290, 0x1fab7f0, 0xfef22000, 0x1fab7c0, 0x0, 0xa0000), at 0xfeeedd40
[12] XtDispatchEventToWidget(0x0, 0x1, 0x0, 0xffbee1bc, 0x1fab7c0, 0xa0000), at 0xfeeedab0
[13] _XtDefaultDispatcher(0x0, 0x0, 0x12, 0x1fab7c0, 0xfeeecd18, 0x0), at 0xfeeed1a8
[14] XtDispatchEvent(0x0, 0xfeeecff8, 0xfb00c8, 0xfef22000, 0x0, 0x1), at 0xfeeeced0
=>[15] MotifEnvironment::m_waitLoop(e = 0xfad798), line 1283 in "motifEnvironment.C"
[16] MotifEnvironment::wait(this = 0xfad798), line 1294 in "motifEnvironment.C"
[17] MotifBuild::wait(this = 0xfaaae8), line 318 in "motifBuild.C"
[18] InteractiveEnvironment::wait(this = 0xffbee418), line 154 in "interactiveEnvironment.C"
[19] JobEditor::run(this = 0xffbee418), line 243 in "jobEdit.C"
[20] main(argc = 2, argv = 0xffbee524), line 325 in "jobEdit.C"

Any ideas on how to fix or work around this would be gratefully received

Hi,

Fortunately we managed to reproduce this hang and use DBX to dump
input data (the list of nodes to sort) given to Sort function.

Then we copied the code of the Sort function and some functions
it calls (not many) from original OpenMotif 2.2.3 sources to
separate file and made a Visual Studio project from it.

We supplied also a simple function which loads the data acquired
from the hung process on Solaris. In theory, in this "laboratory
conditions", separated from Motif and X, it should also hang
proving that there is some bug in the sorting algorithm. IMO any
sorting algorithm shouldn't go into infinite loop in no circumstances,
regardless of the input data.

The result was as expected -- it hung. Below I include the whole
cpp file we used (it consists of mostly copied & pasted Motif/X code
and the data set). You should be able to compile it on any platform
and it should hang (we tried it on Windows under Visual Studio).

What it proves since no sorting algorithm should hang on any data,
it proves there is some bug in it. Or if there are some hidden assumptions
about the input data in this algorithm, it proves that something is wrong
in one of the functions preceding it on stack (but I'd rather follow
the opinion that no pure sorting algorithm should hang).

I think also it's very helpful resource for Motif developers, since
they can now debug it easily, here is the 100%-reproducible testcase.

(Do Motif developers read this list? If so, we'd be very grateful to
hear what do you think about this?)

Best regards,
PK

#include "stdafx.h"
#include
#include

// -----------------------------------------------------------------------------
/*
[PK] Data as copied from the memory of the hung process. These are
XRectangle components of the XmTraversalNodeRec structure. First
pointers (of type XmTraversalNode) were read (they form an array)
and then pointed elements were examined and rect components extracted.
*/

enum { DATA_SIZE = 57 };

unsigned int data [ 2* DATA_SIZE ] =
{
0x0012021b, 0x044c0037, 0x0017fe29, 0x03200078,
0x0017fe29, 0x04600078, 0x0017fe29, 0x00550096,
0x0017fe29, 0x00d200b4, 0x0017fe29, 0x0460012c,
0x0017fe83, 0x01e0001b, 0x0017feab, 0x03200064,
0x0017feab, 0x04600096, 0x0017fef1, 0x00550096,
0x0017ff05, 0x02a300c8, 0x0017ff19, 0x046000aa,
0x0017ff23, 0x03200006, 0x0017ff4b, 0x04600096,
0x0017ff55, 0x010a001b, 0x0017ff73, 0x010a001b,
0x0017ff91, 0x010a001b, 0x0017ffb9, 0x00550096,
0x0017ffcd, 0x03200078, 0x0017ffeb, 0x04600078,
0x00170013, 0x00ba001b, 0x00170013, 0x018d001b,
0x0017001d, 0x0178001b, 0x00170031, 0x0173001b,
0x0017003b, 0x0178001b, 0x0017004f, 0x03200064,
0x0017006d, 0x04600096, 0x00170081, 0x00550096,
0x0017010d, 0x04600096, 0x00170149, 0x00550096,
0x001701ad, 0x04600096, 0x0017022f, 0x018d001b,
0x0017024d, 0x04600096, 0x0107fe29, 0x00f000b4,
0x016b0013, 0x0366001b, 0x016b022f, 0x0154001b,
0x0017fef1, 0x00550096, 0x0017ff05, 0x02a300c8,
0x0017ff19, 0x046000aa, 0x0017ff19, 0x046000aa,
0x0017ff23, 0x03200006, 0x019dff37, 0x01e0001b,
0x019dff55, 0x02a8001b, 0x019dff73, 0x02a8001b,
0x019dff91, 0x02a8001b, 0x00170013, 0x00ba001b,
0x00170013, 0x018d001b, 0x0017001d, 0x0178001b,
0x016b0013, 0x0366001b, 0x0201ffff, 0x0178001b,
0x0201001d, 0x0178001b, 0x02c9ff05, 0x00fa00c8,
0x032dfe83, 0x01ae001b, 0x032dfea1, 0x01ae001b,
0x032dfedd, 0x01ae001b, 0x034bfe5b, 0x00c800b4,
0x0391ff05, 0x00fa00c8
};

// -----------------------------------------------------------------------------
/*
[PK] Various pieces of Motif/X code copied exactly from the OpenMotif 2.2.3
and X headers sources. Also some adtiional definitions (Boolean, True, False).
*/

typedef unsigned int Cardinal;
typedef int Boolean;
typedef unsigned short Dimension; /* Size in pixels */

typedef short Position; /* Offset from 0 coordinate */
typedef struct { short x, y; unsigned short width, height; } XRectangle;
typedef unsigned char XmDirection;

enum { False = 0, True = 1 };

/*
[PK] Note that Sort and dependencies use only rect member of this struct.
*/

typedef struct _XmAnyNodeRec /* Common */
{
/*unsigned char type ;
XmNavigationType nav_type ;
XmDeferredGraphLink tab_parent ;
Widget widget ;*/
XRectangle rect ;
/*union _XmTraversalNodeRec *next ;
union _XmTraversalNodeRec *prev ;*/
} XmAnyNodeRec, *XmAnyNode ;

typedef union _XmTraversalNodeRec
{
XmAnyNodeRec any ;
} XmTraversalNodeRec, *XmTraversalNode ;

typedef int (*Comparator)(const void *, const void *);

typedef struct
{
XmTraversalNode *items;
XmTraversalNode lead_item;
Cardinal num_items;
Cardinal max_items;
Position min_hint;
Position max_hint;
} XmTraversalRow;

#define XmDIRECTION_IGNORED 0x30

#define XmRIGHT_TO_LEFT_MASK 0x01 /* 0x01 for bc */
#define XmLEFT_TO_RIGHT_MASK 0x02
#define XmHORIZONTAL_MASK 0x03
#define XmTOP_TO_BOTTOM_MASK 0x04
#define XmBOTTOM_TO_TOP_MASK 0x08
#define XmVERTICAL_MASK 0x0c
#define XmPRECEDENCE_HORIZ_MASK 0x40
#define XmPRECEDENCE_VERT_MASK 0x80
#define XmPRECEDENCE_MASK 0xc0

enum {
XmRIGHT_TO_LEFT_TOP_TO_BOTTOM =
XmRIGHT_TO_LEFT_MASK | XmTOP_TO_BOTTOM_MASK | XmPRECEDENCE_HORIZ_MASK,
XmLEFT_TO_RIGHT_TOP_TO_BOTTOM =
XmLEFT_TO_RIGHT_MASK | XmTOP_TO_BOTTOM_MASK | XmPRECEDENCE_HORIZ_MASK,
XmRIGHT_TO_LEFT_BOTTOM_TO_TOP =
XmRIGHT_TO_LEFT_MASK | XmBOTTOM_TO_TOP_MASK | XmPRECEDENCE_HORIZ_MASK,
XmLEFT_TO_RIGHT_BOTTOM_TO_TOP =
XmLEFT_TO_RIGHT_MASK | XmBOTTOM_TO_TOP_MASK | XmPRECEDENCE_HORIZ_MASK,
XmTOP_TO_BOTTOM_RIGHT_TO_LEFT =
XmRIGHT_TO_LEFT_MASK | XmTOP_TO_BOTTOM_MASK | XmPRECEDENCE_VERT_MASK,
XmTOP_TO_BOTTOM_LEFT_TO_RIGHT =
XmLEFT_TO_RIGHT_MASK | XmTOP_TO_BOTTOM_MASK | XmPRECEDENCE_VERT_MASK,
XmBOTTOM_TO_TOP_RIGHT_TO_LEFT =
XmRIGHT_TO_LEFT_MASK | XmBOTTOM_TO_TOP_MASK | XmPRECEDENCE_VERT_MASK,
XmBOTTOM_TO_TOP_LEFT_TO_RIGHT =
XmLEFT_TO_RIGHT_MASK | XmBOTTOM_TO_TOP_MASK | XmPRECEDENCE_VERT_MASK,
XmTOP_TO_BOTTOM =
XmTOP_TO_BOTTOM_MASK | XmHORIZONTAL_MASK | XmPRECEDENCE_MASK,
XmBOTTOM_TO_TOP =
XmBOTTOM_TO_TOP_MASK | XmHORIZONTAL_MASK | XmPRECEDENCE_MASK,
XmRIGHT_TO_LEFT =
XmRIGHT_TO_LEFT_MASK | XmVERTICAL_MASK | XmPRECEDENCE_MASK,
XmLEFT_TO_RIGHT =
XmLEFT_TO_RIGHT_MASK | XmVERTICAL_MASK | XmPRECEDENCE_MASK,
XmDEFAULT_DIRECTION = 0xff
};

#define XtNew(type) ((type *) XtMalloc((unsigned) sizeof(type)))

#define ASSIGN_MAX(a, b) ((a) = ((a) > (b) ? (a) (b)))
#define ASSIGN_MIN(a, b) ((a) = ((a) < (b) ? (a) (b)))

/* Handle compatibility with XmStringDirection */
#define Fixdir(d) (((d) <= 1) ? (~((d)+1)) ((d) | XmDIRECTION_IGNORED))

# define XtMalloc malloc
# define XtRealloc realloc
# define XtFree free

Boolean
XmDirectionMatch(XmDirection d1,
XmDirection d2)
{
d1 = Fixdir(d1);
d2 = Fixdir(d2);
return (((XmDirection)(d1 & d2) == (XmDirection)d1) ||
((XmDirection)(d1 & d2) == (XmDirection)d2));
}

Boolean
XmDirectionMatchPartial(XmDirection d1,
XmDirection d2,
XmDirection dmask)
{
return XmDirectionMatch(d1 & dmask, d2 & dmask);
}

/* Compare nodes horizontally in a Left-to-Right, Top-to-Bottom layout. */
static int
CompareNodesHorizLT(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if (nodeA->any.rect.x != nodeB->any.rect.x)
return (nodeA->any.rect.x < nodeB->any.rect.x) ? -1 1;

if (nodeA->any.rect.y != nodeB->any.rect.y)
return (nodeA->any.rect.y < nodeB->any.rect.y) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

return 0;
}

/* Compare nodes horizontally in a Right-to-Left, Top-to-Bottom layout. */
static int
CompareNodesHorizRT(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if ((nodeA->any.rect.x + nodeA->any.rect.width) !=
(nodeB->any.rect.x + nodeB->any.rect.width))
return ((nodeA->any.rect.x + nodeA->any.rect.width) >
(nodeB->any.rect.x + nodeB->any.rect.width)) ? -1 1;

if (nodeA->any.rect.y != nodeB->any.rect.y)
return (nodeA->any.rect.y < nodeB->any.rect.y) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

return 0;
}

/* Compare nodes horizontally in a Left-to-Right, Bottom-to-Top layout. */
static int
CompareNodesHorizLB(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if (nodeA->any.rect.x != nodeB->any.rect.x)
return (nodeA->any.rect.x < nodeB->any.rect.x) ? -1 1;

if ((nodeA->any.rect.y + nodeA->any.rect.height) !=
(nodeB->any.rect.y + nodeB->any.rect.height))
return ((nodeA->any.rect.y + nodeA->any.rect.height) >
(nodeB->any.rect.y + nodeB->any.rect.height)) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

return 0;
}

/* Compare nodes horizontally in a Right-to-Left, Bottom-to-Top layout. */
static int
CompareNodesHorizRB(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if ((nodeA->any.rect.x + nodeA->any.rect.width) !=
(nodeB->any.rect.x + nodeB->any.rect.width))
return ((nodeA->any.rect.x + nodeA->any.rect.width) >
(nodeB->any.rect.x + nodeB->any.rect.width)) ? -1 1;

if ((nodeA->any.rect.y + nodeA->any.rect.height) !=
(nodeB->any.rect.y + nodeB->any.rect.height))
return ((nodeA->any.rect.y + nodeA->any.rect.height) >
(nodeB->any.rect.y + nodeB->any.rect.height)) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

return 0;
}

/* Compare nodes vertically in a Left-to-Right, Top-to-Bottom layout. */
static int
CompareNodesVertLT(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if (nodeA->any.rect.y != nodeB->any.rect.y)
return (nodeA->any.rect.y < nodeB->any.rect.y) ? -1 1;

if (nodeA->any.rect.x != nodeB->any.rect.x)
return (nodeA->any.rect.x < nodeB->any.rect.x) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

return 0;
}

/* Compare nodes vertically in a Right-to-Left, Top-to-Bottom layout. */
static int
CompareNodesVertRT(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if (nodeA->any.rect.y != nodeB->any.rect.y)
return (nodeA->any.rect.y < nodeB->any.rect.y) ? -1 1;

if ((nodeA->any.rect.x + nodeA->any.rect.width) !=
(nodeB->any.rect.x + nodeB->any.rect.width))
return ((nodeA->any.rect.x + nodeA->any.rect.width) >
(nodeB->any.rect.x + nodeB->any.rect.width)) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

return 0;
}

/* Compare nodes vertically in a Left-to-Right, Bottom-to-Top layout. */
static int
CompareNodesVertLB(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if ((nodeA->any.rect.y + nodeA->any.rect.height) !=
(nodeB->any.rect.y + nodeB->any.rect.height))
return ((nodeA->any.rect.y + nodeA->any.rect.height) >
(nodeB->any.rect.y + nodeB->any.rect.height)) ? -1 1;

if (nodeA->any.rect.x != nodeB->any.rect.x)
return (nodeA->any.rect.x < nodeB->any.rect.x) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

return 0;
}

/* Compare nodes vertically in a Right-to-Left, Bottom-to-Top layout. */
static int
CompareNodesVertRB(const void *A,
const void *B)
{
register const XmTraversalNode nodeA = *((XmTraversalNode *) A);
register const XmTraversalNode nodeB = *((XmTraversalNode *) B);

if ((nodeA->any.rect.y + nodeA->any.rect.height) !=
(nodeB->any.rect.y + nodeB->any.rect.height))
return ((nodeA->any.rect.y + nodeA->any.rect.height) >
(nodeB->any.rect.y + nodeB->any.rect.height)) ? -1 1;

if ((nodeA->any.rect.x + nodeA->any.rect.width) !=
(nodeB->any.rect.x + nodeB->any.rect.width))
return ((nodeA->any.rect.x + nodeA->any.rect.width) >
(nodeB->any.rect.x + nodeB->any.rect.width)) ? -1 1;

if (nodeA->any.rect.width != nodeB->any.rect.width)
return (nodeA->any.rect.width < nodeB->any.rect.width) ? -1 1;

if (nodeA->any.rect.height != nodeB->any.rect.height)
return (nodeA->any.rect.height < nodeB->any.rect.height) ? -1 1;

return 0;
}

static Comparator
HorizNodeComparator(XmDirection layout)
{
if (XmDirectionMatchPartial(layout, XmLEFT_TO_RIGHT, XmHORIZONTAL_MASK))
{
if (XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK))
return CompareNodesHorizLT;
else
return CompareNodesHorizLB;
}
else
{
if (XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK))
return CompareNodesHorizRT;
else
return CompareNodesHorizRB;
}
}

/* Select a vertical comparator for this layout direction. */
static Comparator
VertNodeComparator(XmDirection layout)
{
if (XmDirectionMatchPartial(layout, XmLEFT_TO_RIGHT, XmHORIZONTAL_MASK))
{
if (XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK))
return CompareNodesVertLT;
else
return CompareNodesVertLB;
}
else
{
if (XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK))
return CompareNodesVertRT;
else
return CompareNodesVertRB;
}
}

static Boolean
NodesOverlap(XmTraversalNode nodeA,
XmTraversalNode nodeB,
Boolean horizontal)
{
Dimension Acent, Bcent;

if (horizontal)
{
Acent = nodeA->any.rect.y + ((nodeA->any.rect.height) >> 1);
Bcent = nodeB->any.rect.y + ((nodeB->any.rect.height) >> 1);

if (((nodeA->any.rect.y + nodeA->any.rect.height) < Bcent) &&
(Acent < (Dimension) nodeB->any.rect.y))
return False;
else if (((nodeB->any.rect.y + nodeB->any.rect.height) < Acent) &&
(Bcent < (Dimension) nodeA->any.rect.y))
return False;
}
else
{
Acent = nodeA->any.rect.x + ((nodeA->any.rect.width) >> 1);
Bcent = nodeB->any.rect.x + ((nodeB->any.rect.width) >> 1);

if (((nodeA->any.rect.x + nodeA->any.rect.width) < Bcent) &&
(Acent < (Dimension) nodeB->any.rect.x))
return False;
else if (((nodeB->any.rect.x + nodeB->any.rect.width) < Acent) &&
(Bcent < (Dimension) nodeA->any.rect.x))
return False;
}

return True;
}

static void
TruncateRow(XmTraversalRow *row,
Cardinal length,
XmTraversalNode *free_list,
Cardinal *first_free,
Cardinal max_free,
Boolean horizontal,
XmDirection layout)
{
Cardinal tmp;
XmTraversalNode item;
Comparator compare =
(horizontal ? HorizNodeComparator(layout) VertNodeComparator(layout));

assert(length <= row->num_items);
while (row->num_items > length)
{
/* Select an item to free. */
item = row->items[--(row->num_items)];
free_list[(*first_free)--] = item;
assert(((int)*first_free) >= 0);

/* This can't be the determining item for sorting rows. */
if (item == row->lead_item)
row->lead_item = NULL;

/* Push it back onto the free list in sorted order. */
for (tmp = *first_free + 2; tmp < max_free; tmp++)
{
if (compare (free_list + tmp, &item) < 0)
{
free_list[tmp - 1] = free_list[tmp];
free_list[tmp] = item;
}
else
{
/* The free list was sorted initially, so we're done. */
break;
}
}
}
}

static Boolean
NodeDominates(XmTraversalNode node_1,
XmTraversalNode node_2,
Boolean horizontal,
XmDirection layout)
{
if (horizontal)
{
if (XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK))
return (node_1->any.rect.y < node_2->any.rect.y);
else
return ((node_1->any.rect.y + node_1->any.rect.height) >
(node_2->any.rect.y + node_2->any.rect.height));
}
else
{
if (XmDirectionMatchPartial(layout, XmLEFT_TO_RIGHT, XmHORIZONTAL_MASK))
return (node_1->any.rect.x < node_2->any.rect.x);
else
return ((node_1->any.rect.x + node_1->any.rect.width) >
(node_2->any.rect.x + node_2->any.rect.width));
}
}

static void
AppendToRow(XmTraversalNode item,
XmTraversalRow *row,
Boolean horizontal,
XmDirection layout)
{
Cardinal tmp;

/* Make sure there is enough room in the array. */
assert (row->num_items <= row->max_items);
if (row->num_items == row->max_items)
{
row->max_items += 10;
row->items = (XmTraversalNode *)
XtRealloc((char*)row->items, row->max_items * sizeof(XmTraversalNode));
}

/* Append this item.*/
row->items[row->num_items++] = item;

/* Update cached row information. */
tmp = row->num_items - 1;
if (row->lead_item == NULL)
{
row->lead_item = row->items[0];
tmp = 1;
row->min_hint = 32767; /* Should be MAX_POSITION. */
row->max_hint = -32768; /* Should be MIN_POSITION. */
}
for (; tmp < row->num_items; tmp++)
{
XmTraversalNode node = row->items[tmp];

/* Look for a new dominant item. */
if (NodeDominates(node, row->lead_item, horizontal, layout))
row->lead_item = node;

/* Look for new bounds hints. */
if (horizontal)
{
ASSIGN_MIN(row->min_hint, node->any.rect.y);
ASSIGN_MAX(row->max_hint, node->any.rect.y + node->any.rect.height);
}
else
{
ASSIGN_MIN(row->min_hint, node->any.rect.x);
ASSIGN_MAX(row->max_hint, node->any.rect.x + node->any.rect.width);
}
}
}

static void
Sort(XmTraversalNode *list,
size_t n_mem,
Boolean horizontal,
XmDirection layout)
{
/* This rather involved algorithm is intended to produce a grid-like */
/* traversal order (like the keys on a telephone), but at the same */
/* time use an "intuitive" definition of which nodes form a row. */
XmTraversalRow *rows = NULL;
int row;
int num_rows = 0;
Cardinal first_free = (Cardinal) -1;

/* Take the easy out in degenerate cases. */
if (n_mem <= 1)
return;

/* First sort everything based simply on the absolute coordinates. */
if (horizontal)
qsort(list, n_mem, sizeof(XmTraversalNode), HorizNodeComparator(layout));
else
qsort(list, n_mem, sizeof(XmTraversalNode), VertNodeComparator(layout));

/* Assign each free node to a row. */
while (++first_free < n_mem)
{
XmTraversalNode node = list[first_free];
Boolean new_row = True;
Boolean done = False;
Boolean might_overlap = False ;
Cardinal row_len = 0;

row = 0;
while (!done && (row < num_rows))
{
/* Extract some row-specific information. */
if (new_row)
{
new_row = False;
row_len = rows[row].num_items;

if (horizontal)
{
might_overlap = (rows[row].max_hint > node->any.rect.y) &&
(rows[row].min_hint < (node->any.rect.y +
node->any.rect.height));
}
else
{
might_overlap = (rows[row].max_hint > node->any.rect.x) &&
(rows[row].min_hint < (node->any.rect.x +
node->any.rect.width));
}
}

/* Append this node if it overlaps the end of the row. */
if (NodesOverlap(node, rows[row].items[row_len - 1], horizontal))
{
TruncateRow(rows + row, row_len, list, &first_free, n_mem,
horizontal, layout);
AppendToRow(node, rows + row, horizontal, layout);
done = True;
}

/* Else if this node is dominant backtrack and try again. */
else if ((row_len > 1) && might_overlap &&
NodeDominates(node, rows[row].items[rows[row].num_items-1],
horizontal, layout))
row_len--;

/* Try the next row. */
else
{
row++;
new_row = True;
}
}

/* Create a new row if necessary. */
if (!done)
{
XmTraversalRow new_data;
Cardinal new_index = num_rows;

new_data.items = XtNew(XmTraversalNode);
new_data.items[0] = node;
new_data.lead_item = node;
new_data.num_items = 1;
new_data.max_items = 1;
if (horizontal)
{
new_data.min_hint = node->any.rect.y;
new_data.max_hint = node->any.rect.y + node->any.rect.height;
}
else
{
new_data.min_hint = node->any.rect.x;
new_data.max_hint = node->any.rect.x + node->any.rect.width;
}

num_rows++;
rows = (XmTraversalRow *)
XtRealloc((char*) rows, num_rows * sizeof(XmTraversalRow));

/* Keep rows sorted by initial element. */
for (row = new_index; row > 0; row--)
{
if (NodeDominates(node, rows[row-1].lead_item, horizontal,layout))
{
memcpy(rows + row, rows + row - 1, sizeof(XmTraversalRow));
new_index--;
}
else
break;
}

memcpy(rows + new_index, &new_data, sizeof(XmTraversalRow));
}
}
assert(first_free == n_mem);

/* Copy nodes out of rows and into the final order. */
first_free = 0;
if ((horizontal &&
XmDirectionMatchPartial(layout, XmLEFT_TO_RIGHT, XmHORIZONTAL_MASK)) ||
(!horizontal &&
XmDirectionMatchPartial(layout, XmTOP_TO_BOTTOM, XmVERTICAL_MASK)))
{
/* Nodes appear in the desired order. */
for (row = 0; row < num_rows; row++)
{
assert(rows[row].num_items && rows[row].items);
memcpy(list + first_free, rows[row].items,
sizeof(XmTraversalNode) * rows[row].num_items);
first_free += rows[row].num_items;
XtFree((char*) rows[row].items);
}
}
else
{
/* Nodes are in exactly the wrong order, but the head is right. */
int col;
for (row = num_rows - 1; row >= 0; row--)
{
assert(rows[row].num_items && rows[row].items);
for (col = rows[row].num_items - 1; col >= 0; col--)
list[++first_free % n_mem] = rows[row].items[col];
XtFree((char*) rows[row].items);
}
}
assert(first_free == n_mem);
XtFree((char*) rows);
}

// -----------------------------------------------------------------------------
/*
[PK] Our test circuit - simple function which loads the data and forms
XmTraversalNode array from it, then calls the Sort function.
*/

int main(int argc, char** argv )
{
XmTraversalNodeRec nodes [ DATA_SIZE ];

for ( unsigned int i = 0; i != DATA_SIZE; ++i )
{
unsigned int v1 = data [ 2*i ];
unsigned int v2 = data [ 2*i + 1 ];

union
{
short vsigned;
unsigned short vunsigned;
};

vunsigned = static_cast< unsigned short >( v1 >> 16 );
nodes [ i ].any.rect.x = vsigned;
vunsigned = static_cast< unsigned short >( v1 & 65535 );
nodes [ i ].any.rect.y = vsigned;
nodes [ i ].any.rect.width = static_cast< unsigned short >( v2 >> 16 );
nodes [ i ].any.rect.height = static_cast< unsigned short >( v2 & 65535 );

/*
Now we have a very specific set of coordinates which makes
Sort go nuts.
*/

stdcout
<< nodes [ i ].any.rect.x << ", "
<< nodes [ i ].any.rect.y << ", "
<< nodes [ i ].any.rect.width << ", "
<< nodes [ i ].any.rect.height << stdendl;
}

XmTraversalNode pnodes [ DATA_SIZE ];

for ( unsigned int i = 0; i != DATA_SIZE; ++i )
pnodes [ i ] = & nodes [ i ];

/*
Sort requires array of pointers.

The call below causes program to hang.
*/
Sort ( pnodes, DATA_SIZE, 1, ( XmDirection ) 0xCE );
}

Thanks,

But your tracebacks and mine show the program hanging in places where it can not possibly hang. For example

[1] HorizNodeComparator(0xfed24c60, 0xc7, 0x173448, 0xfecebf20, 0xc7, 0xfee98000), at 0xfed24c08
[2] TruncateRow(0x22b4ef4, 0x3, 0xffbfdcfc, 0xffbfdc8c, 0x18, 0x1000000), at 0xfed089d8
[3] Sort(0xffbfdcfc, 0x10, 0x1, 0x0, 0x18, 0x3), at 0xfed015fc

The code I have shows no loops of any sort in HorizNodeComparator, so how can it hang?

My tracebacks show it sometimes blocking in Sort, but sometimes elsewhere. Also, single stepping in the blocked loop shows it in places it can not possibly be, such as "XmCreateArrowButton" called from "_XmNewTravGraph". In my source XmCreateArrowButton isn't called from anywhere. The only common factor I have is _XmNewTravGraph. All this points to something horrible happening to the stack before it even gets there, but that is strange because the problem is so consistant and exists on multiple versions with the same symptoms.

It seems it hangs in the outer 'while' loop in Sort itself

while (++first_free < n_mem)

On our example that we tested on Visual Studio first_free goes from 41 to 49 (as far I can remember), then it cycles back to 41. TruncateRow and HorizNodeComparator are called inside this loop infinite number of times.

Regarding tracebacks from John, the Linux ones differ from the Solaris one (as there is only _XmNewTravGraph), It might be a different problem. On the other hand, the Solaris one is identical to ours and I'm sure that this is the same problem.

Regards,
PK

This may or may not be related to the original problem posted, but for what it is worth I will record how I have solved a similar problem in our code.

We use some ancient layout code based on a shareware custom MLayoutWidget. This is laying out thousands of parameters in an Explorer-like pane. For efficiency most of the containers are Gadgets rather than Widgets and toggling between nodes was achieved by managing and unmanaging containers.

It seems that under certain circumstance mouse events in this window caused some sort of internal memory problem resulting in miscellaneous event loop hangs later on. Maybe the window coordinates were getting scrambled into an unsortable state?

After some investigation, I changed our code to force the main containers to be Widgets rather than Gadgets and the problem miraculously disappeared!

Don't know if this is of any help or what the real underlying problem was, but at least my users are up and running again.

Hello,

Possible fix for this problem is to change:
NodeDominates(node, rows[row].items[rows[row].num_items-1],horizontal, layout));
to
NodeDominates(node, rows[row].items[row_len-1],horizontal, layout));
in sample code provided by Przemek Kuczmierczyk.

Original code will decrement row_len up to next overlap. Patched version will check if node dominates for every pair of nodes compared.
But this is very questionable solution. I will really appreciate your thoughts on that.

Thanks.