struct/tree/tn.c

/* struct::tree - critcl - layer 1 declarations
 * (b) Node operations.
 */

#include <tn.h>
#include <util.h>

/* .................................................. */

static void extend_children  (TNPtr n);
static int  fill_descendants (TNPtr n, int lc, Tcl_Obj** lv, int at);

/* .................................................. */

TNPtr
tn_new (TPtr t, CONST char* name)
{
    TNPtr n = ALLOC (TN);
    int	  new;

    n->name = Tcl_NewStringObj(name, -1);
    Tcl_IncrRefCount (n->name);
    tn_shimmer (n->name, n);

    if (Tcl_FindHashEntry (&t->node, name) != NULL) {
	Tcl_Panic ("struct::tree(c) tn_new - tried to use duplicate name for new node");
    }

    n->he = Tcl_CreateHashEntry(&t->node, name, &new);
    Tcl_SetHashValue (n->he, (ClientData) n);

    n->tree     = t;
    n->nextleaf = NULL;
    n->prevleaf = NULL;
    n->nextnode = NULL;
    n->prevnode = NULL;

    tn_node (n);
    tn_leaf (n);

    n->parent	   = NULL;
    n->child	   = NULL;
    n->maxchildren = 0;
    n->nchildren   = 0;
    n->left	   = NULL;
    n->right	   = NULL;
    n->attr	   = NULL;

    n->index	   = -1;
    n->depth	   = -1;
    n->height	   = -1;
    n->desc	   = -1;

    return n;
}

void
tn_delete (TNPtr n)
{
    T* t = n->tree;

    /* We assume that the node either has no parent or siblings anymore,
     * or that their presence does not matter. The node may still have
     * children. They are deleted recursively. That is the situation
     * where the parent/sibling information does not matter anymore, and
     * can be ignored.
     */

    tn_notleaf (n);
    tn_notnode (n);

    Tcl_DecrRefCount	(n->name); n->name = NULL;
    Tcl_DeleteHashEntry (n->he);   n->he   = NULL;

    if (n->child) {
	int i;

	for (i = 0; i < n->nchildren; i++) {
	    ASSERT_BOUNDS (i, n->nchildren);

	    tn_delete (n->child [i]);
	    n->child [i] = NULL;
	}
	ckfree ((char*) n->child);

	n->child       = NULL;
	n->nchildren   = 0;
	n->maxchildren = 0;
    }

    if (n->attr) {
	Tcl_HashSearch	hs;
	Tcl_HashEntry*	he;

	for(he = Tcl_FirstHashEntry(n->attr, &hs);
	    he != NULL;
	    he = Tcl_NextHashEntry(&hs)) {
	    Tcl_DecrRefCount ((Tcl_Obj*) Tcl_GetHashValue(he));
	}
	Tcl_DeleteHashTable(n->attr);
	ckfree ((char*) n->attr);
	n->attr = NULL;
    }

    ckfree ((char*) n);
}

/* .................................................. */

void
tn_node (TNPtr n)
{
    TPtr  t	= n->tree;
    TNPtr first = t->nodes;

    t->nnodes ++;

    n->nextnode = first;
    n->prevnode = NULL;
    t->nodes	= n;

    if (!first) return;
    first->prevnode = n;
}

void
tn_notnode (TNPtr n)
{
    T* t = n->tree;

    if ((t->nodes == n) || n->prevnode || n->nextnode) {
	if (t->nodes == n) {
	    t->nodes = n->nextnode;
	}
	if (n->prevnode) {
	    n->prevnode->nextnode = n->nextnode;
	}
	if (n->nextnode) {
	    n->nextnode->prevnode = n->prevnode;
	}
	n->prevnode = NULL;
	n->nextnode = NULL;
	t->nnodes --;
    }
}

void
tn_leaf (TNPtr n)
{
    TPtr  t	= n->tree;
    TNPtr first = t->leaves;

    if ((t->leaves == n) || n->prevleaf || n->nextleaf) {
	/* The node is already a leaf */
	return;
    }

    /* Now make the non-leaf it a leaf */

    t->nleaves ++;

    n->nextleaf = first;
    n->prevleaf = NULL;
    t->leaves	= n;

    if (!first) return;
    first->prevleaf = n;
}

