1 /* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> 2 3 This program is free software: you can redistribute it and/or modify 4 it under the terms of the GNU General Public License as published by 5 the Free Software Foundation, either version 3 of the License, or 6 (at your option) any later version. 7 8 This program is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License 14 along with this program. If not, see <https://www.gnu.org/licenses/>. 15 */ 16 17 #pragma once 18 19 struct heap_val { 20 int pos; 21 }; 22 23 typedef struct heap_val heap_val_t; 24 25 struct heap { 26 int num; /* Number of elements */ 27 int max_size; /* Size of allocated memory */ 28 int (*cmp)(void *, void *); 29 heap_val_t **data; 30 }; /* Array follows */ 31 32 #define INITIAL_HEAP_SIZE 512 /* initial heap size */ 33 #define HEAP_INCREASE_STEP 2 /* multiplier for each inflation, keep conservative */ 34 #define HEAP_DECREASE_THRESHOLD 2 /* threshold for deflation, keep conservative */ 35 #define HELEMENT(h,num) ((h)->data + (num)) 36 #define HHEAD(h) HELEMENT((h), 1) 37 #define EMPTY_HEAP(h) ((h)->num == 0) /* h->num == 0 */ 38 39 int heap_init(struct heap *, int (*cmp)(void *, void *), int); 40 void heap_deinit(struct heap *); 41 42 void heap_delmin(struct heap *); 43 int heap_insert(struct heap *, heap_val_t *); 44 int heap_find(struct heap *, heap_val_t *); 45 void heap_delete(struct heap *, int); 46 void heap_replace(struct heap *h, int pos, heap_val_t *); 47