/*
* GPL HEADER START
*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 only,
* as published by the Free Software Foundation.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License version 2 for more details. A copy is
* included in the COPYING file that accompanied this code.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* GPL HEADER END
*/
/*
* Copyright (c) 2011 Intel Corporation
*/
/*
* libcfs/include/libcfs/heap.h
*
* Author: Eric Barton
* Liang Zhen
*/
#ifndef __LIBCFS_HEAP_H__
#define __LIBCFS_HEAP_H__
/** \defgroup heap Binary heap
*
* The binary heap is a scalable data structure created using a binary tree. It
* is capable of maintaining large sets of elements sorted usually by one or
* more element properties, but really based on anything that can be used as a
* binary predicate in order to determine the relevant ordering of any two nodes
* that belong to the set. There is no search operation, rather the intention is
* for the element of the lowest priority which will always be at the root of
* the tree (as this is an implementation of a min-heap) to be removed by users
* for consumption.
*
* Users of the heap should embed a \e cfs_binheap_node_t object instance on
* every object of the set that they wish the binary heap instance to handle,
* and (at a minimum) provide a cfs_binheap_ops_t::hop_compare() implementation
* which is used by the heap as the binary predicate during its internal sorting
* operations.
*
* The current implementation enforces no locking scheme, and so assumes the
* user caters for locking between calls to insert, delete and lookup
* operations. Since the only consumer for the data structure at this point
* are NRS policies, and these operate on a per-CPT basis, binary heap instances
* are tied to a specific CPT.
* @{
*/
/**
* Binary heap node.
*
* Objects of this type are embedded into objects of the ordered set that is to
* be maintained by a \e cfs_binheap_t instance.
*/
typedef struct {
/** Index into the binary tree */
unsigned int chn_index;
} cfs_binheap_node_t;
#define CBH_SHIFT 9
#define CBH_SIZE (1 << CBH_SHIFT) /* # ptrs per level */
#define CBH_MASK (CBH_SIZE - 1)
#define CBH_NOB (CBH_SIZE * sizeof(cfs_binheap_node_t *))
#define CBH_POISON 0xdeadbeef
/**
* Binary heap flags.
*/
enum {
CBH_FLAG_ATOMIC_GROW = 1,
};
struct cfs_binheap;
/**
* Binary heap operations.
*/
typedef struct {
/**
* Called right before inserting a node into the binary heap.
*
* Implementing this operation is optional.
*
* \param[in] h The heap
* \param[in] e The node
*
* \retval 0 success
* \retval != 0 error
*/
int (*hop_enter)(struct cfs_binheap *h,
cfs_binheap_node_t *e);
/**
* Called right after removing a node from the binary heap.
*
* Implementing this operation is optional.
*
* \param[in] h The heap
* \param[in] e The node
*/
void (*hop_exit)(struct cfs_binheap *h,
cfs_binheap_node_t *e);
/**
* A binary predicate which is called during internal heap sorting
* operations, and used in order to determine the relevant ordering of
* two heap nodes.
*
* Implementing this operation is mandatory.
*
* \param[in] a The first heap node
* \param[in] b The second heap node
*
* \retval 0 Node a > node b
* \retval 1 Node a < node b
*
* \see cfs_binheap_bubble()
* \see cfs_biheap_sink()
*/
int (*hop_compare)(cfs_binheap_node_t *a,
cfs_binheap_node_t *b);
} cfs_binheap_ops_t;
/**
* Binary heap object.
*
* Sorts elements of type \e cfs_binheap_node_t
*/
typedef struct cfs_binheap {
/** Triple indirect */
cfs_binheap_node_t ****cbh_elements3;
/** double indirect */
cfs_binheap_node_t ***cbh_elements2;
/** single indirect */
cfs_binheap_node_t **cbh_elements1;
/** # elements referenced */
unsigned int cbh_nelements;
/** high water mark */
unsigned int cbh_hwm;
/** user flags */
unsigned int cbh_flags;
/** operations table */
cfs_binheap_ops_t *cbh_ops;
/** private data */
void *cbh_private;
/** associated CPT table */
struct cfs_cpt_table *cbh_cptab;
/** associated CPT id of this cfs_binheap_t::cbh_cptab */
int cbh_cptid;
} cfs_binheap_t;
void cfs_binheap_destroy(cfs_binheap_t *h);
cfs_binheap_t *cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
unsigned count, void *arg,
struct cfs_cpt_table *cptab, int cptid);
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)
{
return h->cbh_nelements;
}
static inline int
cfs_binheap_is_empty(cfs_binheap_t *h)
{
return h->cbh_nelements == 0;
}
static inline cfs_binheap_node_t *
cfs_binheap_root(cfs_binheap_t *h)
{
return cfs_binheap_find(h, 0);
}
static inline cfs_binheap_node_t *
cfs_binheap_remove_root(cfs_binheap_t *h)
{
cfs_binheap_node_t *e = cfs_binheap_find(h, 0);
if (e != NULL)
cfs_binheap_remove(h, e);
return e;
}
/** @} heap */
#endif /* __LIBCFS_HEAP_H__ */