Blender  V3.3
BLI_dlrbTree.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2009 Blender Foundation, Joshua Leung. All rights reserved. */
3 
4 #pragma once
5 
16 #ifdef __cplusplus
17 extern "C" {
18 #endif
19 
20 /* ********************************************** */
21 /* Data Types and Type Defines */
22 
23 /* -------------------------------------------------------------------- */
28 typedef struct DLRBT_Node {
29  /* ListBase capabilities */
30  struct DLRBT_Node *next, *prev;
31 
32  /* Tree Associativity settings */
33  struct DLRBT_Node *left, *right;
34  struct DLRBT_Node *parent;
35 
36  char tree_col;
37  /* ... for nice alignment, next item should usually be a char too... */
39 
41 typedef enum eDLRBT_Colors {
45 
46 /* -------- */
47 
49 typedef struct DLRBT_Tree {
50  /* ListBase capabilities */
51  void *first, *last; /* these should be based on DLRBT_Node-s */
52 
53  /* Root Node */
54  void *root; /* this should be based on DLRBT_Node-s */
56 
59 /* -------------------------------------------------------------------- */
70 typedef short (*DLRBT_Comparator_FP)(void *node, void *data);
71 
76 typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data);
77 
84 typedef void (*DLRBT_NUpdate_FP)(void *node, void *data);
85 
90 typedef void (*DLRBT_NFree_FP)(void *node);
91 
92 /* ********************************************** */
93 /* Public API */
94 
97 /* -------------------------------------------------------------------- */
105 
111 
116 
121 
124 /* -------------------------------------------------------------------- */
132  DLRBT_Comparator_FP cmp_cb,
133  void *search_data);
134 
139  DLRBT_Comparator_FP cmp_cb,
140  void *search_data);
141 
146  DLRBT_Comparator_FP cmp_cb,
147  void *search_data);
148 
153  DLRBT_Comparator_FP cmp_cb,
154  void *search_data);
155 
159 short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
160 
163 /* -------------------------------------------------------------------- */
178  DLRBT_Comparator_FP cmp_cb,
179  DLRBT_NAlloc_FP new_cb,
181  void *data);
182 
183 /* FIXME: this is not implemented yet. */
187 // void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
188 
191 /* -------------------------------------------------------------------- */
205 
208 #ifdef __cplusplus
209 }
210 #endif
struct DLRBT_Node DLRBT_Node
DLRBT_Node *(* DLRBT_NAlloc_FP)(void *data)
Definition: BLI_dlrbTree.h:76
void BLI_dlrbTree_init(DLRBT_Tree *tree)
Definition: DLRB_tree.c:22
DLRBT_Tree * BLI_dlrbTree_new(void)
Definition: DLRB_tree.c:16
DLRBT_Node * BLI_dlrbTree_search_exact(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:167
DLRBT_Node * BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data)
Definition: DLRB_tree.c:526
void(* DLRBT_NFree_FP)(void *node)
Definition: BLI_dlrbTree.h:90
DLRBT_Node * BLI_dlrbTree_search_prev(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:214
void(* DLRBT_NUpdate_FP)(void *node, void *data)
Definition: BLI_dlrbTree.h:84
void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree)
Definition: DLRB_tree.c:103
DLRBT_Node * BLI_dlrbTree_search(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:120
short(* DLRBT_Comparator_FP)(void *node, void *data)
Definition: BLI_dlrbTree.h:70
short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:274
void BLI_dlrbTree_free(DLRBT_Tree *tree, DLRBT_NFree_FP free_cb)
Definition: DLRB_tree.c:49
eDLRBT_Colors
Definition: BLI_dlrbTree.h:41
@ DLRBT_BLACK
Definition: BLI_dlrbTree.h:42
@ DLRBT_RED
Definition: BLI_dlrbTree.h:43
void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:510
struct DLRBT_Tree DLRBT_Tree
DLRBT_Node * BLI_dlrbTree_search_next(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:244
OperationNode * node
SyclQueue void void size_t num_bytes void
void * tree
static void update_cb(PBVHNode *node, void *rebuild)
Definition: sculpt_undo.c:133
struct DLRBT_Node * parent
Definition: BLI_dlrbTree.h:34
struct DLRBT_Node * next
Definition: BLI_dlrbTree.h:30
struct DLRBT_Node * left
Definition: BLI_dlrbTree.h:33
struct DLRBT_Node * right
Definition: BLI_dlrbTree.h:33
char tree_col
Definition: BLI_dlrbTree.h:36
struct DLRBT_Node * prev
Definition: BLI_dlrbTree.h:30
void * last
Definition: BLI_dlrbTree.h:51
void * root
Definition: BLI_dlrbTree.h:54
void * first
Definition: BLI_dlrbTree.h:51