tree.h File Reference

#include <gwenhywfar/gwenhywfarapi.h>
#include <gwenhywfar/types.h>
#include <assert.h>

Include dependency graph for tree.h:

Go to the source code of this file.

Macros
#define	GWEN_DUMMY_EMPTY_ARG
#define	GWEN_TREE_H
Typesafe Macros
#define	GWEN_TREE_ELEMENT(t)   GWEN_TREE_ELEMENT *_tree_element;
#define	GWEN_TREE_FINI(t, element)
#define	GWEN_TREE_FUNCTION_DEFS(t, pr)    GWEN_TREE_FUNCTION_LIB_DEFS(t, pr, GWEN_DUMMY_EMPTY_ARG)
#define	GWEN_TREE_FUNCTION_DEFS_CONST(t, pr)    GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, GWEN_DUMMY_EMPTY_ARG)
#define	GWEN_TREE_FUNCTION_DEFS_NOCONST(t, pr)    GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, GWEN_DUMMY_EMPTY_ARG)
#define	GWEN_TREE_FUNCTION_LIB_DEFS(t, pr, decl)
#define	GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, decl)
#define	GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, decl)
#define	GWEN_TREE_FUNCTIONS(t, pr)
#define	GWEN_TREE_INIT(t, element)    element->_tree_element=GWEN_TreeElement_new(element);

