GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
heap.c
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /* best view tabstop=4
20  */
21 #include <stdio.h>
22 #include <stdlib.h>
23 
24 #include "type.h"
25 #include "heap.h"
26 
27 
28 
29 void dglHeapInit(dglHeap_s * pheap)
30 {
31  pheap->index = 0;
32  pheap->count = 0;
33  pheap->block = 256;
34  pheap->pnode = NULL;
35 }
36 
37 void dglHeapFree(dglHeap_s * pheap, dglHeapCancelItem_fn pfnCancelItem)
38 {
39  int iItem;
40 
41  if (pheap->pnode) {
42  if (pfnCancelItem) {
43  for (iItem = 0; iItem <= pheap->index; iItem++) {
44  pfnCancelItem(pheap, &pheap->pnode[iItem]);
45  }
46  }
47  free(pheap->pnode);
48  }
49  pheap->pnode = NULL;
50 }
51 
53  long key, unsigned char flags, dglHeapData_u value)
54 {
55  long i;
56 
57  if (pheap->index >= pheap->count - 1) {
58  pheap->count += pheap->block;
59  if ((pheap->pnode =
60  realloc(pheap->pnode,
61  sizeof(dglHeapNode_s) * pheap->count)) == NULL)
62  return -1;
63  }
64 
65  i = ++pheap->index;
66 
67  while (i != 1 && key < pheap->pnode[i / 2].key) {
68  pheap->pnode[i] = pheap->pnode[i / 2];
69  i /= 2;
70  }
71 
72  pheap->pnode[i].key = key;
73  pheap->pnode[i].flags = flags;
74  pheap->pnode[i].value = value;
75 
76  return i;
77 }
78 
79 int dglHeapExtractMin(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
80 {
81  dglHeapNode_s temp;
82  long iparent, ichild;
83 
84  if (pheap->index == 0)
85  return 0; /* empty heap */
86 
87  *pnoderet = pheap->pnode[1];
88 
89  temp = pheap->pnode[pheap->index--];
90 
91  iparent = 1;
92  ichild = 2;
93 
94  while (ichild <= pheap->index) {
95  if (ichild < pheap->index &&
96  pheap->pnode[ichild].key > pheap->pnode[ichild + 1].key) {
97  ichild++;
98  }
99  if (temp.key <= pheap->pnode[ichild].key)
100  break;
101 
102  pheap->pnode[iparent] = pheap->pnode[ichild];
103  iparent = ichild;
104  ichild *= 2;
105  }
106  pheap->pnode[iparent] = temp;
107 
108  return 1;
109 }
110 
112  long key, unsigned char flags, dglHeapData_u value)
113 {
114  long i;
115 
116  if (pheap->index >= pheap->count - 1) {
117  pheap->count += pheap->block;
118  if ((pheap->pnode =
119  realloc(pheap->pnode,
120  sizeof(dglHeapNode_s) * pheap->count)) == NULL)
121  return -1;
122  }
123 
124  i = ++pheap->index;
125 
126  while (i != 1 && key > pheap->pnode[i / 2].key) {
127  pheap->pnode[i] = pheap->pnode[i / 2];
128  i /= 2;
129  }
130 
131  pheap->pnode[i].key = key;
132  pheap->pnode[i].flags = flags;
133  pheap->pnode[i].value = value;
134 
135  return i;
136 }
137 
138 int dglHeapExtractMax(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
139 {
140  dglHeapNode_s temp;
141  long iparent, ichild;
142 
143  if (pheap->index == 0)
144  return 0; /* empty heap */
145 
146  *pnoderet = pheap->pnode[1];
147 
148  temp = pheap->pnode[pheap->index--];
149 
150  iparent = 1;
151  ichild = 2;
152 
153  while (ichild <= pheap->index) {
154  if (ichild < pheap->index &&
155  pheap->pnode[ichild].key < pheap->pnode[ichild + 1].key) {
156  ichild++;
157  }
158  if (temp.key >= pheap->pnode[ichild].key)
159  break;
160 
161  pheap->pnode[iparent] = pheap->pnode[ichild];
162  iparent = ichild;
163  ichild *= 2;
164  }
165  pheap->pnode[iparent] = temp;
166 
167  return 1;
168 }
dglHeapNode_s * pnode
Definition: heap.h:50
long key
Definition: heap.h:38
dglHeapData_u value
Definition: heap.h:39
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
Definition: heap.c:37
void(* dglHeapCancelItem_fn)(dglHeap_s *pheap, dglHeapNode_s *pitem)
Definition: heap.h:57
Definition: heap.h:44
void dglHeapInit(dglHeap_s *pheap)
Definition: heap.c:29
void free(void *)
#define NULL
Definition: ccmath.h:32
long index
Definition: heap.h:47
int dglHeapInsertMax(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:111
long count
Definition: heap.h:48
unsigned char flags
Definition: heap.h:40
int dglHeapInsertMin(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:52
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:79
long block
Definition: heap.h:49
int dglHeapExtractMax(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:138