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