1 /***************************************************************************
2 * gh_heap.c -- heap based priority queue. *
3 * *
4 ***********************IMPORTANT NSOCK LICENSE TERMS***********************
5 * *
6 * The nsock parallel socket event library is (C) 1999-2020 Insecure.Com *
7 * LLC This library is free software; you may redistribute and/or *
8 * modify it under the terms of the GNU General Public License as *
9 * published by the Free Software Foundation; Version 2. This guarantees *
10 * your right to use, modify, and redistribute this software under certain *
11 * conditions. If this license is unacceptable to you, Insecure.Com LLC *
12 * may be willing to sell alternative licenses (contact *
13 * sales@insecure.com ). *
14 * *
15 * As a special exception to the GPL terms, Insecure.Com LLC grants *
16 * permission to link the code of this program with any version of the *
17 * OpenSSL library which is distributed under a license identical to that *
18 * listed in the included docs/licenses/OpenSSL.txt file, and distribute *
19 * linked combinations including the two. You must obey the GNU GPL in all *
20 * respects for all of the code used other than OpenSSL. If you modify *
21 * this file, you may extend this exception to your version of the file, *
22 * but you are not obligated to do so. *
23 * *
24 * If you received these files with a written license agreement stating *
25 * terms other than the (GPL) terms above, then that alternative license *
26 * agreement takes precedence over this comment. *
27 * *
28 * Source is provided to this software because we believe users have a *
29 * right to know exactly what a program is going to do before they run it. *
30 * This also allows you to audit the software for security holes. *
31 * *
32 * Source code also allows you to port Nmap to new platforms, fix bugs, *
33 * and add new features. You are highly encouraged to send your changes *
34 * to the dev@nmap.org mailing list for possible incorporation into the *
35 * main distribution. By sending these changes to Fyodor or one of the *
36 * Insecure.Org development mailing lists, or checking them into the Nmap *
37 * source code repository, it is understood (unless you specify otherwise) *
38 * that you are offering the Nmap Project (Insecure.Com LLC) the *
39 * unlimited, non-exclusive right to reuse, modify, and relicense the *
40 * code. Nmap will always be available Open Source, but this is important *
41 * because the inability to relicense code has caused devastating problems *
42 * for other Free Software projects (such as KDE and NASM). We also *
43 * occasionally relicense the code to third parties as discussed above. *
44 * If you wish to specify special license conditions of your *
45 * contributions, just say so when you send them. *
46 * *
47 * This program is distributed in the hope that it will be useful, but *
48 * WITHOUT ANY WARRANTY; without even the implied warranty of *
49 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
50 * General Public License v2.0 for more details *
51 * (http://www.gnu.org/licenses/gpl-2.0.html). *
52 * *
53 ***************************************************************************/
54
55 /* $Id: gh_heap.c 38071 2020-10-02 05:02:05Z fyodor $ */
56
57 #ifdef HAVE_CONFIG_H
58 #include "nsock_config.h"
59 #include "nbase_config.h"
60 #endif
61
62 #ifdef WIN32
63 #include "nbase_winconfig.h"
64 #endif
65
66 #include <nbase.h>
67 #include "gh_heap.h"
68
69 #define GH_SLOTS 128
70
71
hnode_ptr(gh_heap_t * heap,unsigned int index)72 static gh_hnode_t **hnode_ptr(gh_heap_t *heap, unsigned int index) {
73 assert(index <= heap->count);
74 return &(heap->slots[index]);
75 }
76
gh_heap_find(gh_heap_t * heap,unsigned int index)77 gh_hnode_t *gh_heap_find(gh_heap_t *heap, unsigned int index) {
78 if (index >= heap->count)
79 return NULL;
80
81 return *hnode_ptr(heap, index);
82 }
83
hnode_up(gh_heap_t * heap,gh_hnode_t * hnode)84 static int hnode_up(gh_heap_t *heap, gh_hnode_t *hnode)
85 {
86 unsigned int cur_idx = hnode->index;
87 gh_hnode_t **cur_ptr = hnode_ptr(heap, cur_idx);
88 unsigned int parent_idx;
89 gh_hnode_t **parent_ptr;
90 int action = 0;
91
92 assert(*cur_ptr == hnode);
93
94 while (cur_idx > 0) {
95 parent_idx = (cur_idx - 1) >> 1;
96
97 parent_ptr = hnode_ptr(heap, parent_idx);
98 assert((*parent_ptr)->index == parent_idx);
99
100 if (heap->cmp_op(*parent_ptr, hnode))
101 break;
102
103 (*parent_ptr)->index = cur_idx;
104 *cur_ptr = *parent_ptr;
105 cur_ptr = parent_ptr;
106 cur_idx = parent_idx;
107 action = 1;
108 }
109
110 hnode->index = cur_idx;
111 *cur_ptr = hnode;
112
113 return action;
114 }
115
hnode_down(gh_heap_t * heap,gh_hnode_t * hnode)116 static int hnode_down(gh_heap_t *heap, gh_hnode_t *hnode)
117 {
118 unsigned int count = heap->count;
119 unsigned int ch1_idx, ch2_idx, cur_idx;
120 gh_hnode_t **ch1_ptr, **ch2_ptr, **cur_ptr;
121 gh_hnode_t *ch1, *ch2;
122 int action = 0;
123
124 cur_idx = hnode->index;
125 cur_ptr = hnode_ptr(heap, cur_idx);
126 assert(*cur_ptr == hnode);
127
128 while (cur_idx < count) {
129 ch1_idx = (cur_idx << 1) + 1;
130 if (ch1_idx >= count)
131 break;
132
133 ch1_ptr = hnode_ptr(heap, ch1_idx);
134 ch1 = *ch1_ptr;
135
136 ch2_idx = ch1_idx + 1;
137 if (ch2_idx < count) {
138 ch2_ptr = hnode_ptr(heap, ch2_idx);
139 ch2 = *ch2_ptr;
140
141 if (heap->cmp_op(ch2, ch1)) {
142 ch1_idx = ch2_idx;
143 ch1_ptr = ch2_ptr;
144 ch1 = ch2;
145 }
146 }
147
148 assert(ch1->index == ch1_idx);
149
150 if (heap->cmp_op(hnode, ch1))
151 break;
152
153 ch1->index = cur_idx;
154 *cur_ptr = ch1;
155 cur_ptr = ch1_ptr;
156 cur_idx = ch1_idx;
157 action = 1;
158 }
159
160 hnode->index = cur_idx;
161 *cur_ptr = hnode;
162
163 return action;
164 }
165
heap_grow(gh_heap_t * heap)166 static int heap_grow(gh_heap_t *heap) {
167 int newsize;
168
169 /* Do we really need to grow? */
170 assert(heap->count == heap->highwm);
171
172 newsize = heap->count + GH_SLOTS;
173 heap->slots = (gh_hnode_t **)safe_realloc(heap->slots,
174 newsize * sizeof(gh_hnode_t *));
175 heap->highwm += GH_SLOTS;
176 return 0;
177 }
178
gh_heap_init(gh_heap_t * heap,gh_heap_cmp_t cmp_op)179 int gh_heap_init(gh_heap_t *heap, gh_heap_cmp_t cmp_op) {
180 int rc;
181
182 if (!cmp_op)
183 return -1;
184
185 heap->cmp_op = cmp_op;
186 heap->count = 0;
187 heap->highwm = 0;
188 heap->slots = NULL;
189
190 rc = heap_grow(heap);
191 if (rc)
192 gh_heap_free(heap);
193
194 return rc;
195 }
196
gh_heap_free(gh_heap_t * heap)197 void gh_heap_free(gh_heap_t *heap) {
198 if (heap->highwm) {
199 assert(heap->slots);
200 free(heap->slots);
201 }
202 memset(heap, 0, sizeof(gh_heap_t));
203 }
204
gh_heap_push(gh_heap_t * heap,gh_hnode_t * hnode)205 int gh_heap_push(gh_heap_t *heap, gh_hnode_t *hnode) {
206 gh_hnode_t **new_ptr;
207 unsigned int new_index = heap->count;
208
209 assert(!gh_hnode_is_valid(hnode));
210
211 if (new_index == heap->highwm)
212 heap_grow(heap);
213
214 hnode->index = new_index;
215 new_ptr = hnode_ptr(heap, new_index);
216 heap->count++;
217 *new_ptr = hnode;
218
219 hnode_up(heap, hnode);
220 return 0;
221 }
222
gh_heap_remove(gh_heap_t * heap,gh_hnode_t * hnode)223 int gh_heap_remove(gh_heap_t *heap, gh_hnode_t *hnode)
224 {
225 unsigned int count = heap->count;
226 unsigned int cur_idx = hnode->index;
227 gh_hnode_t **cur_ptr;
228 gh_hnode_t *last;
229
230 assert(gh_hnode_is_valid(hnode));
231 assert(cur_idx < count);
232
233 cur_ptr = hnode_ptr(heap, cur_idx);
234 assert(*cur_ptr == hnode);
235
236 count--;
237 last = *hnode_ptr(heap, count);
238 heap->count = count;
239 if (last == hnode)
240 return 0;
241
242 last->index = cur_idx;
243 *cur_ptr = last;
244 if (!hnode_up(heap, *cur_ptr))
245 hnode_down(heap, *cur_ptr);
246
247 gh_hnode_invalidate(hnode);
248 return 0;
249 }
250