Whamcloud - gitweb
LU-6245 libcfs: remove typedefs in libcfs source code
[fs/lustre-release.git] / libcfs / libcfs / heap.c
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 only,
8  * as published by the Free Software Foundation.
9
10  * This program 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 version 2 for more details.  A copy is
14  * included in the COPYING file that accompanied this code.
15
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (c) 2011 Intel Corporation
24  */
25 /*
26  * libcfs/libcfs/heap.c
27  *
28  * Author: Eric Barton  <eeb@whamcloud.com>
29  *         Liang Zhen   <liang@whamcloud.com>
30  */
31 /** \addtogroup heap
32  *
33  * @{
34  */
35
36 #define DEBUG_SUBSYSTEM S_LNET
37
38 #include <libcfs/libcfs.h>
39
40 #define CBH_ALLOC(ptr, h)                                               \
41 do {                                                                    \
42         if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)                      \
43                 LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid, \
44                                      CBH_NOB, GFP_ATOMIC);              \
45         else                                                            \
46                 LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid,     \
47                                  CBH_NOB);                              \
48 } while (0)
49
50 #define CBH_FREE(ptr)   LIBCFS_FREE(ptr, CBH_NOB)
51
52 /**
53  * Grows the capacity of a binary heap so that it can handle a larger number of
54  * \e struct cfs_binheap_node objects.
55  *
56  * \param[in] h The binary heap
57  *
58  * \retval 0       Successfully grew the heap
59  * \retval -ENOMEM OOM error
60  */
61 static int
62 cfs_binheap_grow(struct cfs_binheap *h)
63 {
64         struct cfs_binheap_node ***frag1 = NULL;
65         struct cfs_binheap_node  **frag2;
66         int hwm = h->cbh_hwm;
67
68         /* need a whole new chunk of pointers */
69         LASSERT((h->cbh_hwm & CBH_MASK) == 0);
70
71         if (hwm == 0) {
72                 /* first use of single indirect */
73                 CBH_ALLOC(h->cbh_elements1, h);
74                 if (h->cbh_elements1 == NULL)
75                         return -ENOMEM;
76
77                 goto out;
78         }
79
80         hwm -= CBH_SIZE;
81         if (hwm < CBH_SIZE * CBH_SIZE) {
82                 /* not filled double indirect */
83                 CBH_ALLOC(frag2, h);
84                 if (frag2 == NULL)
85                         return -ENOMEM;
86
87                 if (hwm == 0) {
88                         /* first use of double indirect */
89                         CBH_ALLOC(h->cbh_elements2, h);
90                         if (h->cbh_elements2 == NULL) {
91                                 CBH_FREE(frag2);
92                                 return -ENOMEM;
93                         }
94                 }
95
96                 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
97                 goto out;
98         }
99
100         hwm -= CBH_SIZE * CBH_SIZE;
101 #if (CBH_SHIFT * 3 < 32)
102         if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
103                 /* filled triple indirect */
104                 return -ENOMEM;
105         }
106 #endif
107         CBH_ALLOC(frag2, h);
108         if (frag2 == NULL)
109                 return -ENOMEM;
110
111         if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
112                 /* first use of this 2nd level index */
113                 CBH_ALLOC(frag1, h);
114                 if (frag1 == NULL) {
115                         CBH_FREE(frag2);
116                         return -ENOMEM;
117                 }
118         }
119
120         if (hwm == 0) {
121                 /* first use of triple indirect */
122                 CBH_ALLOC(h->cbh_elements3, h);
123                 if (h->cbh_elements3 == NULL) {
124                         CBH_FREE(frag2);
125                         CBH_FREE(frag1);
126                         return -ENOMEM;
127                 }
128         }
129
130         if (frag1 != NULL) {
131                 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
132                 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
133         } else {
134                 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
135                 LASSERT(frag1 != NULL);
136         }
137
138         frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
139
140  out:
141         h->cbh_hwm += CBH_SIZE;
142         return 0;
143 }
144
145 /**
146  * Creates and initializes a binary heap instance.
147  *
148  * \param[in] ops   The operations to be used
149  * \param[in] flags The heap flags
150  * \parm[in]  count The initial heap capacity in # of elements
151  * \param[in] arg   An optional private argument
152  * \param[in] cptab The CPT table this heap instance will operate over
153  * \param[in] cptid The CPT id of \a cptab this heap instance will operate over
154  *
155  * \retval valid-pointer A newly-created and initialized binary heap object
156  * \retval NULL          error
157  */
158 struct cfs_binheap *
159 cfs_binheap_create(struct cfs_binheap_ops *ops, unsigned int flags,
160                    unsigned count, void *arg, struct cfs_cpt_table *cptab,
161                    int cptid)
162 {
163         struct cfs_binheap *h;
164
165         LASSERT(ops != NULL);
166         LASSERT(ops->hop_compare != NULL);
167         LASSERT(cptab != NULL);
168         LASSERT(cptid == CFS_CPT_ANY ||
169                (cptid >= 0 && cptid < cptab->ctb_nparts));
170
171         LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
172         if (h == NULL)
173                 return NULL;
174
175         h->cbh_ops        = ops;
176         h->cbh_nelements  = 0;
177         h->cbh_hwm        = 0;
178         h->cbh_private    = arg;
179         h->cbh_flags      = flags & (~CBH_FLAG_ATOMIC_GROW);
180         h->cbh_cptab      = cptab;
181         h->cbh_cptid      = cptid;
182
183         while (h->cbh_hwm < count) { /* preallocate */
184                 if (cfs_binheap_grow(h) != 0) {
185                         cfs_binheap_destroy(h);
186                         return NULL;
187                 }
188         }
189
190         h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
191
192         return h;
193 }
194 EXPORT_SYMBOL(cfs_binheap_create);
195
196 /**
197  * Releases all resources associated with a binary heap instance.
198  *
199  * Deallocates memory for all indirection levels and the binary heap object
200  * itself.
201  *
202  * \param[in] h The binary heap object
203  */
204 void
205 cfs_binheap_destroy(struct cfs_binheap *h)
206 {
207         int idx0;
208         int idx1;
209         int n;
210
211         LASSERT(h != NULL);
212
213         n = h->cbh_hwm;
214
215         if (n > 0) {
216                 CBH_FREE(h->cbh_elements1);
217                 n -= CBH_SIZE;
218         }
219
220         if (n > 0) {
221                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
222                         CBH_FREE(h->cbh_elements2[idx0]);
223                         n -= CBH_SIZE;
224                 }
225
226                 CBH_FREE(h->cbh_elements2);
227         }
228
229         if (n > 0) {
230                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
231
232                         for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
233                                 CBH_FREE(h->cbh_elements3[idx0][idx1]);
234                                 n -= CBH_SIZE;
235                         }
236
237                         CBH_FREE(h->cbh_elements3[idx0]);
238                 }
239
240                 CBH_FREE(h->cbh_elements3);
241         }
242
243         LIBCFS_FREE(h, sizeof(*h));
244 }
245 EXPORT_SYMBOL(cfs_binheap_destroy);
246
247 /**
248  * Obtains a double pointer to a heap element, given its index into the binary
249  * tree.
250  *
251  * \param[in] h   The binary heap instance
252  * \param[in] idx The requested node's index
253  *
254  * \retval valid-pointer A double pointer to a heap pointer entry
255  */
256 static struct cfs_binheap_node **
257 cfs_binheap_pointer(struct cfs_binheap *h, unsigned int idx)
258 {
259         if (idx < CBH_SIZE)
260                 return &(h->cbh_elements1[idx]);
261
262         idx -= CBH_SIZE;
263         if (idx < CBH_SIZE * CBH_SIZE)
264                 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
265
266         idx -= CBH_SIZE * CBH_SIZE;
267         return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
268                                  [(idx >> CBH_SHIFT) & CBH_MASK]\
269                                  [idx & CBH_MASK]);
270 }
271
272 /**
273  * Obtains a pointer to a heap element, given its index into the binary tree.
274  *
275  * \param[in] h   The binary heap
276  * \param[in] idx The requested node's index
277  *
278  * \retval valid-pointer The requested heap node
279  * \retval NULL          Supplied index is out of bounds
280  */
281 struct cfs_binheap_node *
282 cfs_binheap_find(struct cfs_binheap *h, unsigned int idx)
283 {
284         if (idx >= h->cbh_nelements)
285                 return NULL;
286
287         return *cfs_binheap_pointer(h, idx);
288 }
289 EXPORT_SYMBOL(cfs_binheap_find);
290
291 /**
292  * Moves a node upwards, towards the root of the binary tree.
293  *
294  * \param[in] h The heap
295  * \param[in] e The node
296  *
297  * \retval 1 The position of \a e in the tree was changed at least once
298  * \retval 0 The position of \a e in the tree was not changed
299  */
300 static int
301 cfs_binheap_bubble(struct cfs_binheap *h, struct cfs_binheap_node *e)
302 {
303         unsigned int         cur_idx = e->chn_index;
304         struct cfs_binheap_node **cur_ptr;
305         unsigned int         parent_idx;
306         struct cfs_binheap_node **parent_ptr;
307         int                  did_sth = 0;
308
309         cur_ptr = cfs_binheap_pointer(h, cur_idx);
310         LASSERT(*cur_ptr == e);
311
312         while (cur_idx > 0) {
313                 parent_idx = (cur_idx - 1) >> 1;
314
315                 parent_ptr = cfs_binheap_pointer(h, parent_idx);
316                 LASSERT((*parent_ptr)->chn_index == parent_idx);
317
318                 if (h->cbh_ops->hop_compare(*parent_ptr, e))
319                         break;
320
321                 (*parent_ptr)->chn_index = cur_idx;
322                 *cur_ptr = *parent_ptr;
323                 cur_ptr = parent_ptr;
324                 cur_idx = parent_idx;
325                 did_sth = 1;
326         }
327
328         e->chn_index = cur_idx;
329         *cur_ptr = e;
330
331         return did_sth;
332 }
333
334 /**
335  * Moves a node downwards, towards the last level of the binary tree.
336  *
337  * \param[in] h The heap
338  * \param[in] e The node
339  *
340  * \retval 1 The position of \a e in the tree was changed at least once
341  * \retval 0 The position of \a e in the tree was not changed
342  */
343 static int
344 cfs_binheap_sink(struct cfs_binheap *h, struct cfs_binheap_node *e)
345 {
346         unsigned int         n = h->cbh_nelements;
347         unsigned int         child_idx;
348         struct cfs_binheap_node **child_ptr;
349         struct cfs_binheap_node  *child;
350         unsigned int         child2_idx;
351         struct cfs_binheap_node **child2_ptr;
352         struct cfs_binheap_node  *child2;
353         unsigned int         cur_idx;
354         struct cfs_binheap_node **cur_ptr;
355         int                  did_sth = 0;
356
357         cur_idx = e->chn_index;
358         cur_ptr = cfs_binheap_pointer(h, cur_idx);
359         LASSERT(*cur_ptr == e);
360
361         while (cur_idx < n) {
362                 child_idx = (cur_idx << 1) + 1;
363                 if (child_idx >= n)
364                         break;
365
366                 child_ptr = cfs_binheap_pointer(h, child_idx);
367                 child = *child_ptr;
368
369                 child2_idx = child_idx + 1;
370                 if (child2_idx < n) {
371                         child2_ptr = cfs_binheap_pointer(h, child2_idx);
372                         child2 = *child2_ptr;
373
374                         if (h->cbh_ops->hop_compare(child2, child)) {
375                                 child_idx = child2_idx;
376                                 child_ptr = child2_ptr;
377                                 child = child2;
378                         }
379                 }
380
381                 LASSERT(child->chn_index == child_idx);
382
383                 if (h->cbh_ops->hop_compare(e, child))
384                         break;
385
386                 child->chn_index = cur_idx;
387                 *cur_ptr = child;
388                 cur_ptr = child_ptr;
389                 cur_idx = child_idx;
390                 did_sth = 1;
391         }
392
393         e->chn_index = cur_idx;
394         *cur_ptr = e;
395
396         return did_sth;
397 }
398
399 /**
400  * Sort-inserts a node into the binary heap.
401  *
402  * \param[in] h The heap
403  * \param[in] e The node
404  *
405  * \retval 0    Element inserted successfully
406  * \retval != 0 error
407  */
408 int
409 cfs_binheap_insert(struct cfs_binheap *h, struct cfs_binheap_node *e)
410 {
411         struct cfs_binheap_node **new_ptr;
412         unsigned int         new_idx = h->cbh_nelements;
413         int                  rc;
414
415         if (new_idx == h->cbh_hwm) {
416                 rc = cfs_binheap_grow(h);
417                 if (rc != 0)
418                         return rc;
419         }
420
421         if (h->cbh_ops->hop_enter) {
422                 rc = h->cbh_ops->hop_enter(h, e);
423                 if (rc != 0)
424                         return rc;
425         }
426
427         e->chn_index = new_idx;
428         new_ptr = cfs_binheap_pointer(h, new_idx);
429         h->cbh_nelements++;
430         *new_ptr = e;
431
432         cfs_binheap_bubble(h, e);
433
434         return 0;
435 }
436 EXPORT_SYMBOL(cfs_binheap_insert);
437
438 /**
439  * Removes a node from the binary heap.
440  *
441  * \param[in] h The heap
442  * \param[in] e The node
443  */
444 void
445 cfs_binheap_remove(struct cfs_binheap *h, struct cfs_binheap_node *e)
446 {
447         unsigned int         n = h->cbh_nelements;
448         unsigned int         cur_idx = e->chn_index;
449         struct cfs_binheap_node **cur_ptr;
450         struct cfs_binheap_node  *last;
451
452         LASSERT(cur_idx != CBH_POISON);
453         LASSERT(cur_idx < n);
454
455         cur_ptr = cfs_binheap_pointer(h, cur_idx);
456         LASSERT(*cur_ptr == e);
457
458         n--;
459         last = *cfs_binheap_pointer(h, n);
460         h->cbh_nelements = n;
461         if (last == e)
462                 return;
463
464         last->chn_index = cur_idx;
465         *cur_ptr = last;
466         cfs_binheap_relocate(h, *cur_ptr);
467
468         e->chn_index = CBH_POISON;
469         if (h->cbh_ops->hop_exit)
470                 h->cbh_ops->hop_exit(h, e);
471 }
472 EXPORT_SYMBOL(cfs_binheap_remove);
473
474 /**
475  * Relocate a node in the binary heap.
476  * Should be called whenever a node's values
477  * which affects its ranking are changed.
478  *
479  * \param[in] h The heap
480  * \param[in] e The node
481  */
482 void
483 cfs_binheap_relocate(struct cfs_binheap *h, struct cfs_binheap_node *e)
484 {
485         if (!cfs_binheap_bubble(h, e))
486                 cfs_binheap_sink(h, e);
487 }
488 EXPORT_SYMBOL(cfs_binheap_relocate);
489 /** @} heap */