void
tn_notleaf (TNPtr n)
{
    T* t = n->tree;

    if ((t->leaves == n) || n->prevleaf || n->nextleaf) {
	if (t->leaves == n) {
	    t->leaves = n->nextleaf;
	}
	if (n->prevleaf) {
	    n->prevleaf->nextleaf = n->nextleaf;
	}
	if (n->nextleaf) {
	    n->nextleaf->prevleaf = n->prevleaf;
	}
	n->prevleaf = NULL;
	n->nextleaf = NULL;
	t->nleaves --;
    }
}

/* .................................................. */

void
tn_structure (TNPtr n, int depth)
{
    n->depth = depth;
    n->desc  = n->nchildren; /* #direct children */

    depth ++;

    if (n->nchildren) {
	int i, maxh, h;

	for (i = 0, maxh = -1;
	     i < n->nchildren;
	     i++) {
	    ASSERT_BOUNDS (i, n->nchildren);

	    tn_structure (n->child [i], depth);

	    h = n->child [i]->height;

	    if (h > maxh) {
		maxh = h;
	    }
	}

	n->height = maxh + 1;
    } else {
	n->height = 0;
    }

    /* Extend parent with our descendants. Do not count
     * ourselves. This is already done in the parent through
     * the 'direct children' clause above at the beginning
     * of the function.
     */

    if (n->parent) {
	n->parent->desc += n->desc;
    }
}

/* .................................................. */

void
tn_detach (TNPtr n)
{
    /* Detaches the node from the tree by removing it from its parent
     * node. The sibling relationships are squashed as well, and the
     * index information for all right siblings is adjusted. The node
     * does retain its children. After this function is called the node
     * and its children are ready for tn_delete'. Or reinsertion in a
     * different place.
   */

    TNPtr p = n->parent;

    if (p->nchildren == 1) {
	/* This node is the last node in its parent. We can release the
	 * whole array of children now, and declare the parent to be a
	 * leaf again. There is no need to touch the siblings references,
	 * we know that they are NULL.
	 */

	ckfree ((char*) p->child);
	p->child       = NULL;
	p->maxchildren = 0;
	p->nchildren   = 0;

	tn_leaf (p);

    } else {
	/* The node is somewhere in the array of children of its
     * parent. We know the exact location, through 'index'. All
     * siblings to the right are moved down one slot, and their index
     * is adjusted in the same way. This is an O(n)
     * operation. Afterward we adjust the left/right references of the
     * node's siblings, if there are any, and reset the node's sibling
     * references as well.
     */

	int i;
	for (i = n->index; i < (p->nchildren-1); i++) {

	    ASSERT_BOUNDS (i,	p->nchildren);
	    ASSERT_BOUNDS (i+1, p->nchildren);

	    p->child [i] = p->child [i+1];
	    p->child [i]->index --;
	}
	p->nchildren --;
	/* Note regarding the decrement: As the node was _not_ the last
	 * child we know that the condition 'nchildren > 0' still holds, and
	 * that there is no need to free the 'child' array.
     */

	if (n->left) {
	    n->left->right = n->right;
	}
	if (n->right) {
	    n->right->left = n->left;
	}

	n->left	  = NULL;
	n->right  = NULL;
    }

    n->parent = NULL;
    n->tree->structure = 0;
}

