Hitmap 1.3
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Friends
Macros
Groups
Pages
extern
metis
Lib
memory.c
Go to the documentation of this file.
1
/*
2
* Copyright 1997, Regents of the University of Minnesota
3
*
4
* memory.c
5
*
6
* This file contains routines that deal with memory allocation
7
*
8
* Started 2/24/96
9
* George
10
*
11
* $Id: memory.c,v 1.2 1998/11/27 18:16:18 karypis Exp $
12
*
13
*/
14
15
#include <
metis.h
>
16
17
18
/*************************************************************************
19
* This function allocates memory for the workspace
20
**************************************************************************/
21
void
AllocateWorkSpace
(
CtrlType
*ctrl,
GraphType
*
graph
,
int
nparts)
22
{
23
ctrl->
wspace
.
pmat
= NULL;
24
25
if
(ctrl->
optype
==
OP_KMETIS
) {
26
ctrl->
wspace
.
edegrees
= (
EDegreeType
*)
GKmalloc
(graph->
nedges
*
sizeof
(
EDegreeType
),
"AllocateWorkSpace: edegrees"
);
27
ctrl->
wspace
.
vedegrees
= NULL;
28
ctrl->
wspace
.
auxcore
= (
idxtype
*)ctrl->
wspace
.
edegrees
;
29
30
ctrl->
wspace
.
pmat
=
idxmalloc
(nparts*nparts,
"AllocateWorkSpace: pmat"
);
31
32
/* Memory requirements for different phases
33
Coarsening
34
Matching: 4*nvtxs vectors
35
Contraction: 2*nvtxs vectors (from the above 4), 1*nparts, 1*Nedges
36
Total = MAX(4*nvtxs, 2*nvtxs+nparts+nedges)
37
38
Refinement
39
Random Refinement/Balance: 5*nparts + 1*nvtxs + 2*nedges
40
Greedy Refinement/Balance: 5*nparts + 2*nvtxs + 2*nedges + 1*PQueue(==Nvtxs)
41
Total = 5*nparts + 3*nvtxs + 2*nedges
42
43
Total = 5*nparts + 3*nvtxs + 2*nedges
44
*/
45
ctrl->
wspace
.
maxcore
= 3*(graph->
nvtxs
+1) +
/* Match/Refinement vectors */
46
5*(nparts+1) +
/* Partition weights etc */
47
graph->
nvtxs
*(
sizeof
(
ListNodeType
)/
sizeof
(
idxtype
)) +
/* Greedy k-way balance/refine */
48
20
/* padding for 64 bit machines */
49
;
50
}
51
else
if
(ctrl->
optype
==
OP_KVMETIS
) {
52
ctrl->
wspace
.
edegrees
= NULL;
53
ctrl->
wspace
.
vedegrees
= (
VEDegreeType
*)
GKmalloc
(graph->
nedges
*
sizeof
(
VEDegreeType
),
"AllocateWorkSpace: vedegrees"
);
54
ctrl->
wspace
.
auxcore
= (
idxtype
*)ctrl->
wspace
.
vedegrees
;
55
56
ctrl->
wspace
.
pmat
=
idxmalloc
(nparts*nparts,
"AllocateWorkSpace: pmat"
);
57
58
/* Memory requirements for different phases are identical to KMETIS */
59
ctrl->
wspace
.
maxcore
= 3*(graph->
nvtxs
+1) +
/* Match/Refinement vectors */
60
3*(nparts+1) +
/* Partition weights etc */
61
graph->
nvtxs
*(
sizeof
(
ListNodeType
)/
sizeof
(
idxtype
)) +
/* Greedy k-way balance/refine */
62
20
/* padding for 64 bit machines */
63
;
64
}
65
else
{
66
ctrl->
wspace
.
edegrees
= (
EDegreeType
*)
idxmalloc
(graph->
nedges
,
"AllocateWorkSpace: edegrees"
);
67
ctrl->
wspace
.
vedegrees
= NULL;
68
ctrl->
wspace
.
auxcore
= (
idxtype
*)ctrl->
wspace
.
edegrees
;
69
70
ctrl->
wspace
.
maxcore
= 5*(graph->
nvtxs
+1) +
/* Refinement vectors */
71
4*(nparts+1) +
/* Partition weights etc */
72
2*graph->
ncon
*graph->
nvtxs
*(
sizeof
(
ListNodeType
)/
sizeof
(
idxtype
)) +
/* 2-way refinement */
73
2*graph->
ncon
*(
NEG_GAINSPAN
+
PLUS_GAINSPAN
+1)*(
sizeof
(
ListNodeType
*)/
sizeof
(
idxtype
)) +
/* 2-way refinement */
74
20
/* padding for 64 bit machines */
75
;
76
}
77
78
ctrl->
wspace
.
maxcore
+=
HTLENGTH
;
79
ctrl->
wspace
.
core
=
idxmalloc
(ctrl->
wspace
.
maxcore
,
"AllocateWorkSpace: maxcore"
);
80
ctrl->
wspace
.
ccore
= 0;
81
}
82
83
84
/*************************************************************************
85
* This function allocates memory for the workspace
86
**************************************************************************/
87
void
FreeWorkSpace
(
CtrlType
*ctrl,
GraphType
*
graph
)
88
{
89
GKfree
(&ctrl->
wspace
.
edegrees
, &ctrl->
wspace
.
vedegrees
, &ctrl->
wspace
.
core
, &ctrl->
wspace
.
pmat
,
LTERM
);
90
}
91
92
/*************************************************************************
93
* This function returns how may words are left in the workspace
94
**************************************************************************/
95
int
WspaceAvail
(
CtrlType
*ctrl)
96
{
97
return
ctrl->
wspace
.
maxcore
- ctrl->
wspace
.
ccore
;
98
}
99
100
101
/*************************************************************************
102
* This function allocate space from the core
103
**************************************************************************/
104
idxtype
*
idxwspacemalloc
(
CtrlType
*ctrl,
int
n)
105
{
106
n += n%2;
/* This is a fix for 64 bit machines that require 8-byte pointer allignment */
107
108
ctrl->
wspace
.
ccore
+= n;
109
ASSERT
(ctrl->
wspace
.
ccore
<= ctrl->
wspace
.
maxcore
);
110
return
ctrl->
wspace
.
core
+ ctrl->
wspace
.
ccore
- n;
111
}
112
113
/*************************************************************************
114
* This function frees space from the core
115
**************************************************************************/
116
void
idxwspacefree
(
CtrlType
*ctrl,
int
n)
117
{
118
n += n%2;
/* This is a fix for 64 bit machines that require 8-byte pointer allignment */
119
120
ctrl->
wspace
.
ccore
-= n;
121
ASSERT
(ctrl->
wspace
.
ccore
>= 0);
122
}
123
124
125
/*************************************************************************
126
* This function allocate space from the core
127
**************************************************************************/
128
float
*
fwspacemalloc
(
CtrlType
*ctrl,
int
n)
129
{
130
n += n%2;
/* This is a fix for 64 bit machines that require 8-byte pointer allignment */
131
132
ctrl->
wspace
.
ccore
+= n;
133
ASSERT
(ctrl->
wspace
.
ccore
<= ctrl->
wspace
.
maxcore
);
134
return
(
float
*) (ctrl->
wspace
.
core
+ ctrl->
wspace
.
ccore
- n);
135
}
136
137
/*************************************************************************
138
* This function frees space from the core
139
**************************************************************************/
140
void
fwspacefree
(
CtrlType
*ctrl,
int
n)
141
{
142
n += n%2;
/* This is a fix for 64 bit machines that require 8-byte pointer allignment */
143
144
ctrl->
wspace
.
ccore
-= n;
145
ASSERT
(ctrl->
wspace
.
ccore
>= 0);
146
}
147
148
149
150
/*************************************************************************
151
* This function creates a CoarseGraphType data structure and initializes
152
* the various fields
153
**************************************************************************/
154
GraphType
*
CreateGraph
(
void
)
155
{
156
GraphType
*
graph
;
157
158
graph = (
GraphType
*)
GKmalloc
(
sizeof
(
GraphType
),
"CreateCoarseGraph: graph"
);
159
160
InitGraph
(graph);
161
162
return
graph
;
163
}
164
165
166
/*************************************************************************
167
* This function creates a CoarseGraphType data structure and initializes
168
* the various fields
169
**************************************************************************/
170
void
InitGraph
(
GraphType
*
graph
)
171
{
172
graph->
gdata
= graph->
rdata
= NULL;
173
174
graph->
nvtxs
= graph->
nedges
= -1;
175
graph->
mincut
= graph->
minvol
= -1;
176
177
graph->
xadj
= graph->
vwgt
= graph->
adjncy
= graph->
adjwgt
= NULL;
178
graph->
adjwgtsum
= NULL;
179
graph->
label
= NULL;
180
graph->
cmap
= NULL;
181
182
graph->
where
= graph->
pwgts
= NULL;
183
graph->
id
= graph->
ed
= NULL;
184
graph->
bndptr
= graph->
bndind
= NULL;
185
graph->
rinfo
= NULL;
186
graph->
vrinfo
= NULL;
187
graph->
nrinfo
= NULL;
188
189
graph->
ncon
= -1;
190
graph->
nvwgt
= NULL;
191
graph->
npwgts
= NULL;
192
193
graph->
vsize
= NULL;
194
195
graph->
coarser
= graph->
finer
= NULL;
196
197
}
198
199
/*************************************************************************
200
* This function deallocates any memory stored in a graph
201
**************************************************************************/
202
void
FreeGraph
(
GraphType
*
graph
)
203
{
204
205
GKfree
(&graph->
gdata
, &graph->
nvwgt
, &graph->
rdata
, &graph->
npwgts
,
LTERM
);
206
free(graph);
207
}
208
workspacedef::edegrees
EDegreeType * edegrees
Definition:
struct.h:102
graphdef::nrinfo
NRInfoType * nrinfo
Definition:
struct.h:190
vedegreedef
Definition:
struct.h:87
idxwspacefree
#define idxwspacefree
Definition:
rename.h:165
workspacedef::vedegrees
VEDegreeType * vedegrees
Definition:
struct.h:103
HTLENGTH
#define HTLENGTH
Definition:
defs.h:26
workspacedef::ccore
int ccore
Definition:
struct.h:100
graphdef::pwgts
idxtype * pwgts
Definition:
struct.h:176
graphdef::cmap
idxtype * cmap
Definition:
struct.h:172
graphdef::adjwgtsum
idxtype * adjwgtsum
Definition:
struct.h:168
controldef::optype
int optype
Definition:
struct.h:222
graphdef::vrinfo
VRInfoType * vrinfo
Definition:
struct.h:187
graphdef::ed
idxtype * ed
Definition:
struct.h:181
graphdef::id
idxtype * id
Definition:
struct.h:181
fwspacefree
void fwspacefree(CtrlType *ctrl, int n)
Definition:
memory.c:140
FreeGraph
#define FreeGraph
Definition:
rename.h:169
graphdef::mincut
int mincut
Definition:
struct.h:175
graphdef::bndptr
idxtype * bndptr
Definition:
struct.h:178
workspacedef::core
idxtype * core
Definition:
struct.h:99
edegreedef
Definition:
struct.h:77
graphdef::rdata
idxtype * rdata
Definition:
struct.h:157
idxwspacemalloc
#define idxwspacemalloc
Definition:
rename.h:164
graphdef::coarser
struct graphdef * coarser
Definition:
struct.h:198
graphdef::finer
struct graphdef * finer
Definition:
struct.h:198
graph
HitTile_Vector graph
Definition:
spring_bitmap.c:132
controldef
Definition:
struct.h:214
graphdef::where
idxtype * where
Definition:
struct.h:176
LTERM
#define LTERM
Definition:
defs.h:18
graphdef::npwgts
float * npwgts
Definition:
struct.h:196
idxtype
int idxtype
Definition:
struct.h:19
AllocateWorkSpace
#define AllocateWorkSpace
Definition:
rename.h:161
fwspacemalloc
#define fwspacemalloc
Definition:
rename.h:166
OP_KVMETIS
#define OP_KVMETIS
Definition:
defs.h:94
graphdef::label
idxtype * label
Definition:
struct.h:170
graphdef::adjwgt
idxtype * adjwgt
Definition:
struct.h:166
graphdef::rinfo
RInfoType * rinfo
Definition:
struct.h:184
workspacedef::maxcore
int maxcore
Definition:
struct.h:100
WspaceAvail
#define WspaceAvail
Definition:
rename.h:163
metis.h
GKfree
void GKfree(void **ptr1,...)
Definition:
util.c:121
graphdef::ncon
int ncon
Definition:
struct.h:194
CreateGraph
#define CreateGraph
Definition:
rename.h:167
GKmalloc
#define GKmalloc
Definition:
rename.h:387
workspacedef::auxcore
idxtype * auxcore
Definition:
struct.h:106
graphdef
Definition:
struct.h:156
graphdef::bndind
idxtype * bndind
Definition:
struct.h:178
NEG_GAINSPAN
#define NEG_GAINSPAN
Definition:
defs.h:24
OP_KMETIS
#define OP_KMETIS
Definition:
defs.h:90
ListNodeType
struct ListNodeType ListNodeType
Definition:
struct.h:46
FreeWorkSpace
#define FreeWorkSpace
Definition:
rename.h:162
graphdef::vwgt
idxtype * vwgt
Definition:
struct.h:163
PLUS_GAINSPAN
#define PLUS_GAINSPAN
Definition:
defs.h:23
graphdef::minvol
int minvol
Definition:
struct.h:175
graphdef::nedges
int nedges
Definition:
struct.h:161
idxmalloc
#define idxmalloc
Definition:
rename.h:383
workspacedef::pmat
idxtype * pmat
Definition:
struct.h:108
graphdef::gdata
idxtype * gdata
Definition:
struct.h:157
graphdef::nvtxs
int nvtxs
Definition:
struct.h:161
controldef::wspace
WorkSpaceType wspace
Definition:
struct.h:227
ASSERT
#define ASSERT(expr)
Definition:
macros.h:130
graphdef::nvwgt
float * nvwgt
Definition:
struct.h:195
graphdef::vsize
idxtype * vsize
Definition:
struct.h:164
ListNodeType
Definition:
struct.h:41
graphdef::adjncy
idxtype * adjncy
Definition:
struct.h:165
graphdef::xadj
idxtype * xadj
Definition:
struct.h:162
InitGraph
#define InitGraph
Definition:
rename.h:168
Generated on Thu Oct 11 2018 12:23:26 for Hitmap 1.3 by
1.8.5