GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-535c39c9fc
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 void dglHeapInit(dglHeap_s *pheap)
28 {
29  pheap->index = 0;
30  pheap->count = 0;
31  pheap->block = 256;
32  pheap->pnode = NULL;
33 }
34 
35 void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
36 {
37  int iItem;
38 
39  if (pheap->pnode) {
40  if (pfnCancelItem) {
41  for (iItem = 0; iItem <= pheap->index; iItem++) {
42  pfnCancelItem(pheap, &pheap->pnode[iItem]);
43  }
44  }
45  free(pheap->pnode);
46  }
47  pheap->pnode = NULL;
48 }
49 
50 int dglHeapInsertMin(dglHeap_s *pheap, long key, unsigned char flags,
51  dglHeapData_u value)
52 {
53  long i;
54 
55  if (pheap->index >= pheap->count - 1) {
56  pheap->count += pheap->block;
57  if ((pheap->pnode = realloc(pheap->pnode, sizeof(dglHeapNode_s) *
58  pheap->count)) == NULL)
59  return -1;
60  }
61 
62  i = ++pheap->index;
63 
64  while (i != 1 && key < pheap->pnode[i / 2].key) {
65  pheap->pnode[i] = pheap->pnode[i / 2];
66  i /= 2;
67  }
68 
69  pheap->pnode[i].key = key;
70  pheap->pnode[i].flags = flags;
71  pheap->pnode[i].value = value;
72 
73  return i;
74 }
75 
77 {
78  dglHeapNode_s temp;
79  long iparent, ichild;
80 
81  if (pheap->index == 0)
82  return 0; /* empty heap */
83 
84  *pnoderet = pheap->pnode[1];
85 
86  temp = pheap->pnode[pheap->index--];
87 
88  iparent = 1;
89  ichild = 2;
90 
91  while (ichild <= pheap->index) {
92  if (ichild < pheap->index &&
93  pheap->pnode[ichild].key > pheap->pnode[ichild + 1].key) {
94  ichild++;
95  }
96  if (temp.key <= pheap->pnode[ichild].key)
97  break;
98 
99  pheap->pnode[iparent] = pheap->pnode[ichild];
100  iparent = ichild;
101  ichild *= 2;
102  }
103  pheap->pnode[iparent] = temp;
104 
105  return 1;
106 }
107 
108 int dglHeapInsertMax(dglHeap_s *pheap, long key, unsigned char flags,
109  dglHeapData_u value)
110 {
111  long i;
112 
113  if (pheap->index >= pheap->count - 1) {
114  pheap->count += pheap->block;
115  if ((pheap->pnode = realloc(pheap->pnode, sizeof(dglHeapNode_s) *
116  pheap->count)) == NULL)
117  return -1;
118  }
119 
120  i = ++pheap->index;
121 
122  while (i != 1 && key > pheap->pnode[i / 2].key) {
123  pheap->pnode[i] = pheap->pnode[i / 2];
124  i /= 2;
125  }
126 
127  pheap->pnode[i].key = key;
128  pheap->pnode[i].flags = flags;
129  pheap->pnode[i].value = value;
130 
131  return i;
132 }
133 
135 {
136  dglHeapNode_s temp;
137  long iparent, ichild;
138 
139  if (pheap->index == 0)
140  return 0; /* empty heap */
141 
142  *pnoderet = pheap->pnode[1];
143 
144  temp = pheap->pnode[pheap->index--];
145 
146  iparent = 1;
147  ichild = 2;
148 
149  while (ichild <= pheap->index) {
150  if (ichild < pheap->index &&
151  pheap->pnode[ichild].key < pheap->pnode[ichild + 1].key) {
152  ichild++;
153  }
154  if (temp.key >= pheap->pnode[ichild].key)
155  break;
156 
157  pheap->pnode[iparent] = pheap->pnode[ichild];
158  iparent = ichild;
159  ichild *= 2;
160  }
161  pheap->pnode[iparent] = temp;
162 
163  return 1;
164 }
#define NULL
Definition: ccmath.h:32
void dglHeapInit(dglHeap_s *pheap)
Definition: heap.c:27
int dglHeapInsertMin(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:50
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
Definition: heap.c:35
int dglHeapExtractMax(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:134
int dglHeapInsertMax(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:108
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:76
void(* dglHeapCancelItem_fn)(dglHeap_s *pheap, dglHeapNode_s *pitem)
Definition: heap.h:53
void free(void *)
long key
Definition: heap.h:35
unsigned char flags
Definition: heap.h:37
dglHeapData_u value
Definition: heap.h:36
Definition: heap.h:41
dglHeapNode_s * pnode
Definition: heap.h:47
long index
Definition: heap.h:43
long block
Definition: heap.h:46
long count
Definition: heap.h:45