vertex_t *createvertex (xy_t xy) {
    vertex_t *vmemp, *vp;

    vmemp = vp = NULL;
    if (!(vmemp = vmalloc (vvm, sizeof (vertex_t))))
        goto abortcreatevertex;
    vmemp->xy = xy;
    if (!(vp = dtinsert (vertexdict, vmemp)))
        goto abortcreatevertex;
    if (vp != vmemp) {
        vmfree (vvm, vmemp);
        return vp;
    }
    if (!(vp->edgeps = vmalloc (Vmheap, 4 * sizeof (edge_t *))))
        goto abortcreatevertex;
    vp->edgepn = 4;
    vp->edgepl = 0;
    return vp;

abortcreatevertex:
    SUwarning (
        1, "createvertex", "create failed for vertex (%d,%d)", xy.x, xy.y
    );
    if (vp) {
        if (vp == vmemp)
            dtdelete (vertexdict, vp);
        if (vp->edgeps)
            vmfree (Vmheap, vp->edgeps);
    }
    if (vmemp)
        vmfree (vvm, vmemp);
    return NULL;
}

static void vmapAdd(Dt_t * map, int i, int j)
{
    Ipair obj;
    obj.i = i;
    obj.j = j;
    dtinsert(map, &obj);
}

/* insertEdge:
 */
static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
{
    item dummy;

    dummy.p[0] = t;
    dummy.p[1] = h;
    dummy.t = e->tail;
    dummy.h = e->head;
    dtinsert(map, &dummy);

    dummy.p[0] = h;
    dummy.p[1] = t;
    dummy.t = e->head;
    dummy.h = e->tail;
    dtinsert(map, &dummy);
}

/* constrainX:
 * Create the X constrains and solve. We use a linear objective function
 * (absolute values rather than squares), so we can reuse network simplex.
 * The constraints are encoded as a dag with edges having a minimum length.
 */
static void constrainX(graph_t* g, nitem* nlist, int nnodes, intersectfn ifn,
                       int ortho)
{
    Dt_t *list = dtopen(&constr, Dtobag);
    nitem *p = nlist;
    graph_t *cg;
    int i;

    for (i = 0; i < nnodes; i++) {
	p->val = p->pos.x;
	dtinsert(list, p);
	p++;
    }
    if (ortho)
	cg = mkConstraintG(g, list, ifn, distX);
    else
	cg = mkNConstraintG(g, list, ifn, distX);
    rank(cg, 2, INT_MAX);

    p = nlist;
    for (i = 0; i < nnodes; i++) {
	int newpos, oldpos, delta;
	oldpos = p->pos.x;
	newpos = ND_rank(p->cnode);
	delta = newpos - oldpos;
	p->pos.x = newpos;
	p->bb.LL.x += delta;
	p->bb.UR.x += delta;
	p++;
    }

    closeGraph(cg);
    dtclose(list);
}

static void update(Dict_t * Q, Agnode_t * dest, Agnode_t * src, double len)
{
    double newlen = getdist(src) + len;
    double oldlen = getdist(dest);

    if (oldlen == 0) {		/* first time to see dest */
	setdist(dest, newlen);
	if (doPath) setprev(dest, src);
	dtinsert(Q, dest);
    } else if (newlen < oldlen) {
	dtdelete(Q, dest);
	setdist(dest, newlen);
	if (doPath) setprev(dest, src);
	dtinsert(Q, dest);
    }
}

void add_edge(edgelist * list, Agedge_t * e)
{
    edgelistitem temp;

    temp.edge = e;
    dtinsert(list, &temp);
}

void push(queue * nq, void *n)
{
    nsitem obj;

    obj.np = n;
    dtinsert(nq, &obj);
}

/* insertEdge:
 */
static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
{
    item dummy;

    dummy.p[0] = t;
    dummy.p[1] = h;
    dummy.t = agtail(e);
    dummy.h = aghead(e);
    dtinsert(map, &dummy);

    dummy.p[0] = h;
    dummy.p[1] = t;
    dummy.t = aghead(e);
    dummy.h = agtail(e);
    dtinsert(map, &dummy);
}

static void storeline(GVC_t *gvc, textlabel_t *lp, char *line, char terminator)
{
    pointf size;
    textspan_t *span;
    static textfont_t tf;
    int oldsz = lp->u.txt.nspans + 1;

    lp->u.txt.span = ZALLOC(oldsz + 1, lp->u.txt.span, textspan_t, oldsz);
    span = &(lp->u.txt.span[lp->u.txt.nspans]);
    span->str = line;
    span->just = terminator;
    if (line && line[0]) {
	tf.name = lp->fontname;
	tf.size = lp->fontsize;
	span->font = dtinsert(gvc->textfont_dt, &tf);
        size = textspan_size(gvc, span);
    }
    else {
	size.x = 0.0;
	span->size.y = size.y = (int)(lp->fontsize * LINESPACING);
    }

    lp->u.txt.nspans++;
    /* width = max line width */
    lp->dimen.x = MAX(lp->dimen.x, size.x);
    /* accumulate height */
    lp->dimen.y += size.y;
}