TNPtr*
tn_detachmany (TNPtr n, int len)
{
    /* Detaches the node n and its 'len -1' right siblings from the tree
     * by removing them from their parent node. In toto 'len' nodes are
     * removed. The sibling relationships are squashed as well, and the
     * index information for all right siblings is adjusted. The nodes
     * retain their children. After this function is called thes node
     * and their children are ready for tn_delete'. Or reinsertion in a
     * different place.
   *
   * The operation fails with a panic if there are less children we
   * can cut than requested. It also panics when trying to cut
   * nothing.
   *
   * Note: This function does not reset the parent reference in the
   * cut nodes.
   */

    TNPtr* ch;
    TNPtr  p   = n->parent;
    int	   at  = n->index;
    int	   end = at + len;

    ASSERT (end <= p->nchildren, "tn_detachmany - tried to cut too many children");
    ASSERT (len > 0,		 "tn_detachmany - tried to cut nothing");

    if ((at == 0) && (end == p->nchildren)) {
	/* All children are taken. There is no need to copy anything, we
	 * can use the whole array, and reset the other information in the
	 * parent. Note that the condition above implies 'at == 0'. The
	 * parent node becomes a leaf again.
	 */

	ch = p->child;

	p->child       = NULL;
	p->maxchildren = 0;
	p->nchildren   = 0;

	tn_leaf (p);

    } else {
	/* Copies the cut nodes into a result array. Shifts the right
     * siblings down, if there are any.
     */

	int i, k;

	ch = NALLOC (len, TNPtr);

    /* Examples. We always have nchildren = 10.
     *
     * _______________________________
     * at  = 2, len = 3.
     *
     * 01 234 56789 i = 0, k = 2
     *	  012	    i = 3, k = 5
     *
     * 01 234 56789 i = 2, k = 5
     * 01 567 89    i = 7, k = 10
     *
     * _______________________________
     * at  = 7, len = 3.
     *
     * 0123456 789 i = 0, k = 7
     *	       012 i = 3, k = 10
     *
     * 0123456 789 i = 7, k = 10
     * 0123456	   nothing
     *
     * _______________________________
     * at  = 6, len = 3.
     *
     * 012345 678 9 i = 0, k = 6
     *	      012   i = 3, k = 9
     *
     * 012345 678 9 i = 6, k = 9
     * 012345 9	    i = 7, k = 10
     *
     * _______________________________
     * at  = 6, len = 1.
     *
     * 012345 6 789 i = 0, k = 6
     *	      0	    i = 1, k = 7
     *
     * 012345 6 789 i = 6, k = 7
     * 012345 7 89  i = 9, k = 10
     */

	for (i = 0, k = at; i < len; i++, k++) {

	    ASSERT_BOUNDS (k, p->nchildren);
	    ASSERT_BOUNDS (i, len);

	    ch [i] = p->child [k];
	}

	for (i = at, k = end; k < p->nchildren; i++, k++) {

	    ASSERT_BOUNDS (k, p->nchildren);
	    ASSERT_BOUNDS (i, p->nchildren);

	    p->child [i] = p->child [k];
	    p->child [i]->index -= len;
	}

	p->nchildren -= len;

	if (ch [0]->left) {
	    ch [0]->left->right = ch [len-1]->right;
	}
	if (ch [len-1]->right) {
	    ch [len-1]->right->left = ch [0]->left;
	}

	ch [0]->left	  = NULL;
	ch [len-1]->right = NULL;
    }

    n->tree->structure = 0;
    return ch;
}

TNPtr*
tn_detachchildren (TNPtr n, int* nc)
{
    TNPtr* children = n->child;

    *nc = n->nchildren;

    n->child	   = NULL;
    n->maxchildren = 0;
    n->nchildren   = 0;

    tn_leaf (n);
    return children;
}

/* .................................................. */

void
tn_append (TNPtr p, TNPtr n)
{
    /* Appending is O(1) */

    /* The node chosen as parent cannot be a leaf (anymore) */

    int at = p->nchildren;

    tn_notleaf (p);

  /* Allocate/Extend child array as needed */

    p->nchildren ++;
    extend_children (p);

  /* Link the node into the parent and to its left sibling, if
   * any. This overwrites any existing relationships. Make sure
   * that the node n is either new or was cut before.
   */

    ASSERT_BOUNDS (at, p->nchildren);

    p->child [at] = n;

    n->parent = p;
    n->index  = at;
    n->right  = NULL;

    if (at > 0) {
	TNPtr sib;

	ASSERT_BOUNDS (at-1, p->nchildren);

	sib = p->child [at-1];
	n->left	   = sib;
	sib->right = n;
    }

    p->tree->structure = 0;
}

