diff options
Diffstat (limited to 'drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h')
| -rw-r--r-- | drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h b/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h new file mode 100644 index 000000000000..bfa6d7b245ea --- /dev/null +++ b/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h @@ -0,0 +1,200 @@ +/* + * 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 <eeb@whamcloud.com> + * Liang Zhen <liang@whamcloud.com> + */ + +#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); + +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__ */ |