1 /******************************************************************************* 2 * Copyright (c) 2009, 2013 IBM Corp. 3 * 4 * All rights reserved. This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License v1.0 6 * and Eclipse Distribution License v1.0 which accompany this distribution. 7 * 8 * The Eclipse Public License is available at 9 * http://www.eclipse.org/legal/epl-v10.html 10 * and the Eclipse Distribution License is available at 11 * http://www.eclipse.org/org/documents/edl-v10.php. 12 * 13 * Contributors: 14 * Ian Craggs - initial implementation and documentation 15 *******************************************************************************/ 16 17 18 #if !defined(TREE_H) 19 #define TREE_H 20 21 #include <stdlib.h> /* for size_t definition */ 22 23 /*BE 24 defm defTree(T) // macro to define a tree 25 26 def T concat Node 27 { 28 n32 ptr T concat Node "parent" 29 n32 ptr T concat Node "left" 30 n32 ptr T concat Node "right" 31 n32 ptr T id2str(T) 32 n32 suppress "size" 33 } 34 35 36 def T concat Tree 37 { 38 struct 39 { 40 n32 ptr T concat Node suppress "root" 41 n32 ptr DATA suppress "compare" 42 } 43 struct 44 { 45 n32 ptr T concat Node suppress "root" 46 n32 ptr DATA suppress "compare" 47 } 48 n32 dec "count" 49 n32 dec suppress "size" 50 } 51 52 endm 53 54 defTree(INT) 55 defTree(STRING) 56 defTree(TMP) 57 58 BE*/ 59 60 /** 61 * Structure to hold all data for one list element 62 */ 63 typedef struct NodeStruct 64 { 65 struct NodeStruct *parent, /**< pointer to parent tree node, in case we need it */ 66 *child[2]; /**< pointers to child tree nodes 0 = left, 1 = right */ 67 void* content; /**< pointer to element content */ 68 size_t size; /**< size of content */ 69 unsigned int red : 1; 70 } Node; 71 72 73 /** 74 * Structure to hold all data for one tree 75 */ 76 typedef struct 77 { 78 struct 79 { 80 Node *root; /**< root node pointer */ 81 int (*compare)(void*, void*, int); /**< comparison function */ 82 } index[2]; 83 int indexes, /**< no of indexes into tree */ 84 count; /**< no of items */ 85 size_t size; /**< heap storage used */ 86 unsigned int heap_tracking : 1; /**< switch on heap tracking for this tree? */ 87 unsigned int allow_duplicates : 1; /**< switch to allow duplicate entries */ 88 } Tree; 89 90 91 Tree* TreeInitialize(int(*compare)(void*, void*, int)); 92 void TreeInitializeNoMalloc(Tree* aTree, int(*compare)(void*, void*, int)); 93 void TreeAddIndex(Tree* aTree, int(*compare)(void*, void*, int)); 94 95 void* TreeAdd(Tree* aTree, void* content, size_t size); 96 97 void* TreeRemove(Tree* aTree, void* content); 98 99 void* TreeRemoveKey(Tree* aTree, void* key); 100 void* TreeRemoveKeyIndex(Tree* aTree, void* key, int index); 101 102 void* TreeRemoveNodeIndex(Tree* aTree, Node* aNode, int index); 103 104 void TreeFree(Tree* aTree); 105 106 Node* TreeFind(Tree* aTree, void* key); 107 Node* TreeFindIndex(Tree* aTree, void* key, int index); 108 109 Node* TreeNextElement(Tree* aTree, Node* curnode); 110 111 int TreeIntCompare(void* a, void* b, int); 112 int TreePtrCompare(void* a, void* b, int); 113 int TreeStringCompare(void* a, void* b, int); 114 115 #endif 116