Tree.h

Go to the documentation of this file.

/*******************************************************************************
 * 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 v2.0
 * and Eclipse Distribution License v1.0 which accompany this distribution. 
 *
 * The Eclipse Public License is available at 
 *    https://www.eclipse.org/legal/epl-2.0/
 * 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*/

typedef struct NodeStruct
{
        struct NodeStruct *parent,   
                                          *child[2]; 
        void* content;                           
        size_t size;                                     
        unsigned int red : 1;
} Node;


typedef struct
{
        struct
        {
                Node *root;     
                int (*compare)(void*, void*, int); 
        } index[2];
        int indexes,  
                count;    
        size_t size;  
        unsigned int heap_tracking : 1; 
        unsigned int allow_duplicates : 1; 
} 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