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, 0 insertions, 200 deletions
diff --git a/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h b/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h deleted file mode 100644 index bfa6d7b245ea..000000000000 --- a/drivers/staging/lustre/include/linux/libcfs/libcfs_heap.h +++ /dev/null @@ -1,200 +0,0 @@ -/* - * 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__ */ |