[lttng-modules.git] / lib / prio_heap / prio_heap.h

#ifndef _LTTNG_PRIO_HEAP_H
#define _LTTNG_PRIO_HEAP_H

/*
 * prio_heap.h
 *
 * Priority heap containing pointers. Based on CLRS, chapter 6.
 *
 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 */

#include <linux/gfp.h>

struct ptr_heap {
	size_t len, alloc_len;
	void **ptrs;
	int (*gt)(void *a, void *b);
	gfp_t gfpmask;
};

/**
 * heap_maximum - return the largest element in the heap
 * @heap: the heap to be operated on
 *
 * Returns the largest element in the heap, without performing any modification
 * to the heap structure. Returns NULL if the heap is empty.
 */
static inline void *heap_maximum(const struct ptr_heap *heap)
{
	return heap->len ? heap->ptrs[0] : NULL;
}

/**
 * heap_init - initialize the heap
 * @heap: the heap to initialize
 * @alloc_len: number of elements initially allocated
 * @gfp: allocation flags
 * @gt: function to compare the elements
 *
 * Returns -ENOMEM if out of memory.
 */
extern int heap_init(struct ptr_heap *heap,
		     size_t alloc_len, gfp_t gfpmask,
		     int gt(void *a, void *b));

/**
 * heap_free - free the heap
 * @heap: the heap to free
 */
extern void heap_free(struct ptr_heap *heap);

/**
 * heap_insert - insert an element into the heap
 * @heap: the heap to be operated on
 * @p: the element to add
 *
 * Insert an element into the heap.
 *
 * Returns -ENOMEM if out of memory.
 */
extern int heap_insert(struct ptr_heap *heap, void *p);

/**
 * heap_remove - remove the largest element from the heap
 * @heap: the heap to be operated on
 *
 * Returns the largest element in the heap. It removes this element from the
 * heap. Returns NULL if the heap is empty.
 */
extern void *heap_remove(struct ptr_heap *heap);

/**
 * heap_cherrypick - remove a given element from the heap
 * @heap: the heap to be operated on
 * @p: the element
 *
 * Remove the given element from the heap. Return the element if present, else
 * return NULL. This algorithm has a complexity of O(n), which is higher than
 * O(log(n)) provided by the rest of this API.
 */
extern void *heap_cherrypick(struct ptr_heap *heap, void *p);

/**
 * heap_replace_max - replace the the largest element from the heap
 * @heap: the heap to be operated on
 * @p: the pointer to be inserted as topmost element replacement
 *
 * Returns the largest element in the heap. It removes this element from the
 * heap. The heap is rebalanced only once after the insertion. Returns NULL if
 * the heap is empty.
 *
 * This is the equivalent of calling heap_remove() and then heap_insert(), but
 * it only rebalances the heap once. It never allocates memory.
 */
extern void *heap_replace_max(struct ptr_heap *heap, void *p);

#endif /* _LTTNG_PRIO_HEAP_H */
Commit	Line	Data
	1	#ifndef _LTTNG_PRIO_HEAP_H
	2	#define _LTTNG_PRIO_HEAP_H
	3
	4	/*
	5	* prio_heap.h
	6	*
	7	* Priority heap containing pointers. Based on CLRS, chapter 6.
	8	*
	9	* Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	10	*
	11	* Permission is hereby granted, free of charge, to any person obtaining a copy
	12	* of this software and associated documentation files (the "Software"), to deal
	13	* in the Software without restriction, including without limitation the rights
	14	* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	15	* copies of the Software, and to permit persons to whom the Software is
	16	* furnished to do so, subject to the following conditions:
	17	*
	18	* The above copyright notice and this permission notice shall be included in
	19	* all copies or substantial portions of the Software.
	20	*/
	21
	22	#include <linux/gfp.h>
	23
	24	struct ptr_heap {
	25	size_t len, alloc_len;
	26	void **ptrs;
	27	int (gt)(void a, void *b);
	28	gfp_t gfpmask;
	29	};
	30
	31	/**
	32	* heap_maximum - return the largest element in the heap
	33	* @heap: the heap to be operated on
	34	*
	35	* Returns the largest element in the heap, without performing any modification
	36	* to the heap structure. Returns NULL if the heap is empty.
	37	*/
	38	static inline void heap_maximum(const struct ptr_heap heap)
	39	{
	40	return heap->len ? heap->ptrs[0] : NULL;
	41	}
	42
	43	/**
	44	* heap_init - initialize the heap
	45	* @heap: the heap to initialize
	46	* @alloc_len: number of elements initially allocated
	47	* @gfp: allocation flags
	48	* @gt: function to compare the elements
	49	*
	50	* Returns -ENOMEM if out of memory.
	51	*/
	52	extern int heap_init(struct ptr_heap *heap,
	53	size_t alloc_len, gfp_t gfpmask,
	54	int gt(void a, void b));
	55
	56	/**
	57	* heap_free - free the heap
	58	* @heap: the heap to free
	59	*/
	60	extern void heap_free(struct ptr_heap *heap);
	61
	62	/**
	63	* heap_insert - insert an element into the heap
	64	* @heap: the heap to be operated on
	65	* @p: the element to add
	66	*
	67	* Insert an element into the heap.
	68	*
	69	* Returns -ENOMEM if out of memory.
	70	*/
	71	extern int heap_insert(struct ptr_heap heap, void p);
	72
	73	/**
	74	* heap_remove - remove the largest element from the heap
	75	* @heap: the heap to be operated on
	76	*
	77	* Returns the largest element in the heap. It removes this element from the
	78	* heap. Returns NULL if the heap is empty.
	79	*/
	80	extern void heap_remove(struct ptr_heap heap);
	81
	82	/**
	83	* heap_cherrypick - remove a given element from the heap
	84	* @heap: the heap to be operated on
	85	* @p: the element
	86	*
	87	* Remove the given element from the heap. Return the element if present, else
	88	* return NULL. This algorithm has a complexity of O(n), which is higher than
	89	* O(log(n)) provided by the rest of this API.
	90	*/
	91	extern void heap_cherrypick(struct ptr_heap heap, void *p);
	92
	93	/**
	94	* heap_replace_max - replace the the largest element from the heap
	95	* @heap: the heap to be operated on
	96	* @p: the pointer to be inserted as topmost element replacement
	97	*
	98	* Returns the largest element in the heap. It removes this element from the
	99	* heap. The heap is rebalanced only once after the insertion. Returns NULL if
	100	* the heap is empty.
	101	*
	102	* This is the equivalent of calling heap_remove() and then heap_insert(), but
	103	* it only rebalances the heap once. It never allocates memory.
	104	*/
	105	extern void heap_replace_max(struct ptr_heap heap, void *p);
	106
	107	#endif /* _LTTNG_PRIO_HEAP_H */