void
tn_appendmany (TNPtr p, int nc, TNPtr* nv)
{
    int i;

    /* Appending is O(1) */

    /* The node chosen as parent cannot be a leaf (anymore) */

    int at = p->nchildren;

    tn_notleaf (p);

    /* Allocate/Extend child array as needed */

    p->nchildren += nc;
    extend_children (p);

    /* Link the nodes into the parent and to their left siblings, if
     * any. This overwrites any existing relationships. Make sure that
     * the nodes are either new or were cut before.
     */

    for (i = 0; i < nc; i++, at++) {

	ASSERT_BOUNDS (at, p->nchildren);
	ASSERT_BOUNDS (i, nc);

	p->child [at] = nv [i];

	nv [i]->parent = p;
	nv [i]->index  = at;
	nv [i]->right  = NULL;

	if (at > 0) {
	    TNPtr sib;

	    ASSERT_BOUNDS (at, p->nchildren);

	    sib = p->child [at-1];
	    nv [i]->left = sib;
	    sib->right	 = nv [i];
	}
    }

    p->tree->structure = 0;
}

/* .................................................. */

void
tn_insert (TNPtr p, int at, TNPtr n)
{
    int i, k;

    if (at >= p->nchildren) {
	tn_append (p, n);
	return;
    }

    /* Insertion at beginning, or somewhere in the middle */

    if (at < 0) {
	at = 0;
    }

    /* The node chosen as parent cannot be a leaf */
    /* anymore */

    tn_notleaf (p);

    /* Allocate/Extend child array as needed */

    p->nchildren ++;
    extend_children (p);

    /* Link the node into the parent and to its left and right siblings,
     * if any. This overwrites any existing relationships. Make sure
     * that the node n is either new or was cut before.
     *
     * Shift all nodes at 'at' and to the right one slot up.
     * Note that 'nchildren' is incremented already.
     */

    for (i = p->nchildren-1, k = i-1; i > at; i--, k--) {

	ASSERT_BOUNDS (i, p->nchildren);
	ASSERT_BOUNDS (k, p->nchildren);

	p->child [i] = p->child [k];
	p->child [i]->index ++;
    }

    p->child [at] = n;

    n->parent = p;
    n->index  = at;

    /* We have to have a right sibling, otherwise it would have been
     * appending. We may have a left sibling.
     */

    ASSERT_BOUNDS (at+1, p->nchildren);

    n->right = p->child [at+1];
    p->child [at+1]->left = n;

    if (at == 0) {
	n->left = NULL;
    } else {
	ASSERT_BOUNDS (at-1, p->nchildren);

	n->left	       = p->child [at-1];
	p->child [at-1]->right = n;
    }

    p->tree->structure = 0;
}

void
tn_insertmany (TNPtr p, int at, int nc, TNPtr* nv)
{
    int i, k;
    if (at >= p->nchildren) {
	tn_appendmany (p, nc, nv);
	return;
    }

    if (at < 0) {
	at = 0;
    }

    /* The node chosen as parent cannot be a leaf */
    /* anymore */

    tn_notleaf (p);

    /* Allocate/Extend child array as needed */

    p->nchildren += nc;
    extend_children (p);

    /* Link the node into the parent and to its left and right siblings,
     * if any. This overwrites any existing relationships. Make sure
     * that the node n is either new or was cut before.
     *
     * Shift all nodes at 'at' and to the right one slot up.
     * Note that 'nchildren' is incremented already.
     */

    for (i = p->nchildren-1, k = i-nc; k >= at; i--, k--) {

	ASSERT_BOUNDS (i, p->nchildren);
	ASSERT_BOUNDS (k, p->nchildren);

	p->child [i] = p->child [k];
	p->child [i]->index += nc;
    }

    for (i = 0, k = at; i < nc; i++, k++) {

	ASSERT_BOUNDS (i, nc);
	ASSERT_BOUNDS (k, p->nchildren);

	nv [i]->parent = p;
	nv [i]->index  = k;
	p->child [k]   = nv [i];
    }

    for (i = 0, k = at; i < nc; i++, k++) {
	if (k > 0) {
	    ASSERT_BOUNDS (k,	p->nchildren);
	    ASSERT_BOUNDS (k-1, p->nchildren);

	    p->child [k]->left	  = p->child [k-1];
	    p->child [k-1]->right = p->child [k];
	}

	if (k < (p->nchildren-1)) {
	    ASSERT_BOUNDS (k,	p->nchildren);
	    ASSERT_BOUNDS (k+1, p->nchildren);

	    p->child [k]->right	 = p->child [k+1];
	    p->child [k+1]->left = p->child [k];
	}
    }

    p->tree->structure = 0;
}

