text.mod/graphviz.mod/graphviz/lib/fdpgen/grid.c

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/


/*
 * grid.c
 * Written by Emden R. Gansner
 *
 * Support for grid to speed up layout. On each pass, nodes are
 * put into grid cells. Given a node, repulsion is only computed 
 * for nodes in one of that nodes 9 adjacent grids.
 */

/* uses PRIVATE interface for NOTUSED */
#define FDP_PRIVATE 1

#include <fdpgen/fdp.h>
#include <fdpgen/grid.h>
#include <common/macros.h>
#include <stddef.h>
#include <string.h>
#include <util/alloc.h>

  /* structure for maintaining a free list of cells */
typedef struct _block {
    cell *mem;			/* block of cells */
    cell *cur;			/* next available cell */
    cell *endp;			/* after last cell */
    struct _block *next;	/* next memory block */
} block_t;

/* newBlock:
 * Create new block of size cells
 */
static block_t *newBlock(int size)
{
    block_t *newb = gv_alloc(sizeof(block_t));
    newb->next = 0;
    newb->mem = gv_calloc(size, sizeof(cell));
    newb->endp = newb->mem + size;
    newb->cur = newb->mem;

    return newb;
}

/* freeBlock:
 * Free malloc'ed memory and block.
 * Recurse to next block
 */
static void freeBlock(block_t * b)
{
    if (b) {
	block_t *next = b->next;
	free(b->mem);
	free(b);
	freeBlock(next);
    }
}

struct _grid {
    Dt_t *data;			/* cells indexed by (i,j) */
    block_t *cellMem;		/* list of memory blocks for cells */
    block_t *cellCur;		/* current block */
    int listSize;		/* memory of nodes */
    node_list *listMem;		/* list of memory for node items */
    node_list *listCur;		/* next node item */
};

/* getCell:
 * Create a new cell using memory blocks.
 */
static cell *getCell(Grid * g)
{
    cell *cp;
    block_t *bp = g->cellCur;	/* current block */

    if (bp->cur == bp->endp) {	/* current block is full */
	if (bp->next == 0) {
	    bp->next = newBlock(2 * (bp->endp - bp->mem));
	}
	bp = g->cellCur = bp->next;
	bp->cur = bp->mem;
    }
    cp = bp->cur++;
    return cp;
}

static int ijcmpf(void *point1, void *point2) {
    const gridpt *p1 = point1;
    const gridpt *p2 = point2;
    if (p1->i < p2->i) {
        return -1;
    }
    if (p1->i > p2->i) {
        return 1;
    }
    if (p1->j < p2->j) {
        return -1;
    }
    if (p1->j > p2->j) {
        return 1;
    }
    return 0;
}

static Grid _grid; // hack because can't attach info. to Dt_t

/* newCell:
 * Allocate a new cell from free store and initialize its indices
 * This is used by the grid discipline to create cells.
 */
static void *newCell(void *obj, Dtdisc_t *disc) {
    cell *cellp = obj;
    cell *newp;

    (void)disc;
    newp = getCell(&_grid);
    newp->p.i = cellp->p.i;
    newp->p.j = cellp->p.j;
    newp->nodes = 0;

    return newp;
}

/* newNode:
 * Allocate a new node item from free store. 
 * Set node value and hook into list.
 * A grid assumes the memory allocated in adjustGrid
 * will be enough more all nodes added.
 */
static node_list *newNode(Grid * g, Agnode_t * n, node_list * nxt)
{
    node_list *newp;

    newp = g->listCur++;
    newp->node = n;
    newp->next = nxt;

    return newp;
}

static Dtdisc_t gridDisc = {
    offsetof(cell, p),
    sizeof(gridpt),
    offsetof(cell, link),
    newCell,
    NULL,
    ijcmpf,
};

/* mkGrid:
 * Create grid data structure.
 * cellHint provides rough idea of how many cells
 * may be needed.
 */
Grid *mkGrid(int cellHint)
{
    Grid *g = &_grid;
    memset(g, 0, sizeof(*g)); // see comment above
    g->data = dtopen(&gridDisc, Dtoset);
    g->cellMem = newBlock(cellHint);
    return g;
}

/* adjustGrid:
 * Set up node list for grid. Make sure the list
 * can handle nnodes nodes.
 * It is assumed no more than nnodes will be added
 * to the grid.
 */
void adjustGrid(Grid * g, int nnodes)
{
    int nsize;

    if (nnodes > g->listSize) {
	nsize = MAX(nnodes, 2 * g->listSize);
	if (g->listMem)
	    free(g->listMem);
	g->listMem = gv_calloc(nsize, sizeof(node_list));
	g->listSize = nsize;
    }
}

/* clearGrid:
 * Reset grid. This clears the dictionary,
 * and reuses available memory.
 */
void clearGrid(Grid * g)
{
    dtclear(g->data);
    g->listCur = g->listMem;
    g->cellCur = g->cellMem;
    g->cellCur->cur = g->cellCur->mem;
}

/* delGrid:
 * Close and free all grid resources.
 */
void delGrid(Grid * g)
{
    dtclose(g->data);
    freeBlock(g->cellMem);
    free(g->listMem);
}

/* addGrid:
 * Add node n to cell (i,j) in grid g.
 */
void addGrid(Grid * g, int i, int j, Agnode_t * n)
{
    cell *cellp;
    cell key;

    key.p.i = i;
    key.p.j = j;
    cellp = dtinsert(g->data, &key);
    cellp->nodes = newNode(g, n, cellp->nodes);
    if (Verbose >= 3) {
	fprintf(stderr, "grid(%d,%d): %s\n", i, j, agnameof(n));
    }
}

typedef int (*walkfn_t)(void*, void*);

/* walkGrid:
 * Apply function walkf to each cell in the grid.
 * The second argument to walkf is the cell; the
 * third argument is the grid. (The first argument
 * is the dictionary.) walkf must return 0.
 */
void walkGrid(Grid *g, int (*walkf)(cell*, Grid*))
{
    dtwalk(g->data, (walkfn_t) walkf, g);
}

/* findGrid;
 * Return the cell, if any, corresponding to
 * indices i,j
 */
cell *findGrid(Grid * g, int i, int j)
{
    cell key;

    key.p.i = i;
    key.p.j = j;
    return dtsearch(g->data, &key);
}

/* gLength:
 * Return the number of nodes in a cell.
 */
int gLength(cell * p)
{
    int len = 0;
    node_list *nodes = p->nodes;

    while (nodes) {
	len++;
	nodes = nodes->next;
    }
    return len;
}