Fix #22123 and #22124: some problems with mutex locks, also tweak to
[blender.git] / source / blender / blenlib / BLI_dlrbTree.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) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * Contributor(s): Joshua Leung (original author)
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #ifndef BLI_DLRB_TREE_H
29 #define BLI_DLRB_TREE_H
30
31 /* Double-Linked Red-Black Tree Implementation:
32  * 
33  * This is simply a Red-Black Tree implementation whose nodes can later
34  * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase).
35  * The Red-Black Tree implementation is based on the methods defined by Wikipedia.
36  */
37
38 /* ********************************************** */
39 /* Data Types and Type Defines  */
40
41 /* Base Structs --------------------------------- */
42
43 /* Basic Layout for a Node */
44 typedef struct DLRBT_Node {
45         /* ListBase capabilities */
46         struct DLRBT_Node *next, *prev;         
47         
48         /* Tree Associativity settings */
49         struct DLRBT_Node *left, *right;
50         struct DLRBT_Node *parent;
51         
52         char tree_col;
53         /* ... for nice alignment, next item should usually be a char too... */
54 } DLRBT_Node;
55
56 /* Red/Black defines for tree_col */
57 typedef enum eDLRBT_Colors {
58         DLRBT_BLACK= 0,
59         DLRBT_RED,
60 } eDLRBT_Colors;
61
62 /* -------- */
63
64 /* The Tree Data */
65 typedef struct DLRBT_Tree {
66         /* ListBase capabilities */
67         void *first, *last;                     /* these should be based on DLRBT_Node-s */
68
69         /* Root Node */
70         void *root;                                     /* this should be based on DLRBT_Node-s */
71 } DLRBT_Tree;
72
73 /* Callback Types --------------------------------- */
74
75 /* return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node 
76  *      - node: <DLRBT_Node> the node to compare to
77  *      - data: pointer to the relevant data or values stored in the bitpattern dependant on the function
78  */
79 typedef short (*DLRBT_Comparator_FP)(void *node, void *data);
80
81 /* return a new node instance wrapping the given data 
82  *      - data: pointer to the relevant data to create a subclass of node from
83  */
84 typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data);
85
86 /* update an existing node instance accordingly to be in sync with the given data *     
87  *      - node: <DLRBT_Node> the node to update
88  *      - data: pointer to the relevant data or values stored in the bitpattern dependant on the function
89  */
90 typedef void (*DLRBT_NUpdate_FP)(void *node, void *data);
91
92 /* ********************************************** */
93 /* Public API */
94
95 /* ADT Management ------------------------------- */
96
97 /* Create a new tree, and initialise as necessary */
98 DLRBT_Tree *BLI_dlrbTree_new(void);
99
100 /* Initialises some given trees */
101 void BLI_dlrbTree_init(DLRBT_Tree *tree);
102
103 /* Free some tree */
104 void BLI_dlrbTree_free(DLRBT_Tree *tree);
105
106 /* Make sure the tree's Double-Linked list representation is valid */
107 void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
108
109
110 /* Searching ------------------------------------ */
111
112 /* Find the node which matches or is the closest to the requested node */
113 DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
114
115 /* Find the node which exactly matches the required data */
116 DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
117
118 /* Find the node which occurs immediately before the best matching node */
119 DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
120
121 /* Find the node which occurs immediately after the best matching node */
122 DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
123
124
125 /* Check whether there is a node matching the requested node */
126 short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
127
128
129 /* Node Operations (Managed) --------------------- */
130 /* These methods automate the process of adding/removing nodes from the BST, 
131  * using the supplied data and callbacks
132  */
133
134 /* Add the given data to the tree, and return the node added */
135 // NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned
136 DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, 
137                         DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data);
138
139
140 /* Remove the given element from the tree and balance again */
141 // FIXME: this is not implemented yet... 
142 void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
143
144 /* Node Operations (Manual) --------------------- */
145 /* These methods require custom code for creating BST nodes and adding them to the 
146  * tree in special ways, such that the node can then be balanced.
147  *
148  * It is recommended that these methods are only used where the other method is too cumbersome...
149  */
150
151 /* Balance the tree after the given node has been added to it 
152  * (using custom code, in the Binary Tree way).
153  */
154 void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
155
156 /* ********************************************** */
157
158 #endif // BLI_DLRB_TREE_H