1 /**
2 * collectd - src/utils_heap.c
3 * Copyright (C) 2009 Florian octo Forster
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 *
23 * Authors:
24 * Florian octo Forster <octo at collectd.org>
25 **/
26
27 #include "collectd.h"
28
29 #include <assert.h>
30 #include <errno.h>
31 #include <pthread.h>
32 #include <stdlib.h>
33
34 #include "utils/heap/heap.h"
35
36 struct c_heap_s {
37 pthread_mutex_t lock;
38 int (*compare)(const void *, const void *);
39
40 void **list;
41 size_t list_len; /* # entries used */
42 size_t list_size; /* # entries allocated */
43 };
44
45 enum reheap_direction { DIR_UP, DIR_DOWN };
46
reheap(c_heap_t * h,size_t root,enum reheap_direction dir)47 static void reheap(c_heap_t *h, size_t root, enum reheap_direction dir) {
48 size_t left;
49 size_t right;
50 size_t min;
51 int status;
52
53 /* Calculate the positions of the children */
54 left = (2 * root) + 1;
55 if (left >= h->list_len)
56 left = 0;
57
58 right = (2 * root) + 2;
59 if (right >= h->list_len)
60 right = 0;
61
62 /* Check which one of the children is smaller. */
63 if ((left == 0) && (right == 0))
64 return;
65 else if (left == 0)
66 min = right;
67 else if (right == 0)
68 min = left;
69 else {
70 status = h->compare(h->list[left], h->list[right]);
71 if (status > 0)
72 min = right;
73 else
74 min = left;
75 }
76
77 status = h->compare(h->list[root], h->list[min]);
78 if (status <= 0) {
79 /* We didn't need to change anything, so the rest of the tree should be
80 * okay now. */
81 return;
82 } else /* if (status > 0) */
83 {
84 void *tmp;
85
86 tmp = h->list[root];
87 h->list[root] = h->list[min];
88 h->list[min] = tmp;
89 }
90
91 if ((dir == DIR_UP) && (root == 0))
92 return;
93
94 if (dir == DIR_UP)
95 reheap(h, (root - 1) / 2, dir);
96 else if (dir == DIR_DOWN)
97 reheap(h, min, dir);
98 } /* void reheap */
99
c_heap_create(int (* compare)(const void *,const void *))100 c_heap_t *c_heap_create(int (*compare)(const void *, const void *)) {
101 c_heap_t *h;
102
103 if (compare == NULL)
104 return NULL;
105
106 h = calloc(1, sizeof(*h));
107 if (h == NULL)
108 return NULL;
109
110 pthread_mutex_init(&h->lock, /* attr = */ NULL);
111 h->compare = compare;
112
113 h->list = NULL;
114 h->list_len = 0;
115 h->list_size = 0;
116
117 return h;
118 } /* c_heap_t *c_heap_create */
119
c_heap_destroy(c_heap_t * h)120 void c_heap_destroy(c_heap_t *h) {
121 if (h == NULL)
122 return;
123
124 h->list_len = 0;
125 h->list_size = 0;
126 free(h->list);
127 h->list = NULL;
128
129 pthread_mutex_destroy(&h->lock);
130
131 free(h);
132 } /* void c_heap_destroy */
133
c_heap_insert(c_heap_t * h,void * ptr)134 int c_heap_insert(c_heap_t *h, void *ptr) {
135 size_t index;
136
137 if ((h == NULL) || (ptr == NULL))
138 return -EINVAL;
139
140 pthread_mutex_lock(&h->lock);
141
142 assert(h->list_len <= h->list_size);
143 if (h->list_len == h->list_size) {
144 void **tmp;
145
146 tmp = realloc(h->list, (h->list_size + 16) * sizeof(*h->list));
147 if (tmp == NULL) {
148 pthread_mutex_unlock(&h->lock);
149 return -ENOMEM;
150 }
151
152 h->list = tmp;
153 h->list_size += 16;
154 }
155
156 /* Insert the new node as a leaf. */
157 index = h->list_len;
158 h->list[index] = ptr;
159 h->list_len++;
160
161 /* Reorganize the heap from bottom up. */
162 reheap(h, /* parent of this node = */ (index - 1) / 2, DIR_UP);
163
164 pthread_mutex_unlock(&h->lock);
165 return 0;
166 } /* int c_heap_insert */
167
c_heap_get_root(c_heap_t * h)168 void *c_heap_get_root(c_heap_t *h) {
169 void *ret = NULL;
170
171 if (h == NULL)
172 return NULL;
173
174 pthread_mutex_lock(&h->lock);
175
176 if (h->list_len == 0) {
177 pthread_mutex_unlock(&h->lock);
178 return NULL;
179 } else if (h->list_len == 1) {
180 ret = h->list[0];
181 h->list[0] = NULL;
182 h->list_len = 0;
183 } else /* if (h->list_len > 1) */
184 {
185 ret = h->list[0];
186 h->list[0] = h->list[h->list_len - 1];
187 h->list[h->list_len - 1] = NULL;
188 h->list_len--;
189
190 reheap(h, /* root = */ 0, DIR_DOWN);
191 }
192
193 /* free some memory */
194 if ((h->list_len + 32) < h->list_size) {
195 void **tmp;
196
197 tmp = realloc(h->list, (h->list_len + 16) * sizeof(*h->list));
198 if (tmp != NULL) {
199 h->list = tmp;
200 h->list_size = h->list_len + 16;
201 }
202 }
203
204 pthread_mutex_unlock(&h->lock);
205
206 return ret;
207 } /* void *c_heap_get_root */
208