CoCalc -- gk_mkpqueue.h

GitHub Repository: ElmerCSC/elmerfem
Path: blob/devel/elmergrid/src/metis-5.1.0/GKlib/gk_mkpqueue.h
³²⁰⁶ views
1
/*!
2
\file  gk_mkpqueue.h
3
\brief Templates for priority queues
4

5
\date   Started 4/09/07
6
\author George
7
\version\verbatim $Id: gk_mkpqueue.h 13005 2012-10-23 22:34:36Z karypis $ \endverbatim
8
*/
9

10

11
#ifndef _GK_MKPQUEUE_H
12
#define _GK_MKPQUEUE_H
13

14

15
#define GK_MKPQUEUE(FPRFX, PQT, KVT, KT, VT, KVMALLOC, KMAX, KEY_LT)\
16
/*************************************************************************/\
17
/*! This function creates and initializes a priority queue */\
18
/**************************************************************************/\
19
PQT *FPRFX ## Create(size_t maxnodes)\
20
{\
21
  PQT *queue; \
22
\
23
  queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate: queue");\
24
  FPRFX ## Init(queue, maxnodes);\
25
\
26
  return queue;\
27
}\
28
\
29
\
30
/*************************************************************************/\
31
/*! This function initializes the data structures of the priority queue */\
32
/**************************************************************************/\
33
void FPRFX ## Init(PQT *queue, size_t maxnodes)\
34
{\
35
  queue->nnodes = 0;\
36
  queue->maxnodes = maxnodes;\
37
\
38
  queue->heap    = KVMALLOC(maxnodes, "gk_PQInit: heap");\
39
  queue->locator = gk_idxsmalloc(maxnodes, -1, "gk_PQInit: locator");\
40
}\
41
\
42
\
43
/*************************************************************************/\
44
/*! This function resets the priority queue */\
45
/**************************************************************************/\
46
void FPRFX ## Reset(PQT *queue)\
47
{\
48
  gk_idx_t i;\
49
  gk_idx_t *locator=queue->locator;\
50
  KVT *heap=queue->heap;\
51
\
52
  for (i=queue->nnodes-1; i>=0; i--)\
53
    locator[heap[i].val] = -1;\
54
  queue->nnodes = 0;\
55
}\
56
\
57
\
58
/*************************************************************************/\
59
/*! This function frees the internal datastructures of the priority queue */\
60
/**************************************************************************/\
61
void FPRFX ## Free(PQT *queue)\
62
{\
63
  if (queue == NULL) return;\
64
  gk_free((void **)&queue->heap, &queue->locator, LTERM);\
65
  queue->maxnodes = 0;\
66
}\
67
\
68
\
69
/*************************************************************************/\
70
/*! This function frees the internal datastructures of the priority queue \
71
    and the queue itself */\
