svn merge -r40140:r40148 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / blenlib / BLI_heap.h
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: none of this file.
24  *
25  * Contributor(s): Brecht Van Lommel
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29  
30 #ifndef BLI_HEAP_H
31 #define BLI_HEAP_H
32
33 /** \file BLI_heap.h
34  *  \ingroup bli
35  *  \brief A heap / priority queue ADT
36  */
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