BLI_dlrbTree.h

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2009 Blender Authors, Joshua Leung. All rights reserved.
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once
 
#ifdef __cplusplus
extern "C" {
#endif
 
/* ********************************************** */
/* Data Types and Type Defines */
 
/* -------------------------------------------------------------------- */
typedef struct DLRBT_Node {
  /* ListBase capabilities */
  struct DLRBT_Node *next, *prev;
 
  /* Tree Associativity settings */
  struct DLRBT_Node *left, *right;
  struct DLRBT_Node *parent;
 
  char tree_col;
  /* ... for nice alignment, next item should usually be a char too... */
} DLRBT_Node;
 
typedef enum eDLRBT_Colors {
  DLRBT_BLACK = 0,
  DLRBT_RED,
} eDLRBT_Colors;
 
/* -------- */
 
typedef struct DLRBT_Tree {
  /* ListBase capabilities */
  void *first, *last; /* these should be based on DLRBT_Node-s */
 
  /* Root Node */
  void *root; /* this should be based on DLRBT_Node-s */
} DLRBT_Tree;
 
/* -------------------------------------------------------------------- */
typedef short (*DLRBT_Comparator_FP)(void *node, void *data);
 
typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data);
 
typedef void (*DLRBT_NUpdate_FP)(void *node, void *data);
 
typedef void (*DLRBT_NFree_FP)(void *node);
 
/* ********************************************** */
/* Public API */
 
/* -------------------------------------------------------------------- */
DLRBT_Tree *BLI_dlrbTree_new(void);
 
void BLI_dlrbTree_init(DLRBT_Tree *tree);
 
void BLI_dlrbTree_free(DLRBT_Tree *tree, DLRBT_NFree_FP free_cb);
 
void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
 
/* -------------------------------------------------------------------- */
DLRBT_Node *BLI_dlrbTree_search(const DLRBT_Tree *tree,
                                DLRBT_Comparator_FP cmp_cb,
                                void *search_data);
 
DLRBT_Node *BLI_dlrbTree_search_exact(const DLRBT_Tree *tree,
                                      DLRBT_Comparator_FP cmp_cb,
                                      void *search_data);
 
DLRBT_Node *BLI_dlrbTree_search_prev(const DLRBT_Tree *tree,
                                     DLRBT_Comparator_FP cmp_cb,
                                     void *search_data);
 
DLRBT_Node *BLI_dlrbTree_search_next(const DLRBT_Tree *tree,
                                     DLRBT_Comparator_FP cmp_cb,
                                     void *search_data);
 
short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
 
/* -------------------------------------------------------------------- */
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);
 
/* FIXME: this is not implemented yet. */
// void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
 
/* -------------------------------------------------------------------- */
void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
 
#ifdef __cplusplus
}
#endif