72
/**************************************************************************/\
73
void FPRFX ## Destroy(PQT *queue)\
74
{\
75
  if (queue == NULL) return;\
76
  FPRFX ## Free(queue);\
77
  gk_free((void **)&queue, LTERM);\
78
}\
79
\
80
\
81
/*************************************************************************/\
82
/*! This function returns the length of the queue */\
83
/**************************************************************************/\
84
size_t FPRFX ## Length(PQT *queue)\
85
{\
86
  return queue->nnodes;\
87
}\
88
\
89
\
90
/*************************************************************************/\
91
/*! This function adds an item in the priority queue */\
92
/**************************************************************************/\
93
int FPRFX ## Insert(PQT *queue, VT node, KT key)\
94
{\
95
  gk_idx_t i, j;\
96
  gk_idx_t *locator=queue->locator;\
97
  KVT *heap=queue->heap;\
98
\
99
  ASSERT2(FPRFX ## CheckHeap(queue));\
100
\
101
  ASSERT(locator[node] == -1);\
102
\
103
  i = queue->nnodes++;\
104
  while (i > 0) {\
105
    j = (i-1)>>1;\
106
    if (KEY_LT(key, heap[j].key)) {\
107
      heap[i] = heap[j];\
108
      locator[heap[i].val] = i;\
109
      i = j;\
110
    }\
111
    else\
112
      break;\
113
  }\
114
  ASSERT(i >= 0);\
115
  heap[i].key   = key;\
116
  heap[i].val   = node;\
117
  locator[node] = i;\
118
\
119
  ASSERT2(FPRFX ## CheckHeap(queue));\
120
\
121
  return 0;\
122
}\
123
\
124
\
125
/*************************************************************************/\
126
/*! This function deletes an item from the priority queue */\
127
/**************************************************************************/\
128
int FPRFX ## Delete(PQT *queue, VT node)\
129
{\
130
  gk_idx_t i, j, nnodes;\
131
  KT newkey, oldkey;\
132
  gk_idx_t *locator=queue->locator;\
133
  KVT *heap=queue->heap;\
134
\
135
  ASSERT(locator[node] != -1);\
136
  ASSERT(heap[locator[node]].val == node);\
137
\
138
  ASSERT2(FPRFX ## CheckHeap(queue));\
139
\
140
  i = locator[node];\
141
  locator[node] = -1;\
142
\
143
  if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {\
144
    node   = heap[queue->nnodes].val;\
145
    newkey = heap[queue->nnodes].key;\
146
    oldkey = heap[i].key;\
147
\
148
    if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
149
      while (i > 0) {\
150
        j = (i-1)>>1;\
151
        if (KEY_LT(newkey, heap[j].key)) {\
152
          heap[i] = heap[j];\
153
          locator[heap[i].val] = i;\
154
          i = j;\
155
        }\
156
        else\
157
          break;\
158
      }\
159
    }\
160
    else { /* Filter down */\
161
      nnodes = queue->nnodes;\
162
      while ((j=(i<<1)+1) < nnodes) {\
163
        if (KEY_LT(heap[j].key, newkey)) {\
164
          if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
165
            j++;\
166
          heap[i] = heap[j];\
167
          locator[heap[i].val] = i;\
168
          i = j;\
169
        }\
170
        else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
171
          j++;\
172
          heap[i] = heap[j];\
173
          locator[heap[i].val] = i;\
174
          i = j;\
175
        }\
176
        else\
177
          break;\
178
      }\
179
    }\
180
\
181
    heap[i].key   = newkey;\
182
    heap[i].val   = node;\
183
    locator[node] = i;\
184
  }\
185
\
186
  ASSERT2(FPRFX ## CheckHeap(queue));\
187
\
188
  return 0;\
189
}\
190
\
191
\
192
/*************************************************************************/\
193
/*! This function updates the key values associated for a particular item */ \
194
/**************************************************************************/\
195
void FPRFX ## Update(PQT *queue, VT node, KT newkey)\
196
{\
197
  gk_idx_t i, j, nnodes;\
198
  KT oldkey;\
199
  gk_idx_t *locator=queue->locator;\
200
  KVT *heap=queue->heap;\
201
\
202
  oldkey = heap[locator[node]].key;\
203
\
204
  ASSERT(locator[node] != -1);\
205
  ASSERT(heap[locator[node]].val == node);\
206
  ASSERT2(FPRFX ## CheckHeap(queue));\
207
\
208
  i = locator[node];\
209
\
210
  if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
211
    while (i > 0) {\
212
      j = (i-1)>>1;\
213
      if (KEY_LT(newkey, heap[j].key)) {\
214
        heap[i] = heap[j];\
215
        locator[heap[i].val] = i;\
216
        i = j;\
217
      }\
218
      else\
219
        break;\
220
    }\
221
  }\
222
  else { /* Filter down */\
223
    nnodes = queue->nnodes;\
224
    while ((j=(i<<1)+1) < nnodes) {\
225
      if (KEY_LT(heap[j].key, newkey)) {\
226
        if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
227
          j++;\
228
        heap[i] = heap[j];\
229
        locator[heap[i].val] = i;\
230
        i = j;\
231
      }\
232
      else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
233
        j++;\
234
        heap[i] = heap[j];\
235
        locator[heap[i].val] = i;\
236
        i = j;\
237
      }\
238
      else\
239
        break;\
240
    }\
241
  }\
242
\
243
  heap[i].key   = newkey;\
244
  heap[i].val   = node;\
245
  locator[node] = i;\
246
\
247
  ASSERT2(FPRFX ## CheckHeap(queue));\
248
\
249
  return;\
250
}\
251
\
252
\
253
/*************************************************************************/\
254
/*! This function returns the item at the top of the queue and removes\
255
    it from the priority queue */\
256
/**************************************************************************/\
257
VT FPRFX ## GetTop(PQT *queue)\
258
{\
259
  gk_idx_t i, j;\
260
  gk_idx_t *locator;\
261
  KVT *heap;\
262
  VT vtx, node;\
263
  KT key;\
264
\
265
  ASSERT2(FPRFX ## CheckHeap(queue));\
266
\
267
  if (queue->nnodes == 0)\
268
    return -1;\
269
\
270
  queue->nnodes--;\
271
\
272
  heap    = queue->heap;\
273
  locator = queue->locator;\
274
\
275
  vtx = heap[0].val;\
276
  locator[vtx] = -1;\
277
\
278
  if ((i = queue->nnodes) > 0) {\
279
    key  = heap[i].key;\
280
    node = heap[i].val;\
281
    i = 0;\
282
    while ((j=2*i+1) < queue->nnodes) {\
283
      if (KEY_LT(heap[j].key, key)) {\
284
        if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
285
          j = j+1;\
286
        heap[i] = heap[j];\
287
        locator[heap[i].val] = i;\
288
        i = j;\
289
      }\
290
      else if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, key)) {\
291
        j = j+1;\
292
        heap[i] = heap[j];\
293
        locator[heap[i].val] = i;\
294
        i = j;\
295
      }\
296
      else\
297
        break;\
298
    }\
299
\
300
    heap[i].key   = key;\
301
    heap[i].val   = node;\
302
    locator[node] = i;\
303
  }\
304
\
305
  ASSERT2(FPRFX ## CheckHeap(queue));\
306
  return vtx;\
307
}\
308
\
309
\
310
/*************************************************************************/\
311
/*! This function returns the item at the top of the queue. The item is not\
312
    deleted from the queue. */\
313
/**************************************************************************/\
314
VT FPRFX ## SeeTopVal(PQT *queue)\
315
{\
316
  return (queue->nnodes == 0 ? -1 : queue->heap[0].val);\
317
}\
318
\
319
\
320
/*************************************************************************/\
321
/*! This function returns the key of the top item. The item is not\
322
    deleted from the queue. */\
323
/**************************************************************************/\
324
KT FPRFX ## SeeTopKey(PQT *queue)\
325
{\
326
  return (queue->nnodes == 0 ? KMAX : queue->heap[0].key);\
327
}\
328
\
329
\
330
/*************************************************************************/\
331
/*! This function returns the key of a specific item */\
332
/**************************************************************************/\
333
KT FPRFX ## SeeKey(PQT *queue, VT node)\
334
{\
335
  gk_idx_t *locator;\
336
  KVT *heap;\
337
\
338
  heap    = queue->heap;\
339
  locator = queue->locator;\
340
\
341
  return heap[locator[node]].key;\
342
}\
343
\
344
\
345
/*************************************************************************/\
346
/*! This function returns the first item in a breadth-first traversal of\
347
    the heap whose key is less than maxwgt. This function is here due to\
348
    hMETIS and is not general!*/\
349
/**************************************************************************/\
350
/*\
351
VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts)\
352
{\
353
  gk_idx_t i;\
354
\
355
  if (queue->nnodes == 0)\
356
    return -1;\
357
\
358
  if (maxwgt <= 1000)\
359
    return FPRFX ## SeeTopVal(queue);\
360
\
361
  for (i=0; i<queue->nnodes; i++) {\
362
    if (queue->heap[i].key > 0) {\
363
      if (wgts[queue->heap[i].val] <= maxwgt)\
364
        return queue->heap[i].val;\
365
    }\
366
    else {\
367
      if (queue->heap[i/2].key <= 0)\
368
        break;\
369
    }\
370
  }\
371
\
372
  return queue->heap[0].val;\
373
\
374
}\
375
*/\
376
\
377
\
378
/*************************************************************************/\
379
/*! This functions checks the consistency of the heap */\
380
/**************************************************************************/\
381
int FPRFX ## CheckHeap(PQT *queue)\
382
{\
383
  gk_idx_t i, j;\
384
  size_t nnodes;\
385
  gk_idx_t *locator;\
386
  KVT *heap;\
387
\
388
  heap    = queue->heap;\
389
  locator = queue->locator;\
390
  nnodes  = queue->nnodes;\
391
\
392
  if (nnodes == 0)\
393
    return 1;\
394
\
395
  ASSERT(locator[heap[0].val] == 0);\
396
  for (i=1; i<nnodes; i++) {\
397
    ASSERT(locator[heap[i].val] == i);\
398
    ASSERT(!KEY_LT(heap[i].key, heap[(i-1)/2].key));\
399
  }\
400
  for (i=1; i<nnodes; i++)\
401
    ASSERT(!KEY_LT(heap[i].key, heap[0].key));\
402
\
403
  for (j=i=0; i<queue->maxnodes; i++) {\
404
    if (locator[i] != -1)\
405
      j++;\
406
  }\
407
  ASSERTP(j == nnodes, ("%jd %jd\n", (intmax_t)j, (intmax_t)nnodes));\
408
\
409
  return 1;\
410
}\
411

412

413
#define GK_MKPQUEUE_PROTO(FPRFX, PQT, KT, VT)\
414
  PQT *  FPRFX ## Create(size_t maxnodes);\
415
  void   FPRFX ## Init(PQT *queue, size_t maxnodes);\
416
  void   FPRFX ## Reset(PQT *queue);\
417
  void   FPRFX ## Free(PQT *queue);\
418
  void   FPRFX ## Destroy(PQT *queue);\
419
  size_t FPRFX ## Length(PQT *queue);\
420
  int    FPRFX ## Insert(PQT *queue, VT node, KT key);\
421
  int    FPRFX ## Delete(PQT *queue, VT node);\
422
  void   FPRFX ## Update(PQT *queue, VT node, KT newkey);\
423
  VT     FPRFX ## GetTop(PQT *queue);\
424
  VT     FPRFX ## SeeTopVal(PQT *queue);\
425
  KT     FPRFX ## SeeTopKey(PQT *queue);\
426
  KT     FPRFX ## SeeKey(PQT *queue, VT node);\
427
  VT     FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts);\
428
  int    FPRFX ## CheckHeap(PQT *queue);\
429

430

431
/* This is how these macros are used
432
GK_MKPQUEUE(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t, gk_dkvmalloc, DBL_MAX)
433
GK_MKPQUEUE_PROTO(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t)
434
*/
435

436

437
#endif
438

439
Product

Resources

Company