/* insertNodeset:
 * Add a node into the nodeset.
 */
void insertNodeset(nodeset_t * ns, Agnode_t * n)
{
    nsitem_t key;

    key.np = n;
    dtinsert(ns, &key);
}

void addPS(PointSet * ps, int x, int y)
{
    point pt;

    pt.x = x;
    pt.y = y;
    dtinsert(ps, mkPair(pt));
}

void 
addIntSet (Dt_t* is, int v)
{
    intitem obj;

    obj.id = v;
    dtinsert(is, &obj);
}

int
ptdelete(Pt_t* tab, Ptaddr_t min, Ptaddr_t max)
{
	register Ptprefix_t*	xp;
	Ptprefix_t		key;
	Ptprefix_t		cur;

	tab->entries++;
	key.min = min;
	key.max = max;
	if (xp = (Ptprefix_t*)dtsearch(tab->dict, &key))
	{
		do
		{
			cur.min = xp->min;
			cur.max = xp->max;
			dtdelete(tab->dict, xp);
			if (key.min > cur.min)
			{
				max = cur.max;
				cur.max = key.min - 1;
				if (!dtinsert(tab->dict, &cur))
					goto bad;
				if (key.max < max)
				{
					cur.min = key.max + 1;
					cur.max = max;
					if (!dtinsert(tab->dict, &cur))
						goto bad;
					break;
				}
			}
			else if (key.max < xp->max)
			{
				xp->min = key.max + 1;
				if (!dtinsert(tab->dict, xp))
					goto bad;
			}
		} while (xp = (Ptprefix_t*)dtnext(tab->dict, xp));
	}
	return 0;
 bad:
	if (tab->disc->errorf)
		(*tab->disc->errorf)(NiL, tab->disc, ERROR_SYSTEM|2, "out of space");
	return -1;
}

void insertPS(PointSet * ps, point pt)
{
    pair *pp;

    pp = mkPair(pt);
    if (dtinsert(ps, pp) != pp)
        free(pp);
}

/* insertDeglist:
 * Add a node to the node list.
 * Nodes are kept sorted by DEGREE, smallest degrees first.
 */
void insertDeglist(deglist_t * ns, Agnode_t * n)
{
    degitem key;
    degitem *kp;

    key.deg = DEGREE(n);
    kp = dtinsert(ns, &key);
    ND_next(n) = kp->np;
    kp->np = n;
}

static textfont_t *mkFont(GVC_t *gvc, char **atts, int flags, int ul)
{
    textfont_t tf = {NULL,NULL,NULL,0.0,0,0};

    tf.size = -1.0;		/* unassigned */
    tf.flags = flags;
    if (atts)
	doAttrs(&tf, font_items, sizeof(font_items) / ISIZE, atts, "<FONT>");

    return dtinsert(gvc->textfont_dt, &tf);
}

void addPS(PointSet * ps, int x, int y)
{
    point pt;
    pair *pp;

    pt.x = x;
    pt.y = y;
    pp = mkPair(pt);
    if (dtinsert(ps, pp) != pp)
        free(pp);
}

int insertPM(PointMap * pm, int x, int y, int v)
{
    mpair *p;
    mpair dummy;

    dummy.id.x = x;
    dummy.id.y = y;
    dummy.v = v;
    p = dtinsert(pm, &dummy);
    return p->v;
}

static void associate(Agraph_t *model, void *key, rep_t val)
{
	Dict_t		*dict;
	repkey_t	*newelt;

	assert(association(model,key).type == 0);
	dict = repdict(model);
	newelt = NEW(repkey_t);
	newelt->key = key;
	newelt->val = val;
	dtinsert(dict,newelt);
}

int
pssttyadd(register Pss_t* pss, const char* name, Pss_dev_t dev)
{
	register Tty_t*	tty;

	if (!dtmatch(pss->ttybyname, name))
	{
		if (!(tty = vmnewof(pss->vm, 0, Tty_t, 1, strlen(name))))
		{
			if (pss->disc->errorf)
				(*pss->disc->errorf)(pss, pss->disc, ERROR_SYSTEM|2, "out of space");
			return -1;
		}
		strcpy(tty->name, name);
		tty->dev = dev;
		dtinsert(pss->ttybyname, tty);
		if (!dtmatch(pss->ttybydev, &dev))
			dtinsert(pss->ttybydev, tty);
	}
	return 0;
}