| /* |
| * 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__ */ |