/* .................................................. */

void
tn_cut (TNPtr n)
{
    TNPtr p  = n->parent; /* Remember the location of n in its */
    int at = n->index;	/* parent, this is the point there its
			 * children are re-inserted */
    int	 nc;
    TNPtr* nv;

    nv = tn_detachchildren (n, &nc);
    tn_detach (n);

    tn_insertmany (p, at, nc, nv);
    ckfree ((char*) nv);

    tn_delete (n);
}

TNPtr
tn_dup (TPtr dst, TNPtr src)
{
    TNPtr dstn;

    dstn = tn_new (dst, Tcl_GetString (src->name));

    if (src->attr) {
	int i, new;
	Tcl_HashSearch hs;
	Tcl_HashEntry* he;
	Tcl_HashEntry* dhe;
	CONST char*    key;
	Tcl_Obj*       val;

	dstn->attr = ALLOC (Tcl_HashTable);
	Tcl_InitHashTable(dstn->attr, TCL_STRING_KEYS);

	for(i = 0, he = Tcl_FirstHashEntry(src->attr, &hs);
	    he != NULL;
	    he = Tcl_NextHashEntry(&hs), i++) {

	    key = Tcl_GetHashKey (src->attr, he);
	    val = (Tcl_Obj*) Tcl_GetHashValue(he);

	    dhe = Tcl_CreateHashEntry(dstn->attr, key, &new);

	    Tcl_IncrRefCount (val);
	    Tcl_SetHashValue (dhe, (ClientData) val);
	}
    }

    if (src->nchildren) {
	int i;

	dstn->child	  = NALLOC (src->nchildren, TNPtr);
	dstn->maxchildren = src->nchildren;
	dstn->nchildren	  = 0;

	for (i = 0; i < src->nchildren; i++) {

	    ASSERT_BOUNDS (i, src->nchildren);

	    tn_append (dstn,
		       tn_dup (dst, src->child [i]));
	}
    }

    return dstn;
}

/* .................................................. */

void
tn_set_attr (TNPtr n, Tcl_Interp* interp, Tcl_Obj* dict)
{
    Tcl_HashEntry* he;
    CONST char*	   key;
    Tcl_Obj*	   val;
    int		   new, i;
    int		   listc;
    Tcl_Obj**	   listv;

    if (Tcl_ListObjGetElements (interp, dict, &listc, &listv) != TCL_OK) {
	Tcl_Panic ("Malformed nodes attributes, snuck through validation of serialization.");
    }

    if (!listc) {
	return;
    }

    tn_extend_attr (n);

    for (i = 0; i < listc; i+= 2) {

	ASSERT_BOUNDS (i,   listc);
	ASSERT_BOUNDS (i+1, listc);

	key = Tcl_GetString (listv [i]);
	val = listv [i+1];

	he = Tcl_CreateHashEntry(n->attr, key, &new);

	Tcl_IncrRefCount (val);
	Tcl_SetHashValue (he, (ClientData) val);
    }
}

/* .................................................. */

void
tn_extend_attr (TNPtr n)
{
    if (n->attr != NULL) {
	return;
    }

    n->attr = ALLOC (Tcl_HashTable);
    Tcl_InitHashTable(n->attr, TCL_STRING_KEYS);
}

/* .................................................. */

int
tn_depth (TNPtr n)
{
    if (!n->tree->structure) {
	t_structure (n->tree);
    }
    return n->depth;
}

int
tn_height (TNPtr n)
{
    if (!n->tree->structure) {
	t_structure (n->tree);
    }
    return n->height;
}

