From 8beee9d0ff74f78fc5b072d1cf98f55d927dcdbe Mon Sep 17 00:00:00 2001 From: Li Xi Date: Sun, 28 Jul 2013 08:48:47 -0700 Subject: [PATCH 1/1] LU-3494 libcfs: Add relocation function to libcfs heap When changing the values of the node in the heap which might affect its ranking, we have to remove the node from the heap, change the values and then insert the node into the heap again. The process of inserting into the heap might fail because of memory insufficiency. Sometimes, it is not convienient and efficient for a caller to handle such kind of failure. This patch adds a new function to do the job. Signed-off-by: Li Xi Change-Id: I31ce530d750341f6479470ba61457d9ed03afed3 Reviewed-on: http://review.whamcloud.com/6743 Tested-by: Hudson Tested-by: Maloo Reviewed-by: Bobbie Lind Reviewed-by: Liang Zhen Reviewed-by: Oleg Drokin --- libcfs/include/libcfs/libcfs_heap.h | 1 + libcfs/libcfs/heap.c | 18 ++++++++++++++++-- 2 files changed, 17 insertions(+), 2 deletions(-) diff --git a/libcfs/include/libcfs/libcfs_heap.h b/libcfs/include/libcfs/libcfs_heap.h index 40d4eda..8a9a855 100644 --- a/libcfs/include/libcfs/libcfs_heap.h +++ b/libcfs/include/libcfs/libcfs_heap.h @@ -166,6 +166,7 @@ cfs_binheap_t *cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags, cfs_binheap_node_t *cfs_binheap_find(cfs_binheap_t *h, unsigned int idx); int cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e); void cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e); +void cfs_binheap_relocate(cfs_binheap_t *h, cfs_binheap_node_t *e); static inline int cfs_binheap_size(cfs_binheap_t *h) diff --git a/libcfs/libcfs/heap.c b/libcfs/libcfs/heap.c index f9362ea..ed87fa7 100644 --- a/libcfs/libcfs/heap.c +++ b/libcfs/libcfs/heap.c @@ -463,8 +463,7 @@ cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e) last->chn_index = cur_idx; *cur_ptr = last; - if (!cfs_binheap_bubble(h, *cur_ptr)) - cfs_binheap_sink(h, *cur_ptr); + cfs_binheap_relocate(h, *cur_ptr); e->chn_index = CBH_POISON; if (h->cbh_ops->hop_exit) @@ -472,4 +471,19 @@ cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e) } EXPORT_SYMBOL(cfs_binheap_remove); +/** + * Relocate a node in the binary heap. + * Should be called whenever a node's values + * which affects its ranking are changed. + * + * \param[in] h The heap + * \param[in] e The node + */ +void +cfs_binheap_relocate(cfs_binheap_t *h, cfs_binheap_node_t *e) +{ + if (!cfs_binheap_bubble(h, e)) + cfs_binheap_sink(h, e); +} +EXPORT_SYMBOL(cfs_binheap_relocate); /** @} heap */ -- 1.8.3.1