[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;
};

#ifdef DEBUG_HEAP
void check_heap(const struct ptr_heap *heap);
#else
static inline
void check_heap(const struct ptr_heap *heap)
{
}
#endif

/**
 * 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)
{
	check_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	#ifdef DEBUG_HEAP
	32	void check_heap(const struct ptr_heap *heap);
	33	#else
	34	static inline
	35	void check_heap(const struct ptr_heap *heap)
	36	{
	37	}
	38	#endif
	39
	40	/**
	41	* heap_maximum - return the largest element in the heap
	42	* @heap: the heap to be operated on
	43	*
	44	* Returns the largest element in the heap, without performing any modification
	45	* to the heap structure. Returns NULL if the heap is empty.
	46	*/
	47	static inline void heap_maximum(const struct ptr_heap heap)
	48	{
	49	check_heap(heap);
	50	return heap->len ? heap->ptrs[0] : NULL;
	51	}
	52
	53	/**
	54	* heap_init - initialize the heap
	55	* @heap: the heap to initialize
	56	* @alloc_len: number of elements initially allocated
	57	* @gfp: allocation flags
	58	* @gt: function to compare the elements
	59	*
	60	* Returns -ENOMEM if out of memory.
	61	*/
	62	extern int heap_init(struct ptr_heap *heap,
	63	size_t alloc_len, gfp_t gfpmask,
	64	int gt(void a, void b));
	65
	66	/**
	67	* heap_free - free the heap
	68	* @heap: the heap to free
	69	*/
	70	extern void heap_free(struct ptr_heap *heap);
	71
	72	/**
	73	* heap_insert - insert an element into the heap
	74	* @heap: the heap to be operated on
	75	* @p: the element to add
	76	*
	77	* Insert an element into the heap.
	78	*
	79	* Returns -ENOMEM if out of memory.
	80	*/
	81	extern int heap_insert(struct ptr_heap heap, void p);
	82
	83	/**
	84	* heap_remove - remove the largest element from the heap
	85	* @heap: the heap to be operated on
	86	*
	87	* Returns the largest element in the heap. It removes this element from the
	88	* heap. Returns NULL if the heap is empty.
	89	*/
	90	extern void heap_remove(struct ptr_heap heap);
	91
	92	/**
	93	* heap_cherrypick - remove a given element from the heap
	94	* @heap: the heap to be operated on
	95	* @p: the element
	96	*
	97	* Remove the given element from the heap. Return the element if present, else
	98	* return NULL. This algorithm has a complexity of O(n), which is higher than
	99	* O(log(n)) provided by the rest of this API.
	100	*/
	101	extern void heap_cherrypick(struct ptr_heap heap, void *p);
	102
	103	/**
	104	* heap_replace_max - replace the the largest element from the heap
	105	* @heap: the heap to be operated on
	106	* @p: the pointer to be inserted as topmost element replacement
	107	*
	108	* Returns the largest element in the heap. It removes this element from the
	109	* heap. The heap is rebalanced only once after the insertion. Returns NULL if
	110	* the heap is empty.
	111	*
	112	* This is the equivalent of calling heap_remove() and then heap_insert(), but
	113	* it only rebalances the heap once. It never allocates memory.
	114	*/
	115	extern void heap_replace_max(struct ptr_heap heap, void *p);
	116
	117	#endif /* _LTTNG_PRIO_HEAP_H */