int
tn_ndescendants (TNPtr n)
{
    if (n == n->tree->root) {
	/* For the root we do not need to know the structure data of the
	 * tree to determine the number of descendants. It is the number
	 * of nodes minus one, i.e. all nodes except the root.
	 */

	return n->tree->nnodes - 1;

    } else if (!n->nchildren) {
	/* If the node has no direct children we know there are no
	 * descendants as well
	 */

	return 0;

    } else if (!n->tree->structure) {
	t_structure (n->tree);
    }

    return n->desc;
}

Tcl_Obj**
tn_getdescendants (TNPtr n, int* nc)
{
    int	      end;
    int	      lc = tn_ndescendants (n);
    Tcl_Obj** lv;

    *nc = lc;

    if (lc == 0) {
	return NULL;
    }

    lv	= NALLOC (lc, Tcl_Obj*);
    end = fill_descendants (n, lc, lv, 0);

    ASSERT (end == lc, "Bad list of descendants");
    return lv;
}

Tcl_Obj**
tn_getchildren (TNPtr n, int* nc)
{
    if (!n->nchildren) {
	*nc = 0;
	return NULL;
    } else {
	int	  i;
	Tcl_Obj** lv;

	*nc = n->nchildren;
	lv  = NALLOC (n->nchildren, Tcl_Obj*);

	for (i = 0; i < n->nchildren; i++) {

	    ASSERT_BOUNDS (i, n->nchildren);

	    lv [i] = n->child [i]->name;
	}

	return lv;
    }
}

int
tn_filternodes (int* nc,   Tcl_Obj** nv,
		int  cmdc, Tcl_Obj** cmdv,
		Tcl_Obj* tree, Tcl_Interp* interp)
{
    int i;
    int	      ec;
    Tcl_Obj** ev;

    if (cmdc && (*nc > 0)) {
	/* Run the filter command over all nodes in the list.
	 * Keep only the nodes passing the filter in the list.
	 */

	int	  lc = *nc;

	int src, dst, res, flag;

	/* Set up the command vector for the callback.
	 * Two placeholders for tree and node arguments.
	 */

	ec = cmdc + 2;
	ev = NALLOC (ec, Tcl_Obj*);

	for (i = 0; i < cmdc; i++) {
	    ASSERT_BOUNDS (i, ec);

	    ev [i] = cmdv [i];
	    Tcl_IncrRefCount (ev [i]);
	}
	ASSERT_BOUNDS (cmdc, ec);

	ev [cmdc] = tree; /* Tree */
	Tcl_IncrRefCount (ev [cmdc]);

	/* Run the callback on each element of the list */

	for (src = 0, dst = 0;
	     src < lc;
	     src++) {

	    /* Fill the placeholders */

	    ASSERT_BOUNDS (cmdc+1, ec);
	    ASSERT_BOUNDS (src, lc);

	    ev [cmdc+1] = nv [src]; /* Node */

	    /* Run the callback */

	    Tcl_IncrRefCount (ev [cmdc+1]);

	    res = Tcl_EvalObjv (interp, ec, ev, 0);

	    Tcl_DecrRefCount (ev [cmdc+1]);

	    /* Process the result */

	    if (res != TCL_OK) {
		goto abort;
	    }

	    if (Tcl_GetBooleanFromObj (interp,
				       Tcl_GetObjResult (interp),
				       &flag) != TCL_OK) {
		goto abort;
	    }

	    /* Result is valid, use this decide retain/write over */

	    if (!flag)
		continue;

	    ASSERT_BOUNDS (dst, lc);
	    ASSERT_BOUNDS (src, lc);

	    nv [dst] = nv [src];
	    dst++;
	}

	/* Cleanup state */

	Tcl_ResetResult (interp);

	for (i = 0; i < cmdc; i++) {
	    ASSERT_BOUNDS (i, ec);
	    Tcl_DecrRefCount (ev [i]);
	}
	ASSERT_BOUNDS (cmdc, ec);
	Tcl_DecrRefCount (ev [cmdc]); /* Tree */

	ckfree ((char*) ev);

	*nc = dst;
    }

    return TCL_OK;

 abort:
    /* We do not reset the interp result. It either contains
     * the non-boolean result, or the error message
     */

    for (i = 0; i < cmdc; i++) {
	ASSERT_BOUNDS (i, ec);
	Tcl_DecrRefCount (ev [i]);
    }
    ASSERT_BOUNDS (cmdc, ec);
    Tcl_DecrRefCount (ev [cmdc]); /* Tree */

    ckfree ((char*) ev);
    return TCL_ERROR;
}

