Filling in branch from trunk
[blender.git] / source / blender / blenlib / BLI_heap.h
1 /**
2  * A heap / priority queue ADT
3  * 
4  * $Id$
5  *
6  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version. The Blender
12  * Foundation also sells licenses for use in proprietary software under
13  * the Blender License.  See http://www.blender.org/BL/ for information
14  * about this.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  *
25  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
26  * All rights reserved.
27  *
28  * The Original Code is: none of this file.
29  *
30  * Contributor(s): Brecht Van Lommel
31  *
32  * ***** END GPL/BL DUAL LICENSE BLOCK *****
33  */
34  
35 #ifndef BLI_HEAP_H
36 #define BLI_HEAP_H
37
38 struct Heap;
39 struct HeapNode;
40 typedef struct Heap Heap;
41 typedef struct HeapNode HeapNode;
42
43 typedef void    (*HeapFreeFP)(void *ptr);
44
45 /* Creates a new heap. BLI_memarena is used for allocating nodes. Removed nodes
46    are recycled, so memory usage will not shrink. */
47 Heap*                   BLI_heap_new    (void);
48 void                    BLI_heap_free   (Heap *heap, HeapFreeFP ptrfreefp);
49
50 /* Insert heap node with a value (often a 'cost') and pointer into the heap,
51    duplicate values are allowed. */
52 HeapNode*               BLI_heap_insert         (Heap *heap, float value, void *ptr);
53
54 /* Remove a heap node. */
55 void                    BLI_heap_remove         (Heap *heap, HeapNode *node);
56
57 /* Return 0 if the heap is empty, 1 otherwise. */
58 int                             BLI_heap_empty          (Heap *heap);
59
60 /* Return the size of the heap. */
61 int                             BLI_heap_size           (Heap *heap);
62
63 /* Return the top node of the heap. This is the node with the lowest value. */
64 HeapNode*               BLI_heap_top            (Heap *heap);
65
66 /* Pop the top node off the heap and return it's pointer. */
67 void*                   BLI_heap_popmin         (Heap *heap);
68
69 /* Return the value or pointer of a heap node. */
70 float                   BLI_heap_node_value     (HeapNode *heap);
71 void*                   BLI_heap_node_ptr       (HeapNode *heap);
72
73 #endif
74