| /******************************************************************************* |
| * Copyright (c) 2009, 2013 IBM Corp. |
| * |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * and Eclipse Distribution License v1.0 which accompany this distribution. |
| * |
| * The Eclipse Public License is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * and the Eclipse Distribution License is available at |
| * http://www.eclipse.org/org/documents/edl-v10.php. |
| * |
| * Contributors: |
| * Ian Craggs - initial implementation and documentation |
| *******************************************************************************/ |
| |
| |
| #if !defined(TREE_H) |
| #define TREE_H |
| |
| #include <stdlib.h> /* for size_t definition */ |
| |
| /*BE |
| defm defTree(T) // macro to define a tree |
| |
| def T concat Node |
| { |
| n32 ptr T concat Node "parent" |
| n32 ptr T concat Node "left" |
| n32 ptr T concat Node "right" |
| n32 ptr T id2str(T) |
| n32 suppress "size" |
| } |
| |
| |
| def T concat Tree |
| { |
| struct |
| { |
| n32 ptr T concat Node suppress "root" |
| n32 ptr DATA suppress "compare" |
| } |
| struct |
| { |
| n32 ptr T concat Node suppress "root" |
| n32 ptr DATA suppress "compare" |
| } |
| n32 dec "count" |
| n32 dec suppress "size" |
| } |
| |
| endm |
| |
| defTree(INT) |
| defTree(STRING) |
| defTree(TMP) |
| |
| BE*/ |
| |
| /** |
| * Structure to hold all data for one list element |
| */ |
| typedef struct NodeStruct |
| { |
| struct NodeStruct *parent, /**< pointer to parent tree node, in case we need it */ |
| *child[2]; /**< pointers to child tree nodes 0 = left, 1 = right */ |
| void* content; /**< pointer to element content */ |
| size_t size; /**< size of content */ |
| unsigned int red : 1; |
| } Node; |
| |
| |
| /** |
| * Structure to hold all data for one tree |
| */ |
| typedef struct |
| { |
| struct |
| { |
| Node *root; /**< root node pointer */ |
| int (*compare)(void*, void*, int); /**< comparison function */ |
| } index[2]; |
| int indexes, /**< no of indexes into tree */ |
| count; /**< no of items */ |
| size_t size; /**< heap storage used */ |
| unsigned int heap_tracking : 1; /**< switch on heap tracking for this tree? */ |
| unsigned int allow_duplicates : 1; /**< switch to allow duplicate entries */ |
| } Tree; |
| |
| |
| Tree* TreeInitialize(int(*compare)(void*, void*, int)); |
| void TreeInitializeNoMalloc(Tree* aTree, int(*compare)(void*, void*, int)); |
| void TreeAddIndex(Tree* aTree, int(*compare)(void*, void*, int)); |
| |
| void* TreeAdd(Tree* aTree, void* content, size_t size); |
| |
| void* TreeRemove(Tree* aTree, void* content); |
| |
| void* TreeRemoveKey(Tree* aTree, void* key); |
| void* TreeRemoveKeyIndex(Tree* aTree, void* key, int index); |
| |
| void* TreeRemoveNodeIndex(Tree* aTree, Node* aNode, int index); |
| |
| void TreeFree(Tree* aTree); |
| |
| Node* TreeFind(Tree* aTree, void* key); |
| Node* TreeFindIndex(Tree* aTree, void* key, int index); |
| |
| Node* TreeNextElement(Tree* aTree, Node* curnode); |
| |
| int TreeIntCompare(void* a, void* b, int); |
| int TreePtrCompare(void* a, void* b, int); |
| int TreeStringCompare(void* a, void* b, int); |
| |
| #endif |