Internal Functions
All functions and structs within this group should be considered internal. They just implement the functionality behind the typesafe list macros (see GWEN_TREE_FUNCTION_LIB_DEFS and following).
typedef struct GWEN_TREE	GWEN_TREE
GWENHYWFAR_API void	GWEN_Tree_Add (GWEN_TREE *l, GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void	GWEN_Tree_AddChild (GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void	GWEN_Tree_AddList (GWEN_TREE *dest, GWEN_TREE *l)
GWENHYWFAR_API void	GWEN_Tree_Del (GWEN_TREE_ELEMENT *el)
typedef struct GWEN_TREE_ELEMENT	GWEN_TREE_ELEMENT
GWENHYWFAR_API void	GWEN_Tree_free (GWEN_TREE *l)
GWENHYWFAR_API int	GWEN_Tree_GetCount (const GWEN_TREE *l)
GWENHYWFAR_API void *	GWEN_Tree_GetFirst (const GWEN_TREE *l)
GWENHYWFAR_API void *	GWEN_Tree_GetLast (const GWEN_TREE *l)
GWENHYWFAR_API void	GWEN_Tree_Insert (GWEN_TREE *l, GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void	GWEN_Tree_InsertChild (GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API GWEN_TREE *	GWEN_Tree_new (void)
GWENHYWFAR_API void	GWEN_Tree_Replace (GWEN_TREE_ELEMENT *elToReplace, GWEN_TREE_ELEMENT *elReplacement)
GWENHYWFAR_API void	GWEN_TreeElement_free (GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetBelow (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API uint32_t	GWEN_TreeElement_GetChildrenCount (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetFirstChild (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetLastChild (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetNext (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetParent (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API void *	GWEN_TreeElement_GetPrevious (const GWEN_TREE_ELEMENT *el)
GWENHYWFAR_API GWEN_TREE_ELEMENT *	GWEN_TreeElement_new (void *d)

Macro Definition Documentation

GWEN_DUMMY_EMPTY_ARG

#define GWEN_DUMMY_EMPTY_ARG

Necessary for MSVC compiler because it does not accept a left-out macro argument.

Definition at line 34 of file tree.h.

GWEN_TREE_ELEMENT

#define GWEN_TREE_ELEMENT

(

t

)

GWEN_TREE_ELEMENT *_tree_element;

Use this inside the declaration of a struct for which you want to create lists.

Definition at line 286 of file tree.h.

GWEN_TREE_FINI

#define GWEN_TREE_FINI	(		t,
			element
	)

Value:

  if (element && element->_tree_element) { \
    GWEN_TreeElement_free(element->_tree_element); \
    element->_tree_element=0; \
  }

Use this in your code file (*.c) inside the fini code for the struct you want to use in lists (in GWEN these are the functions which end with "_free".

Definition at line 571 of file tree.h.

GWEN_TREE_FUNCTION_DEFS

#define GWEN_TREE_FUNCTION_DEFS	(		t,
			pr
	)		GWEN_TREE_FUNCTION_LIB_DEFS(t, pr, GWEN_DUMMY_EMPTY_ARG)

This macro should be used in applications, not in libraries. In libraries please use the macro GWEN_TREE_FUNCTION_LIB_DEFS.

Definition at line 393 of file tree.h.

GWEN_TREE_FUNCTION_DEFS_CONST

#define GWEN_TREE_FUNCTION_DEFS_CONST	(		t,
			pr
	)		GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, GWEN_DUMMY_EMPTY_ARG)

Definition at line 330 of file tree.h.

GWEN_TREE_FUNCTION_DEFS_NOCONST

#define GWEN_TREE_FUNCTION_DEFS_NOCONST	(		t,
			pr
	)		GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, GWEN_DUMMY_EMPTY_ARG)

Definition at line 333 of file tree.h.

GWEN_TREE_FUNCTION_LIB_DEFS

#define GWEN_TREE_FUNCTION_LIB_DEFS	(		t,
			pr,
			decl
	)

Value:

  GWEN_TREE_FUNCTION_LIB_DEFS_CONST(t, pr, decl) \
  GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST(t, pr, decl)

Use this in public header files to define some prototypes for list functions. Let's assume the type of your list elements is "MYTYPE" and you want to use the prefix "MyType_" for the list functions. The following function prototypes will then be created:

• void MyType_Tree_Add(MYTYPE *element, MYTYPE_TREE *list);
  Adds (appends) a MYTYPE struct at the end of the given list. (We apologize for the unusual argument order here.)
• void MyType_Tree_Del(MYTYPE *element);
  Removes a MyType struct from the list it is enlisted to.
• MYTYPE *MyType_Tree_First(MYTYPE *element);
  Returns the first element of the given list.
• MYTYPE* MyType_Tree_Next(const MYTYPE *element);
  Returns the next list element to the given one (the successor) in its list.
• MYTYPE* MyType_Tree_Previous(const MYTYPE *element);
  Returns the previous list element to the given one (the predecessor) in its list.
• void MyType_Tree_Clear(MYTYPE *element);
  Frees all entries of the given list. This function assumes that there is a function Mytype_free().
• MYTYPE_TREE *MyType_Tree_new();
  Creates a new list of elements of MYTYPE type.
• void MyType_Tree_free(MYTYPE_TREE *l);
  Clears and frees a list of elements of MYTYPE type. All objects inside the list are freed.

Definition at line 384 of file tree.h.

GWEN_TREE_FUNCTION_LIB_DEFS_CONST

#define GWEN_TREE_FUNCTION_LIB_DEFS_CONST	(		t,
			pr,
			decl
	)

Value:

  typedef GWEN_TREE t##_TREE; \
  \
  decl t* pr##_Tree_GetFirst(const t##_TREE *l); \
  decl t* pr##_Tree_GetLast(const t##_TREE *l); \
  decl t* pr##_Tree_GetNext(const t *element); \
  decl t* pr##_Tree_GetPrevious(const t *element); \
  decl t* pr##_Tree_GetBelow(const t *element); \
  decl uint32_t pr##_Tree_GetCount(const t##_TREE *l); \
  decl int pr##_Tree_HasElement(const t##_TREE *l, const t *element); \
  decl t* pr##_Tree_GetFirstChild(const t *element); \
  decl t* pr##_Tree_GetLastChild(const t *element); \
  decl uint32_t pr##_Tree_GetChildrenCount(const t *element); \
  decl t* pr##_Tree_GetParent(const t *element);

Use this macro in your public header files to export only list functions which do not modify a list. This allows your code to return lists which can not be modified by callers. It also prevents callers from creating their own lists (this is sometimes needed).

Definition at line 295 of file tree.h.

GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST

#define GWEN_TREE_FUNCTION_LIB_DEFS_NOCONST	(		t,
			pr,
			decl
	)

Value:

  typedef GWEN_TREE_ELEMENT t##_TREE_ELEMENT; \
  \
  decl void pr##_Tree_Clear(t##_TREE *l); \
  decl t##_TREE* pr##_Tree_new(); \
  decl void pr##_Tree_free(t##_TREE *l); \
  decl void pr##_Tree_AddList(t##_TREE *dst, t##_TREE *l); \
  decl void pr##_Tree_Add(t##_TREE *list, t *element); \
  decl void pr##_Tree_Insert(t##_TREE *list, t *element); \
  decl void pr##_Tree_Del(t *element); \
  decl void pr##_Tree_Replace(t *elToReplace, t *elReplacement); \
  \
  decl void pr##_Tree_AddChild(t *where, t *element); \
  decl void pr##_Tree_InsertChild(t *where, t *element); \
  \
  decl int pr##_Tree_HasChildElement(const t *who, const t *element); \
  decl void pr##_Tree_ClearChildren(t *element); \

Definition at line 311 of file tree.h.

GWEN_TREE_FUNCTIONS

#define GWEN_TREE_FUNCTIONS	(		t,
			pr
	)

Use this inside your code files (*.c). Actually implements the functions for which the prototypes have been defined via GWEN_TREE_FUNCTION_DEFS.

Definition at line 402 of file tree.h.

GWEN_TREE_H

#define GWEN_TREE_H

Definition at line 39 of file tree.h.

GWEN_TREE_INIT

#define GWEN_TREE_INIT	(		t,
			element
	)		element->_tree_element=GWEN_TreeElement_new(element);

Use this in your code file (*.c) inside the init code for the struct you want to use in lists (in GWEN these are the functions which end with "_new".

Definition at line 562 of file tree.h.

Typedef Documentation

GWEN_TREE

typedef struct GWEN_TREE GWEN_TREE

Definition at line 155 of file tree.h.

GWEN_TREE_ELEMENT

typedef struct GWEN_TREE_ELEMENT GWEN_TREE_ELEMENT

Definition at line 156 of file tree.h.

Function Documentation

GWEN_Tree_Add()

GWENHYWFAR_API void GWEN_Tree_Add	(	GWEN_TREE *	l,
		GWEN_TREE_ELEMENT *	el
	)

Adds (appends) a toplevel tree element. (This operation is also called "append" or "push_back" elsewhere.)

Definition at line 65 of file tree.c.

References DBG_ERROR, GWEN_LOGDOMAIN, and NULL.

Referenced by GWEN_Tree_AddList().

Here is the caller graph for this function:

GWEN_Tree_AddChild()

GWENHYWFAR_API void GWEN_Tree_AddChild	(	GWEN_TREE_ELEMENT *	where,
		GWEN_TREE_ELEMENT *	el
	)

Add a child below the given element.

Definition at line 234 of file tree.c.

References DBG_ERROR, and GWEN_LOGDOMAIN.

GWEN_Tree_AddList()

GWENHYWFAR_API void GWEN_Tree_AddList	(	GWEN_TREE *	dest,
		GWEN_TREE *	l
	)

Adds (appends) the second list to the end of the first list. (This operation is also called "append" or "concatenate" elsewhere.) The second list will be empty upon return.

Definition at line 91 of file tree.c.

References GWEN_Tree_Add(), and GWEN_Tree_Del().

Here is the call graph for this function:

GWEN_Tree_Del()

GWENHYWFAR_API void GWEN_Tree_Del

(

GWEN_TREE_ELEMENT *

el

)

Deletes (removes) a tree element from the tree it used to belong to. The tree element is not free'd or anything, it is only removed from the list it used to belong to. (This operation is also called "remove" or "unlink" elsewhere.)

Definition at line 129 of file tree.c.

References DBG_ERROR, GWEN_LOGDOMAIN, and NULL.

Referenced by GWEN_Tree_AddList(), and GWEN_TreeElement_free().

Here is the caller graph for this function:

GWEN_Tree_free()

GWENHYWFAR_API void GWEN_Tree_free

(

GWEN_TREE *

l

)

Free (delete) an existing list. The list elements are untouched by this function; they need to be freed beforehand.

Definition at line 48 of file tree.c.

References GWEN_FREE_OBJECT.

GWEN_Tree_GetCount()

GWENHYWFAR_API int GWEN_Tree_GetCount

(

const GWEN_TREE *

l

)

Returns the number of elements in this list. This value is cached in the list structure, so this function is a cheap function.

Definition at line 57 of file tree.c.

GWEN_Tree_GetFirst()

GWENHYWFAR_API void * GWEN_Tree_GetFirst

(

const GWEN_TREE *

l

)

Returns the data pointer of the first list element.

Definition at line 284 of file tree.c.

GWEN_Tree_GetLast()

GWENHYWFAR_API void * GWEN_Tree_GetLast

(

const GWEN_TREE *

l

)

Returns the data pointer of the last list element.

Definition at line 293 of file tree.c.

GWEN_Tree_Insert()

GWENHYWFAR_API void GWEN_Tree_Insert	(	GWEN_TREE *	l,
		GWEN_TREE_ELEMENT *	el
	)

Inserts (prepends) a toplevel tree element at the beginning of the list. (This operation is also called "prepend" or "push_front" elsewhere.)

Definition at line 106 of file tree.c.

References DBG_ERROR, GWEN_LOGDOMAIN, and NULL.

GWEN_Tree_InsertChild()

GWENHYWFAR_API void GWEN_Tree_InsertChild	(	GWEN_TREE_ELEMENT *	where,
		GWEN_TREE_ELEMENT *	el
	)

Insert a child below the given element.

Definition at line 260 of file tree.c.

References DBG_ERROR, GWEN_LOGDOMAIN, and NULL.

GWEN_Tree_new()

GWENHYWFAR_API GWEN_TREE * GWEN_Tree_new

(

void

)

Allocate (create) a new empty list.

Definition at line 39 of file tree.c.

References GWEN_NEW_OBJECT.

GWEN_Tree_Replace()

GWENHYWFAR_API void GWEN_Tree_Replace	(	GWEN_TREE_ELEMENT *	elToReplace,
		GWEN_TREE_ELEMENT *	elReplacement
	)

Replaces a tree element with another one, so the replacement takes the place of the given element. The given element to replace is unlinked in the process and can be free'd. The replacement MUST NOT be part of any tree.

Definition at line 173 of file tree.c.

References DBG_ERROR, GWEN_LOGDOMAIN, and NULL.

GWEN_TreeElement_free()

GWENHYWFAR_API void GWEN_TreeElement_free

(

GWEN_TREE_ELEMENT *

el

)

Free (delete) a list element structure.

Definition at line 316 of file tree.c.

References DBG_ERROR, GWEN_FREE_OBJECT, GWEN_LOGDOMAIN, and GWEN_Tree_Del().

Here is the call graph for this function:

GWEN_TreeElement_GetBelow()

GWENHYWFAR_API void * GWEN_TreeElement_GetBelow

(

const GWEN_TREE_ELEMENT *

el

)

Returns the element which is logically below the given one. The order of search is this:

• first child of the given element
• next neighbour of the given element
• loop for every parent: check next neighbour of the given element's parent (if any)

Definition at line 349 of file tree.c.

References NULL.

GWEN_TreeElement_GetChildrenCount()

GWENHYWFAR_API uint32_t GWEN_TreeElement_GetChildrenCount

(

const GWEN_TREE_ELEMENT *

el

)

Returns the number of children of the given element

Definition at line 397 of file tree.c.

GWEN_TreeElement_GetFirstChild()

GWENHYWFAR_API void * GWEN_TreeElement_GetFirstChild

(

const GWEN_TREE_ELEMENT *

el

)

Returns the first child of the given element.

Definition at line 370 of file tree.c.

References NULL.

GWEN_TreeElement_GetLastChild()

GWENHYWFAR_API void * GWEN_TreeElement_GetLastChild

(

const GWEN_TREE_ELEMENT *

el

)

Returns the last child of the given element.

Definition at line 379 of file tree.c.

References NULL.

GWEN_TreeElement_GetNext()

GWENHYWFAR_API void * GWEN_TreeElement_GetNext

(

const GWEN_TREE_ELEMENT *

el

)

Returns the data pointer of the list element that is the next one (successor) to the given one in its list. If there is no such prepending list element, returns NULL.

Definition at line 340 of file tree.c.

GWEN_TreeElement_GetParent()

GWENHYWFAR_API void * GWEN_TreeElement_GetParent

(

const GWEN_TREE_ELEMENT *

el

)

Definition at line 388 of file tree.c.

References NULL.

GWEN_TreeElement_GetPrevious()

GWENHYWFAR_API void * GWEN_TreeElement_GetPrevious

(

const GWEN_TREE_ELEMENT *

el

)

Returns the data pointer of the list element that is the previous (predecessor) to the given one in its list. If there is no such prepending list element, returns NULL.

Definition at line 331 of file tree.c.

GWEN_TreeElement_new()

GWENHYWFAR_API GWEN_TREE_ELEMENT * GWEN_TreeElement_new

(

void *

d

)

Allocate (create) a new list element structure.

Definition at line 304 of file tree.c.

References GWEN_NEW_OBJECT.