← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to dotneato/neatogen/heap.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
dotneato/neatogen/heap.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
#pragma prototyped
 
11
 
 
12
#include<stdio.h>
 
13
 
 
14
#include "mem.h"
 
15
#include "hedges.h"
 
16
#include "heap.h"
 
17
 
 
18
#ifdef DMALLOC
 
19
#include "dmalloc.h"
 
20
#endif
 
21
 
 
22
static Halfedge *PQhash;
 
23
static int PQhashsize;
 
24
static int PQcount;
 
25
static int PQmin;
 
26
 
 
27
static int 
 
28
PQbucket(Halfedge *he)
 
29
{
 
30
    int bucket;
 
31
 
 
32
    bucket = (he->ystar - ymin)/deltay * PQhashsize;
 
33
    if (bucket<0) bucket = 0;
 
34
    if (bucket>=PQhashsize) bucket = PQhashsize-1 ;
 
35
    if (bucket < PQmin) PQmin = bucket;
 
36
    return(bucket);
 
37
}
 
38
 
 
39
void
 
40
PQinsert(Halfedge *he, Site *v, float offset)
 
41
{
 
42
    Halfedge  *last, *next;
 
43
 
 
44
    he -> vertex = v;
 
45
    ref(v);
 
46
    he -> ystar = v -> coord.y + offset;
 
47
    last = &PQhash[PQbucket(he)];
 
48
    while ((next = last -> PQnext) != (struct Halfedge *) NULL &&
 
49
        (he -> ystar  > next -> ystar  ||
 
50
        (he -> ystar == next -> ystar && v -> coord.x > next->vertex->coord.x)))
 
51
      {
 
52
        last = next;
 
53
      }
 
54
    he -> PQnext = last -> PQnext; 
 
55
    last -> PQnext = he;
 
56
    PQcount += 1;
 
57
}
 
58
 
 
59
void
 
60
PQdelete(Halfedge *he)
 
61
{
 
62
    Halfedge *last;
 
63
 
 
64
    if(he ->  vertex != (Site *) NULL) {
 
65
        last = &PQhash[PQbucket(he)];
 
66
        while (last -> PQnext != he) last = last -> PQnext;
 
67
        last -> PQnext = he -> PQnext;
 
68
        PQcount -= 1;
 
69
        deref(he -> vertex);
 
70
        he -> vertex = (Site *) NULL;
 
71
    }
 
72
}
 
73
 
 
74
 
 
75
int 
 
76
PQempty()
 
77
{
 
78
    return(PQcount==0);
 
79
}
 
80
 
 
81
 
 
82
Point 
 
83
PQ_min()
 
84
{
 
85
    Point answer;
 
86
 
 
87
    while(PQhash[PQmin].PQnext == (struct Halfedge *)NULL) {PQmin += 1;}
 
88
    answer.x = PQhash[PQmin].PQnext -> vertex -> coord.x;
 
89
    answer.y = PQhash[PQmin].PQnext -> ystar;
 
90
    return (answer);
 
91
}
 
92
 
 
93
Halfedge *
 
94
PQextractmin()
 
95
{
 
96
    Halfedge *curr;
 
97
 
 
98
    curr = PQhash[PQmin].PQnext;
 
99
    PQhash[PQmin].PQnext = curr -> PQnext;
 
100
    PQcount -= 1;
 
101
    return(curr);
 
102
}
 
103
 
 
104
 
 
105
void
 
106
PQinitialize()
 
107
{
 
108
    int i; 
 
109
 
 
110
    PQcount = 0;
 
111
    PQmin = 0;
 
112
    PQhashsize = 4 * sqrt_nsites;
 
113
    if (PQhash == NULL) 
 
114
        PQhash = (Halfedge *) myalloc(PQhashsize * sizeof *PQhash);
 
115
    for(i=0; i<PQhashsize; i+=1) PQhash[i].PQnext = (Halfedge *)NULL;
 
116
}
 
117
 
 
118
static void
 
119
PQdumphe (Halfedge *p)
 
120
{
 
121
    printf ("  [%x] %x %x %d %d %d %d %f\n",
 
122
      p, p->ELleft, p->ELright, p->ELedge->edgenbr,
 
123
      p->ELrefcnt, p->ELpm, (p->vertex ? p->vertex->sitenbr : -1), p->ystar);
 
124
}
 
125
 
 
126
void PQdump()
 
127
{
 
128
    int i;
 
129
    Halfedge *p;
 
130
 
 
131
    for(i=0; i<PQhashsize; i+=1) {
 
132
      printf("[%d]\n", i);
 
133
      p = PQhash[i].PQnext;
 
134
      while (p != NULL) {
 
135
        PQdumphe (p);
 
136
        p = p->PQnext;
 
137
      }
 
138
    }
 
139
 
 
140
}
 
141