/* .................................................. */

int
tn_isancestorof (TNPtr na, TNPtr nb)
{
    /* True <=> a is ancestor of b */

    for (nb = nb->parent; nb != NULL; ) {
	if (na == nb) {
	    return 1;
	}
	nb = nb->parent;
    }

    return 0;
}

/* .................................................. */

Tcl_Obj*
tn_get_attr (TNPtr tdn, Tcl_Obj* empty)
{
    int		   i;
    Tcl_Obj*	   res;
    int		   listc;
    Tcl_Obj**	   listv;
    Tcl_HashSearch hs;
    Tcl_HashEntry* he;
    CONST char*	   key;

    if ((tdn->attr == NULL) || (tdn->attr->numEntries == 0)) {
	return empty;
    }

    listc = 2 * tdn->attr->numEntries;
    listv = NALLOC (listc, Tcl_Obj*);

    for(i = 0, he = Tcl_FirstHashEntry(tdn->attr, &hs);
	he != NULL;
	he = Tcl_NextHashEntry(&hs)) {

	key = Tcl_GetHashKey (tdn->attr, he);

	ASSERT_BOUNDS (i,   listc);
	ASSERT_BOUNDS (i+1, listc);

	listv [i] = Tcl_NewStringObj (key, -1);	     i++;
	listv [i] = (Tcl_Obj*) Tcl_GetHashValue(he); i++;
    }

    res = Tcl_NewListObj (listc, listv);
    ckfree ((char*) listv);
    return res;
}

int
tn_serialize (TNPtr tdn, int listc, Tcl_Obj** listv, int at, int parent, Tcl_Obj* empty)
{
    int self = at;

    ASSERT_BOUNDS (at+0, listc);
    ASSERT_BOUNDS (at+1, listc);
    ASSERT_BOUNDS (at+2, listc);

    listv [at++] = tdn->name;
    listv [at++] = (parent < 0 ? empty : Tcl_NewIntObj (parent));
    listv [at++] = tn_get_attr (tdn, empty);

    if (tdn->nchildren) {
	int i;
	for (i = 0; i < tdn->nchildren; i++) {
	    at = tn_serialize (tdn->child [i], listc, listv, at, self, empty);
	}
    }

    return at;
}

/* .................................................. */static int
fill_descendants (TNPtr n, int lc, Tcl_Obj** lv, int at)
{
    /* The descendants of the root are simply all nodes except the root
     * itself. That is easy to retrieve.
   */

    if (n == n->tree->root) {
	TNPtr iter;

	for (iter = n->tree->nodes;
	     iter != NULL;
	     iter = iter->nextnode) {

	    /* Skip the root node, it is not a descendant! */
	    if (iter == n) continue;

	    ASSERT_BOUNDS (at, lc);

	    lv [at] = iter->name;
	    at++;
	}
    } else if (n->child) {
	int   i;
	TNPtr c;

	for (i = 0; i < n->nchildren; i++) {
	    c = n->child [i];

	    ASSERT_BOUNDS (at, lc);
	    ASSERT_BOUNDS (i,  n->nchildren);

	    lv [at] = c->name;
	    at++;

	    at = fill_descendants (c, lc, lv, at);
	}
    }

    return at;
}

static void
extend_children (TNPtr n)
{
    if (n->nchildren > n->maxchildren) {
	if (n->child == NULL) {
	    n->child = NALLOC (n->nchildren, TNPtr);
	} else {
	    int	   nc  = 2 * n->nchildren;
	    TNPtr* new = (TNPtr*) attemptckrealloc ((char*) n->child,
						    nc * sizeof (TNPtr));
	    if (new == NULL) {
		nc  = n->nchildren;
		new = (TNPtr*) ckrealloc ((char*) n->child, nc * sizeof (TNPtr));
	    }
	    n->child	   = new;
	    n->maxchildren = nc;
	}
    }
}

/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 78
 * End:
 */