alloc.c

Go to the documentation of this file.

#define       NULL 0
#include "bary.h"
#include <stdio.h>
#include <stdlib.h>

/*--------------------------------------------------------------------*/

/*  Memory Management for DLLIST objects 
 *  ====================================
 */

/*  To have a good layout, we calculate the number of crossings of edges
 *  and try to minimize them. For the calculation of crossings, we need
 *  double linked lists of nodes (see step2.c) representing the upper
 *  list of touched nodes and the lower list of touched nodes. Because
 *  nodes may have multible occurences in these lists, we use the special
 *  data structure DLLIST. 
 *  We reuse the DSUCC field to keep the list of free dllist nodes.
 *  But THIS dllist_freelist is NOT double linked.
 */

static DLLIST   dllist_freelist  = NULL;     /* list of free dllist nodes */


/*  Allocate a DLLIST object
 *  ------------------------
 *  First, we look in the free list, if we have a free cell. Otherwise,
 *  we allocate a cell from the core memory.
 *  The successor is always NULL, because we append at the end of the
 *  list. pred is the predecessor.
 */


#ifdef ANSI_C
DLLIST  dllist_alloc(GNODE node, DLLIST pred)
#else
DLLIST  dllist_alloc(node,pred)
GNODE  node;
DLLIST pred;
#endif
{
        DLLIST  h;

        debugmessage("dllist_alloc","");
        if (dllist_freelist) {
                h = dllist_freelist;
                dllist_freelist = DSUCC(dllist_freelist);
        }
        else    h = (DLLIST)myalloc(sizeof(struct dllist));
        DNODE(h) = node;
        DPRED(h) = pred;
        DSUCC(h) = NULL;
        return(h);
}


/*  Deallocate one DLLIST objects
 *  -----------------------------
 *  The crossing algorithm is stable enough such that after calculation
 *  of crossings all DLLIST elements are given free by this function.
 *  Thus we don't need any additional memory management.
 */

#ifdef ANSI_C
void    dllist_free(DLLIST x)
#else
void    dllist_free(x)
DLLIST x;
#endif
{
        debugmessage("dllist_free","");
        DSUCC(x) = dllist_freelist;
        dllist_freelist = x;
}


/*  Deallocate a list of DLLIST objects
 *  -----------------------------------
 */

#ifdef ANSI_C
void    dllist_free_all(DLLIST x)
#else
void    dllist_free_all(x)
DLLIST x;
#endif
{
        DLLIST h;

        debugmessage("dllist_free","");
        if (x) {
                h = x;
                while (DSUCC(h)) h = DSUCC(h);
                DSUCC(h) = dllist_freelist;
                dllist_freelist = x;
        }
}



void * myalloc(unsigned size)
{
    return malloc(size);
}


/*  Allocate a temporary GNLIST object
 *  ----------------------------------
 *  First, we look in the free list, if we have a free node. Otherwise,
 *  we allocate a node from the core memory.
 *  We also set some default values.
 *  These node lists are temporary, thus we store them in the
 *  tmpnconslist, to give them free later.
 */
static GNLIST ncons_freelist = NULL;  /* list of free cons cells      */
static GNLIST tmpnconslist   = NULL;  /* list of allocated cons cells */

GNLIST  tmpnodelist_alloc(void)
{
        GNLIST  h;

        debugmessage("tmpnodelist_alloc","");
        if (ncons_freelist) {
                h = ncons_freelist;
                ncons_freelist = GNINTERN(ncons_freelist);
        }
        else    h = (GNLIST)myalloc(sizeof(struct gnlist));
        GNINTERN(h) = tmpnconslist;
        GNNODE(h)   = NULL;
        GNNEXT(h)   = NULL;
        tmpnconslist = h;
        return(h);
}

---