1 /*
2 * Copyright (C) 2021 Jakub Kruszona-Zawadzki, Core Technology Sp. z o.o.
3 *
4 * This file is part of MooseFS.
5 *
6 * MooseFS is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2 (only).
9 *
10 * MooseFS is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with MooseFS; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA
18 * or visit http://www.gnu.org/licenses/gpl-2.0.html
19 */
20
21 #include <stdlib.h>
22 #include <inttypes.h>
23
24 #include "massert.h"
25 #include "mfsalloc.h"
26
27 static uint32_t *heap = NULL;
28 static uint32_t heapsize = 0;
29 static uint32_t heapelements = 0;
30
31 #define PARENT(x) (((x)-1)/2)
32 #define CHILD(x) (((x)*2)+1)
33
heap_sort_down(void)34 static inline void heap_sort_down(void) {
35 uint32_t l,r,m;
36 uint32_t pos=0;
37 uint32_t x;
38 while (pos<heapelements) {
39 l = CHILD(pos);
40 r = l+1;
41 if (l>=heapelements) {
42 return;
43 }
44 m = l;
45 if (r<heapelements && heap[r] < heap[l]) {
46 m = r;
47 }
48 if (heap[pos] <= heap[m]) {
49 return;
50 }
51 x = heap[pos];
52 heap[pos] = heap[m];
53 heap[m] = x;
54 pos = m;
55 }
56 }
57
heap_sort_up(void)58 static inline void heap_sort_up(void) {
59 uint32_t pos=heapelements-1;
60 uint32_t p;
61 uint32_t x;
62 while (pos>0) {
63 p = PARENT(pos);
64 if (heap[pos] >= heap[p]) {
65 return;
66 }
67 x = heap[pos];
68 heap[pos] = heap[p];
69 heap[p] = x;
70 pos = p;
71 }
72 }
73
heap_cleanup(void)74 void heap_cleanup(void) {
75 heapelements = 0;
76 }
77
heap_push(uint32_t element)78 void heap_push(uint32_t element) {
79 if (heapelements>=heapsize) {
80 if (heap==NULL) {
81 heapsize = 1024;
82 heap = malloc(sizeof(uint32_t)*heapsize);
83 } else {
84 heapsize <<= 1;
85 heap = mfsrealloc(heap,sizeof(uint32_t)*heapsize);
86 }
87 passert(heap);
88 }
89 heap[heapelements] = element;
90 heapelements++;
91 heap_sort_up();
92 }
93
heap_pop(void)94 uint32_t heap_pop(void) {
95 uint32_t element;
96 if (heapelements==0) {
97 return 0;
98 }
99 element = heap[0];
100 heapelements--;
101 if (heapelements>0) {
102 heap[0] = heap[heapelements];
103 heap_sort_down();
104 }
105 return element;
106 }
107
heap_elements(void)108 uint32_t heap_elements(void) {
109 return heapelements;
110 }
111
heap_term(void)112 void heap_term(void) {
113 if (heap!=NULL) {
114 free(heap);
115 }
116 heap = NULL;
117 heapsize = 0;
118 heapelements = 0;
119 }
120