1 // Gmsh - Copyright (C) 1997-2021 C. Geuzaine, J.-F. Remacle
2 //
3 // See the LICENSE.txt file in the Gmsh root directory for license information.
4 // Please report all issues on https://gitlab.onelab.info/gmsh/gmsh/issues.
5 //
6 // Contributor(s):
7 // Marc Ume
8 //
9
10 #include <stdlib.h>
11 #include <string.h>
12 #include "MallocUtils.h"
13 #include "TreeUtils.h"
14
Tree_Create(int size,int (* fcmp)(const void * a,const void * b))15 Tree_T *Tree_Create(int size, int (*fcmp)(const void *a, const void *b))
16 {
17 Tree_T *tree = (Tree_T *)Malloc(sizeof(Tree_T));
18 tree->size = size;
19 tree->root = avl_init_table(fcmp);
20 return tree;
21 }
22
Tree_Delete(Tree_T * tree)23 void Tree_Delete(Tree_T *tree)
24 {
25 if(!tree) return;
26 avl_free_table(tree->root, Free, nullptr);
27 Free(tree);
28 }
29
Tree_Delete(Tree_T * tree,void (* freefn)(void *))30 void Tree_Delete(Tree_T *tree, void (*freefn)(void *))
31 {
32 if(!tree) return;
33 avl_free_table(tree->root, freefn, nullptr);
34 Free(tree);
35 }
36
Tree_Add(Tree_T * tree,void * data)37 void *Tree_Add(Tree_T *tree, void *data)
38 {
39 if(!tree) return nullptr;
40 void *ptr = Malloc(tree->size);
41 memcpy(ptr, data, tree->size);
42 avl_insert(tree->root, ptr, ptr);
43 return ptr;
44 }
45
Tree_Nbr(Tree_T * tree)46 int Tree_Nbr(Tree_T *tree)
47 {
48 if(!tree) return 0;
49 return avl_count(tree->root);
50 }
51
Tree_Insert(Tree_T * tree,void * data)52 int Tree_Insert(Tree_T *tree, void *data)
53 {
54 if(!Tree_Search(tree, data)) {
55 Tree_Add(tree, data);
56 return 1;
57 }
58 return 0;
59 }
60
Tree_Search(Tree_T * tree,void * data)61 int Tree_Search(Tree_T *tree, void *data)
62 {
63 if(!tree) return 0;
64 void *ptr;
65 return avl_lookup(tree->root, data, &ptr);
66 }
67
Tree_Query(Tree_T * tree,void * data)68 int Tree_Query(Tree_T *tree, void *data)
69 {
70 if(!tree) return 0;
71 void *ptr;
72 if(!avl_lookup(tree->root, data, &ptr)) return 0;
73 memcpy(data, ptr, tree->size);
74 return 1;
75 }
76
Tree_PQuery(Tree_T * tree,void * data)77 void *Tree_PQuery(Tree_T *tree, void *data)
78 {
79 if(!tree) return nullptr;
80 void *ptr;
81 if(!avl_lookup(tree->root, data, &ptr)) return nullptr;
82 return ptr;
83 }
84
Tree_Suppress(Tree_T * tree,void * data)85 int Tree_Suppress(Tree_T *tree, void *data)
86 {
87 if(!tree) return 0;
88 void *ptr = data;
89 if(!avl_delete(tree->root, &ptr, &ptr)) return 0;
90 Free(ptr);
91 return 1;
92 }
93
Tree_Size(Tree_T * tree)94 int Tree_Size(Tree_T *tree)
95 {
96 if(!tree) return 0;
97 return tree->size;
98 }
99
Tree_Action(Tree_T * tree,void (* action)(void * data,void * dummy))100 void Tree_Action(Tree_T *tree, void (*action)(void *data, void *dummy))
101 {
102 if(!tree) return;
103 avl_foreach(tree->root, action, AVL_FORWARD);
104 }
105
106 static List_T *pListTransfer;
107
TransferList(void * a,void * b)108 void TransferList(void *a, void *b) { List_Add(pListTransfer, a); }
109
Tree2List(Tree_T * pTree)110 List_T *Tree2List(Tree_T *pTree)
111 {
112 int Nb;
113 Nb = Tree_Nbr(pTree);
114 if(Nb == 0) Nb = 1;
115 pListTransfer = List_Create(Nb, Nb, Tree_Size(pTree));
116 Tree_Action(pTree, TransferList);
117 return pListTransfer;
118 }
119