#define CBH_ALLOC(ptr, h) \
do { \
- if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
- LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid, \
- CBH_NOB, GFP_ATOMIC); \
- else \
- LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid, \
- CBH_NOB); \
+ if (h->cbh_cptab) { \
+ if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
+ LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, \
+ h->cbh_cptid, CBH_NOB, \
+ GFP_ATOMIC); \
+ else \
+ LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, \
+ h->cbh_cptid, CBH_NOB); \
+ } else { \
+ if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
+ LIBCFS_ALLOC_ATOMIC((ptr), CBH_NOB); \
+ else \
+ LIBCFS_ALLOC((ptr), CBH_NOB); \
+ } \
} while (0)
#define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)
/**
* Grows the capacity of a binary heap so that it can handle a larger number of
- * \e cfs_binheap_node_t objects.
+ * \e struct cfs_binheap_node objects.
*
* \param[in] h The binary heap
*
* \retval -ENOMEM OOM error
*/
static int
-cfs_binheap_grow(cfs_binheap_t *h)
+cfs_binheap_grow(struct cfs_binheap *h)
{
- cfs_binheap_node_t ***frag1 = NULL;
- cfs_binheap_node_t **frag2;
+ struct cfs_binheap_node ***frag1 = NULL;
+ struct cfs_binheap_node **frag2;
int hwm = h->cbh_hwm;
/* need a whole new chunk of pointers */
* \retval valid-pointer A newly-created and initialized binary heap object
* \retval NULL error
*/
-cfs_binheap_t *
-cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
+struct cfs_binheap *
+cfs_binheap_create(struct cfs_binheap_ops *ops, unsigned int flags,
unsigned count, void *arg, struct cfs_cpt_table *cptab,
int cptid)
{
- cfs_binheap_t *h;
+ struct cfs_binheap *h;
LASSERT(ops != NULL);
LASSERT(ops->hop_compare != NULL);
- LASSERT(cptab != NULL);
- LASSERT(cptid == CFS_CPT_ANY ||
- (cptid >= 0 && cptid < cptab->ctb_nparts));
-
- LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
- if (h == NULL)
+ if (cptab) {
+ LASSERT(cptid == CFS_CPT_ANY ||
+ (cptid >= 0 && cptid < cptab->ctb_nparts));
+ LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
+ } else {
+ LIBCFS_ALLOC(h, sizeof(*h));
+ }
+ if (!h)
return NULL;
h->cbh_ops = ops;
* \param[in] h The binary heap object
*/
void
-cfs_binheap_destroy(cfs_binheap_t *h)
+cfs_binheap_destroy(struct cfs_binheap *h)
{
int idx0;
int idx1;
*
* \retval valid-pointer A double pointer to a heap pointer entry
*/
-static cfs_binheap_node_t **
-cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
+static struct cfs_binheap_node **
+cfs_binheap_pointer(struct cfs_binheap *h, unsigned int idx)
{
if (idx < CBH_SIZE)
return &(h->cbh_elements1[idx]);
* \retval valid-pointer The requested heap node
* \retval NULL Supplied index is out of bounds
*/
-cfs_binheap_node_t *
-cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
+struct cfs_binheap_node *
+cfs_binheap_find(struct cfs_binheap *h, unsigned int idx)
{
if (idx >= h->cbh_nelements)
return NULL;
* \retval 0 The position of \a e in the tree was not changed
*/
static int
-cfs_binheap_bubble(cfs_binheap_t *h, cfs_binheap_node_t *e)
+cfs_binheap_bubble(struct cfs_binheap *h, struct cfs_binheap_node *e)
{
unsigned int cur_idx = e->chn_index;
- cfs_binheap_node_t **cur_ptr;
+ struct cfs_binheap_node **cur_ptr;
unsigned int parent_idx;
- cfs_binheap_node_t **parent_ptr;
+ struct cfs_binheap_node **parent_ptr;
int did_sth = 0;
cur_ptr = cfs_binheap_pointer(h, cur_idx);
* \retval 0 The position of \a e in the tree was not changed
*/
static int
-cfs_binheap_sink(cfs_binheap_t *h, cfs_binheap_node_t *e)
+cfs_binheap_sink(struct cfs_binheap *h, struct cfs_binheap_node *e)
{
unsigned int n = h->cbh_nelements;
unsigned int child_idx;
- cfs_binheap_node_t **child_ptr;
- cfs_binheap_node_t *child;
+ struct cfs_binheap_node **child_ptr;
+ struct cfs_binheap_node *child;
unsigned int child2_idx;
- cfs_binheap_node_t **child2_ptr;
- cfs_binheap_node_t *child2;
+ struct cfs_binheap_node **child2_ptr;
+ struct cfs_binheap_node *child2;
unsigned int cur_idx;
- cfs_binheap_node_t **cur_ptr;
+ struct cfs_binheap_node **cur_ptr;
int did_sth = 0;
cur_idx = e->chn_index;
* \retval != 0 error
*/
int
-cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e)
+cfs_binheap_insert(struct cfs_binheap *h, struct cfs_binheap_node *e)
{
- cfs_binheap_node_t **new_ptr;
+ struct cfs_binheap_node **new_ptr;
unsigned int new_idx = h->cbh_nelements;
int rc;
* \param[in] e The node
*/
void
-cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e)
+cfs_binheap_remove(struct cfs_binheap *h, struct cfs_binheap_node *e)
{
unsigned int n = h->cbh_nelements;
unsigned int cur_idx = e->chn_index;
- cfs_binheap_node_t **cur_ptr;
- cfs_binheap_node_t *last;
+ struct cfs_binheap_node **cur_ptr;
+ struct cfs_binheap_node *last;
LASSERT(cur_idx != CBH_POISON);
LASSERT(cur_idx < n);
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)
}
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(struct cfs_binheap *h, struct cfs_binheap_node *e)
+{
+ if (!cfs_binheap_bubble(h, e))
+ cfs_binheap_sink(h, e);
+}
+EXPORT_SYMBOL(cfs_binheap_relocate);
/** @} heap */
git://git.whamcloud.com / fs / lustre-release.git / blobdiff