[babeltrace.git] / include / babeltrace / prio_heap.h

#ifndef _BABELTRACE_PRIO_HEAP_H
#define _BABELTRACE_PRIO_HEAP_H

/*
 * prio_heap.h
 *
 * Static-sized 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 <unistd.h>

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

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