Tree abstraction

Question

This code provides a Tree abstraction.

I would like to finalize the code structure only in tree directory, before starting implementation, because there are multiple conditional compilations, written at the function level.

User code (testing) is yet to be attempted, as it is yet to fill the functions in Tree abstraction.

The main intent of this query is to finalize the code structure.

The code is compiled and linked successfully.

/code
$ ls -LR
.:
list  testList.c testTree.c  tree  type.h

./list:
arrayImpl.c  linkedListImpl.c  list.h

./tree:
binarySearchTree.c  binaryTree.c  lcrsImpl.c  multiWalkImpl.c  tree.h

---

type.h

This file provides some system headers:

/********* type.h ********/
#ifndef TYPE_H
#define TYPE_H /* Header guard */
 #include<stdbool.h>
 #include<stddef.h>
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
#endif /* TYPE_H */

---

list.h

This is the List abstraction, re-used by Tree abstraction:

/************ list.h ************/

/*
   List is an ordered collection of homogenuous type elements(unique or duplicate).
   List is not designed to have collection of heterogenuous type elements
   All elements in a List are related.
   List is mutable
   Each element has a position.
   If an element is deleted, then still the remaining elements sit in new order.

   Array implementation of List
   Linked implementation of List
*/

#ifndef LIST_H /* Header guard */
#define LIST_H
#include"type.h"

/***************** Usage-start ************/

#if defined(ARRAY) || (LINKED_LIST)

  /* To ensure Encapsulation(i.e., maintain invariants of array & linked list)
     So, Just provide the `List` declartion, to avoid mis-use of `List`
  */
  typedef struct List List;

#else
  #error "Wrong list implementation macro name !!!"
#endif


 void listInsertItem(List *, void *newItem);
 void *listDeleteItem(List *, int listIndex);
 void *listDeleteLastItem(List *);
 void *listDeleteFirstItem(List *);
 const void *listGetItem(List *, int index); /* 'index' is array index */
 int listGetSize(List *);

 List* createList();
 bool freeList(List *);
#endif /* LIST_H */

/***************** Usage-end ***************/

---

arrayImpl.c

/***************** arrayImpl.c **************/

#include"list/list.h"

#if defined(ARRAY)
typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;
static List *resizeList(List *, ListResizeOperation);


/************ Representation - start ************/
typedef struct List{
  void **array;

  /* Housekeeping - Array enhancement/shrink */
  int lastItemPosition;
  int size;
}List;

#define INITIAL_LIST_SIZE 50
#define FIRST_ITEM_INDEX 0
/********************* Representation - end ************/


/************* Usage - start ***************/
List *createList(){

    List *list = malloc(sizeof(List));
    if(list != NULL){

      list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
      if(list->array != NULL){

        /* Is it safe to initialise zero to  array of  pointers? */
        list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *));
      }else{
        return NULL;
      }
      list->lastItemPosition = -1;
      list->size = INITIAL_LIST_SIZE;
      return list;
    }else{
      return NULL;
    }
}

bool freeList(List *list){

  if(list != NULL){

    int index = 0;
    while( index < list->size){
      free(list->array[index]);
    }

    free(list->array);
    free(list);
    return true;
  }else{

    return false;
  }
}

int listGetSize(List *list){
  if(list != NULL){
    return list->size;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

const void *listGetItem(List *list, int index){
  if((index >=0) && (index < list->size)){
    return (const void *)list->array[index];
  }else{
    return NULL;
  }
}

void listInsertItem(List *arrayList, void *newItem){

  /* House keeping - Enhance the array */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = resizeList(arrayList, DOUBLE_THE_LIST);
    if(arrayList == NULL){
      fprintf(stderr, "insertItem() - Unable to allocate memory \n");
      exit(1);
    }
  }


  /* Insert new element - O(1) operation */
  arrayList->array[++(arrayList->lastItemPosition)] = newItem;
}


void *listDeleteItem(List *arrayList, int listIndex){

  void *returnElement  = arrayList->array[listIndex];

  /* Delete operation - O(n) operation */
  for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
    arrayList->array[accumulator] = arrayList->array[accumulator + 1];
  }

  arrayList->lastItemPosition--;


  /* House keeping - Half the list */
  if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
      arrayList = resizeList(arrayList, HALF_THE_LIST);
      if(arrayList == NULL){
        fprintf(stderr, "deleteItem() - Unable to allocate memory \n");
        exit(1);
      }
    }
  }
  return returnElement; /* User must free this element*/

}

void * listDeleteLastItem(List *arrayList){
  return listDeleteItem(arrayList, arrayList->lastItemPosition);
}

void *listDeleteFirstItem(List *arrayList){
  return listDeleteItem(arrayList, FIRST_ITEM_INDEX);
}

/******************** Usage - end *******************/

---

linkedListImpl.c

/**********linkedListImpl.c ***********/

#include"type.h"

#if defined(LINKED_LIST)



/***************** Representation - start ******************/
  /* struct members are not visible to other .c files */
  struct DListNode{
    void *item;
    struct DListNode *next;
    struct DListNode *prev;
  };

  /* Should be used in this .c file, only, so static */
  typedef struct DListNode DListNode;
  static DListNode* createNode(void *);


  /* struct members are not visible to other .c files */
  typedef struct List{

    DListNode *head;
    int size; /*size attribute is not part of list definition, but quick way to help user code */
  }List;

#define SENTINEL_NODE_DATA_ITEM (void *)0

/************ Representation - end *************/
/******** Usage - start **********/

List *createList(){

List *list = (List *)malloc(sizeof(List));
if(list != NULL){
  DListNode *sentinel = createNode(SENTINEL_NODE_DATA_ITEM);
  list->head = sentinel;
  list->head->next = list->head;
  list->head->prev = list->head;
  list->size = 0;

  return list;
}else{
  return NULL;
}

}
bool freeList(List *list){

  if(list != NULL){

    if(list->size > 0){

      int index = 0;
      DListNode *currentNode, *nextNode;
      currentNode = list->head->next;
      do{
        nextNode = currentNode->next;
        free(currentNode->item);
        free(currentNode);
        currentNode = nextNode;
      }while(++index < list->size);
      return true;
    }else{
      return true;
    }
  }else{
    return false;
  }
}


int listGetSize(List *list){
  if(list != NULL){
    return list->size;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

const void *listGetItem(List *list, int index){

  if((index >=0) && (index < list->size)){

    DListNode *node = list->head->next;
    while(index-- > 0){
      node = node->next;
    }
    return (const void *)node->item;
  }else{

    fprintf(stderr, "Invalid index \n");
    return NULL;
  }
}
    /* O(1) operation - insert() operation */
void listInsertItem(List *linkedList, void *newItem){

  DListNode *newNode = createNode(newItem);

  if(linkedList->size == 0){

    linkedList->head->next = linkedList->head->prev = newNode;

  }else{

    /* Link with current last node in the linked list*/
    newNode->prev = linkedList->head->prev;
    linkedList->head->prev->next = newNode;

    /* Link with Sentinel node */
    newNode->next = linkedList->head;
    linkedList->head->prev = newNode;
  }
}

       /* O(n) - delete() operation*/
void *listDeleteItem(List *linkedList, int listIndex){

  int accumulator = 0;
  DListNode *nodeToDelete = linkedList->head->next;

  if(listIndex < linkedList->size){

     while(accumulator++ < listIndex){
      nodeToDelete = nodeToDelete->next;
     }
     nodeToDelete->prev->next = nodeToDelete->next;
     nodeToDelete->next->prev = nodeToDelete->prev;

     linkedList->size++;

     void *item = nodeToDelete->item;
     free(nodeToDelete);
     return item; /* User must delete by casting to free(item); */
  }else{

    fprintf(stderr, "deleteItem() - Invalid Index");
    return NULL;
  }
}

/* O(1) - deleteLastItem() operation */
void *listDeleteLastItem(List *linkedList){


  if(linkedList->size){

    DListNode *nodeToDelete = linkedList->head->prev;
    void *item = nodeToDelete->item;
    nodeToDelete->prev->next = nodeToDelete->next;
    nodeToDelete->next->prev = nodeToDelete->prev;

    free(nodeToDelete);
    return item; /* User must free this item,by casting, free(item) */
  }else{

    return NULL;
  }
}

/* O(1) - deleteFirstItem() operation */
void *listDeleteFirstItem(List *linkedList){


  if(linkedList->size){

    DListNode *nodeToDelete = linkedList->head->next;
    void *item = nodeToDelete->item;
    nodeToDelete->next->prev = nodeToDelete->prev;
    nodeToDelete->prev->next = nodeToDelete->next;

    free(nodeToDelete);
    return item; /* User must free this item,by casting, free(item) */
  }else{

    return NULL;
  }
}

/********** Usage - end *************/

/********** Helper function - start ****************/
/*    createNode() is not visible to the linker(ld)    */

static DListNode *createNode(void * value){

  DListNode *newNode= malloc(sizeof(DListNode));

  newNode->next = newNode;
  newNode->prev = newNode;
  newNode->item = value;

  return newNode;
}

/******** Helper function - end ********/


#endif

---

tree.h

/*************** tree.h ***************************/



#ifndef TREE_H /* Header guard */
#define TREE_H


#if defined(MULTI_WALK) || (BINARY_TREE_USING_ARRAY) || (BINARY_SEARCH_TREE_USING_ARRAY)
  #include"list/list.h" //Using array implementation
#elif defined(LCRS) ||  (BINARY_TREE_USING_NODE) || (BINARY_SEARCH_TREE_USING_NODE)
  #include"type.h"
#else
  #error "Invalid representation\n"
#endif


/****************** Usage-start ************/
#if defined(LCRS)

  typedef struct LCRSTree Tree;

#elif defined(MULTI_WALK)

  typedef struct multiWalkTree Tree;

#elif defined(BINARY_TREE_USING_NODE) || (BINARY_TREE_USING_ARRAY)

  typedef struct BinaryTree Tree;

#elif defined(BINARY_SEARCH_TREE_USING_NODE) || (BINARY_SEARCH_TREE_USING_ARRAY)

 typedef struct BinarySearchTree Tree;

#endif


typedef void (*visitFunc)(void *);

Tree * newTree(void);
bool destroyTree(Tree *);


#if defined(LCRS) || (MULTI_WALK)

 typedef void* (*parseFunc)(void *);
 void treeInsertItem(Tree *, void *item, parseFunc);
 void* treeDeleteItem(Tree *, void *item, parseFunc);

#elif defined(BINARY_TREE_USING_NODE) || (BINARY_TREE_USING_ARRAY) || (BINARY_SEARCH_TREE_USING_NODE) || (BINARY_SEARCH_TREE_USING_ARRAY)

 void treeInsertItem(Tree *, void *item);
 void* treeDeleteItem(Tree *, void *item);

#endif


void preOrderTraversal(Tree*, visitFunc);
void postOrderTraversal(Tree *, visitFunc);
void breadthFirstTraversal(Tree *, visitFunc);
void inOrderTraversal(Tree *, visitFunc);

int treeGetSize(Tree *);
/**************** Usage-end ******************/
#endif  /* TREE_H */

---

multiWalkImpl.c

/******************* multiWalkImpl.c*************/
#include"tree.h"


#if defined(MULTI_WALK)

typedef struct treeNode{
  struct treeNode *parent;
  void *item;
  List **childList;
}Node;

typedef struct multiWalkTree{
  Node *root;
  int size;
}Tree;

/*
  Analysis
  ========
  Ignoring the size of actual data, but including the size of pointer pointing
  to data, multi walk tree takes more space compared to LCRS tree
*/

Tree * newTree(void){
  return NULL;
}

bool destroyTree(Tree *t){
  return false;
}

int treeGetSize(Tree *t){
  return 0;
}

void treeInsertItem(Tree *t, void *item, parseFunc f){
  return;
}

void* treeDeleteItem(Tree *t, void *item, parseFunc f){
  return NULL;
}

void preOrderTraversal(Tree *t, visitFunc f){
  return;
}

void postOrderTraversal(Tree *t, visitFunc f){
  return;
}

void  breadthFirsTraversal(Tree *t, visitFunc f){
  return;
}
#endif

---

lcrsImpl.c

/**********************lcrsImpl.c ***********************/
#include"tree.h"


#if defined(LCRS)
  /*******************Representation-start **************/
  typedef struct SiblingTreeNode{
    struct SiblingTreeNode *parent;
    void *item;
    struct SiblingTreeNode *firstChild;
    struct SiblingTreeNode *nextSibling;
  }Node;

  static void postOrderTraverse(Node *, visitFunc);
  static void preOrderTraverse(Node *, visitFunc);
  static void breadthFirstTraverse(Node *, visitFunc);
  typedef struct LCRSTree{
    Node *root;
    int size;
  }Tree;

/******************Representation-end*********************/

/**********************Usage-start************************/

Tree * newTree(void){
  Tree *rootedTree = malloc(sizeof(Tree));
  rootedTree->root = NULL;
  rootedTree->size = 0;
  return rootedTree;
}

bool destroyTree(Tree *t){
  return false;
}

int treeGetSize(Tree *t){
  return 0;
}

void *treeDeleteItem(Tree *t, void *item, parseFunc f){
  return NULL;
}

void treeInsertItem(Tree *rootedTree, void *item, parseFunc f){
  if(rootedTree->root == NULL){

    Node *rootNode = malloc(sizeof(Node));
    rootNode->parent = NULL;
    rootNode->item = item;

    rootNode->firstChild = NULL;
    rootNode->nextSibling = NULL;

    rootedTree->root = rootNode;
    rootedTree->size = 0;
  }else{
  }
}

void preOrderTraversal(Tree *tree, visitFunc f){
  preOrderTraverse(tree->root, f);
}


void postOrderTraversal(Tree *tree, visitFunc f){
  postOrderTraverse(tree->root, f);
}


/*
  Level-order traversal
*/
void breadthFirsTraversal(Tree *t, visitFunc f){
  breadthFirstTraverse(t->root, f);
}

/**********************Usage-end ***************/

/***********************Helper function - start ************/



static void postOrderTraverse(Node *node, visitFunc f){


}

static void preOrderTraverse(Node * node, visitFunc f){

}

static void breadthFirstTraverse(Node *n, visitFunc f){

}

/***************Helper function -end******************/
#endif

---

binaryTree.c

/***************binaryTree.c***************/
#include"tree/tree.h"


#if defined(BINARY_TREE_USING_ARRAY)

/************* Representation-start *************/
typedef struct BinaryTree{
  List **array;
  int size;
}Tree;
/**************Representation-end *****************/

#elif defined(BINARY_TREE_USING_NODE)

/************* Representation-start *************/
typedef struct BinaryTreeNode{
  void *item;
  struct BinaryTreeNode *parent;
  struct BinaryTreeNode *left;
  struct BinaryTreeNode *right;
}Node;

typedef struct BinaryTree{
  Node *root;
  int size;
}Tree;
/**************Representation-end *****************/
static void inOrderTraverse(Node *, visitFunc);
static void postOrderTraverse(Node *, visitFunc);
static void preOrderTraverse(Node *, visitFunc);
static void breadthFirstTraverse(Node *, visitFunc);

#endif



#if defined(BINARY_TREE_USING_NODE) || (BINARY_TREE_USING_ARRAY)

/******************Usage-start *****************/
Tree * newTree(void){
  #if defined(BINARY_TREE_USING_NODE)
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif
  return NULL;
}

bool destroyTree(Tree *t){
  #if defined(BINARY_TREE_USING_NODE)
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif

  return false;
}

void treeInsertItem(Tree *t, void *item){
  #if defined(BINARY_TREE_USING_NODE)
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif

}

void* treeDeleteItem(Tree *t, void *item){
  #if defined(BINARY_TREE_USING_NODE)
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif
  return NULL;
}

int treeGetSize(Tree *t){
  #if defined(BINARY_TREE_USING_NODE)
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif
  return 0;
}

void preOrderTraversal(Tree* t, visitFunc action){
  #if defined(BINARY_TREE_USING_NODE)
      preOrderTraverse(t->root, action);
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif

  /* only iterative - no recursive approach */

}


void inOrderTraversal(Tree *bT, visitFunc action){
  #if defined(BINARY_TREE_USING_NODE)
    inOrderTraverse(bT->root, action);
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif


}

void postOrderTraversal(Tree *t, visitFunc action){
  #if defined(BINARY_TREE_USING_NODE)
    postOrderTraverse(t->root, action);
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif

void breadthFirsTraversal(Tree *t, visitFunc action){
  #if defined(BINARY_TREE_USING_NODE)
    breadthFirstTraverse(t->root, action);
  #elif defined(BINARY_TREE_USING_ARRAY)
  #endif


}

/****************Usage-end ********************/

#endif


#if defined(BINARY_TREE_USING_NODE)

/*****************Helper function-start **************/
static void inOrderTraverse(Node *n, visitFunc action){
}

static void breadthFirstTraverse(Node *n, visitFunc action){

}

static void postOrderTraverse(Node *n, visitFunc action){

}

static void preOrderTraverse(Node *n, visitFunc action){

}
/*****************Helper function-end *****************/

#endif

---

binarySearchTree.c

/***************binarySearchTree.c***************/
#include"tree/tree.h"


#if defined(BINARY_SEARCH_TREE_USING_ARRAY)

/************* Representation-start *************/
typedef struct BinarySearchTree{
  List **array;
  int size;
}Tree;
/**************Representation-end *****************/

#elif defined(BINARY_SEARCH_TREE_USING_NODE)

/************* Representation-start *************/
typedef struct BinarySearchTreeNode{
  void *item;
  struct BinaryTreeNode *parent;
  struct BinaryTreeNode *left;
  struct BinaryTreeNode *right;
}Node;

typedef struct BinarySearchTree{
  Node *root;
  int size;
}Tree;
/**************Representation-end *****************/
static void inOrderTraverse(Node *, visitFunc);
static void postOrderTraverse(Node *, visitFunc);
static void preOrderTraverse(Node *, visitFunc);
static void breadthFirstTraverse(Node *, visitFunc);

#endif


#if defined(BINARY_SEARCH_TREE_USING_NODE) || (BINARY_SEARCH_TREE_USING_ARRAY)
/******************Usage-start *****************/
Tree * newTree(void){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif
  return NULL;
}

bool destroyTree(Tree *t){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif

  return false;
}

void treeInsertItem(Tree *t, void *item){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif

}

void* treeDeleteItem(Tree *t, void *item){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif
  return NULL;
}

int treeGetSize(Tree *t){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif
  return 0;
}

void preOrderTraversal(Tree* t, visitFunc action){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
    preOrderTraverse(t->root, action);
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif

  /* only iterative - no recursive approach */

}


void inOrderTraversal(Tree *bT, visitFunc action){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
    inOrderTraverse(bT->root, action);
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif


}

void postOrderTraversal(Tree *t, visitFunc action){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
    postOrderTraverse(t->root, action);
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif
}

void breadthFirsTraversal(Tree *t, visitFunc action){
  #if defined(BINARY_SEARCH_TREE_USING_NODE)
     breadthFirstTraverse(t->root, action);
  #elif defined(BINARY_SEARCH_TREE_USING_ARRAY)
  #endif


}

/****************Usage-end ********************/

#endif



#if defined(BINARY_SEARCH_TREE_USING_NODE)

/*****************Helper function-start **************/
static void inOrderTraverse(Node *n, visitFunc action){
}

static void breadthFirstTraverse(Node *n, visitFunc action){

}

static void postOrderTraverse(Node *n, visitFunc action){

}

static void preOrderTraverse(Node *n, visitFunc action){

}
/*****************Helper function-end *****************/
#endif

---

Compilation procedure:

To test Multiwalk tree using list:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DMULTI_WALK -DARRAY ./list/*.c ./tree/*.c testTree.c -o testTree

To test Binary tree using list:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DARRAY -DBINARY_TREE_USING_ARRAY ./list/*.c ./tree/*.c testTree.c -o testTree

To test Binary search tree using list:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DARRAY -DBINARY_SEARCH_TREE_USING_ARRAY ./list/*.c ./tree/*.c testTree.c -o testTree

To test LCRS tree:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DLCRS ./tree/*.c testTree.c -o testTree

To test Binary tree using node:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DBINARY_TREE_USING_NODE ./tree/*.c testTree.c -o testTree

To test Binary search tree using node:

1. Sit in code folder,

2. Run command, gcc -Wall -g -I. -DBINARY_SEARCH_TREE_USING_NODE ./tree/*.c testTree.c -o testTree

---

Users of Tree abstraction:

1. Priority queue can be implemented efficiently using LCRS implementation of N-ary tree (N <= 2).

2. State propagation tree, shown here, can be implemented using multi walk tree

3. Ordered data can be maintained by a binary search tree

4. Expression trees can be implemented using a binary tree

---

Questions:

1. Does the code structure that involves conditional compilation, at function level, looks maintainable? If no, can the code get further structured that minimizes conditional compilations?

2. As per this declaration, void inOrderTraversal(Tree *, visitFunc); inOrder traversal is applied on N-ary tree(N>2). As per this answer, does it practically make sense to apply on other than a binary tree?

3. Further, PriorityQueue abstraction code will not be part of tree directory, by definition. It will sit in codedirectory. Please confirm the correction of this approach.

Note: After review of code structure, implementation of the functions would continue. Complete code is here .

Answer 1

This is a lot of code to go through, and I don't have time to go over it all. However, I see several issues just with the array implementation, so I'll discuss those.

createList()

In your createList() function, you will leak memory if you are able to allocate a list structure, but not able to allocate the array for it. In the first else block you need to free the list you created or it will leak.

You also have 3 return statements in the function which makes it a little difficult to follow the flow of control. I recommend having a single return at the end that always returns list. It would look like this (along with fixing the memory leak):

List *createList() {

    List* list = malloc(sizeof(List));
    if (list != NULL) {

        list->array = malloc(INITIAL_LIST_SIZE * sizeof(void*));
        if (list->array != NULL) {

            /* Is it safe to initialise zero to  array of  pointers? */
            list->array = memset(list->array, 0, INITIAL_LIST_SIZE * sizeof (void*));
            list->lastItemPosition = -1;
            list->size = INITIAL_LIST_SIZE;
        } else {
            free(list);
            list = NULL;
        }
    }

    return list;
}

freeList()

It's really odd to have a free method that returns a value. I'm not aware of any others that do. It's also not clear to me that it should matter if a caller passes in NULL for a list. Regardless, none of the code you posted ever calls freeList() or checks its return value, so why keep the return value around?

You have an infinite loop in this function, too. The while loop never increments the index, so it will never end.

There's also a potential crasher in this function if a caller passes in a list that has a NULL pointer for the array member. That shouldn't happen if the caller is always using the createList() function to allocate a List, but if some smart person decides to create their own, it would be nice to handle it gracefully. (And it can be useful during debugging the library itself.) I'd change the function to look like this:

void freeList(List *list) {

    if (list != NULL) {

        if (list->array != NULL) {

            int index = 0;
            while (index < list->size) {

                free(list->array[ index ]);
                index++;
            }

            free(list->array);
        } else {

            // Here you can either print something to stderr, 
            // assert, or something else that you can see while
            // debugging the library, or when callers pass in invalid data
            fprintf(stderr, "Invalid list sent to 'freeList()'.");
        }

        free(list);
    }
}

listGetSize()

I noticed that you changed the naming at this point. The above 2 functions were named <something>List(), while this and the remaining functions are all named list<something>(). I recommend sticking with one or the other. listAllocate() and listFree() seem reasonable, as do getListSize(), getListItem(), etc.

This is another case where I'm not sure whether you should differentiate a NULL List. But if you do want to keep that separate from a 0-length, but actually allocated List, you should return an error value from the function, and make the size be an output parameter. Something like this:

int listGetSize(List *list, int *outSize) {

    int result = NO_ERROR;
    if (list != NULL) {
        *outSize = list->size;
    } else {
        fprintf(stderr, "List is NULL\n");
        result = INVALID_LIST;
    }

    return result;
}

You might also want to make the List structure's size member and the outSize parameter be of type size_t which has some guarantees about being able to hold any number of elements you could actually allocate.

listGetItem()

Since the index parameter is never changed in the function, it should be marked as const. It should probably also be an unsigned type since it's not valid to be less than 0. That would get rid of at least one condition in the function.

This function also doesn't check whether the List is valid or not. If NULL is passed in, it will crash. As with the other functions, you need to decide whether that should return an error value (in which case the current return value will need to become a parameter), or whether a NULL list is valid and the return value is just NULL, too. I'd make it consistent with whatever you decide for the other functions.

listInsertItem()

It's fairly surprising that if there's no memory to insert the item, any application using this library will exit. I don't expect my libraries to unceremoniously exit on me when an error occurs. I expect them to tell me about it. Since the function doesn't currently return a value, why not return an error code that indicates success or failure?

Also, there's no check to see if the List that's passed in is valid. In this case, there's no logical thing to do when it is, other than return an error.

listDeleteItem()

This has similar issues to listInsertItem() in that it doesn't detect an invalid List being passed in, and it can exit unexpectedly.

I would recommend using the memmove() function from string.h to do the moving of elements past the selected index back by 1. It's a single call and is likely highly optimized for your architecture.

listDeleteFirstItem()

I wouldn't bother with a named constant for the first index. In C, the first index is always 0.

Answer 2

Looking at the tree implementation I have to say that this is really ambitious. It's a great way to learn how these algorithms work. Kudos to you!

That said, if you're going to use these types of data structures and algorithms professionally, I'd recommend using an existing library. In 30 years of professional development, I've never had to write my own, and the few times I tried, I've ended up with subtle bugs.

Main Issues

As it currently stands, I see 2 main issues:

1. When I start development of a project, I may not know which particular implementation of a container I need. I may have a general idea that I need a tree, but not have a specific one in mind. Making me set a bunch of #defines just to get working seems cumbersome.
2. As it currently stands, a user of this code can't have more than one type of tree in same file due to macros. If I needed to, say, put incoming network packets into a priority queue, then as I pull them out I need to put them into a binary search tree, I can't because I can only define Tree as being one of those 2 things. At least, I can't do it in the same file. That seems problematic to me.

Documentation

What is a "multi-walk" tree? An LCRS tree? I've never heard either term. I can look up LCRS Tree in Wikipedia or whatever and figure out which one it is, but it sure would be nice to have a link in a comment somewhere. Or at least expand the acronym once. I've used these plenty of times but never heard it called by that name. As for "multi-walk" tree, I can't find any information on what that is. Because the words "walk" and "tree" have such common meanings, my searches turned up nothing useful. (There were 2 Stack Overflow results, but both have since been deleted!) So you should probably at least document something basic about that type of tree, or list some synonyms, or link to something that explains it.

Interfaces

It seems like the point of having all these different types of trees, but requiring the user to define which one to use is that they share the same interface. This is like defining an abstract base class called Tree, which is very useful. But it turns out they don't share the same interface! LCRS and Multi-walk have different insert/delete function prototypes and the other trees don't have a parseFunc type definition. So that's a little odd. I would make the parseFunc be a member of the implementations of the LCRS and Multi-walk trees and not pass the function in to the insert/delete item functions. However, that may mean having to have different newTree() functions, as you generally want members to be fully defined after creating a new instance. It's a tricky problem.

Looking at all this, it occurs to me that you're manually reinventing object-oriented programming with this approach. You've got an abstract base class (or interface), you've got inheritance, and you've got polymorphism. Is there a reason why you don't just write this in an object-oriented language? It seems very well suited for this particular job.

Naming

As I mentioned in the arrayImpl answer, you've named things a little oddly. You have <something>Tree() and tree<something>() names. You should make them consistent. I notice you also named the deallocation function destroyTree() whereas other deallocation functions are named free<something>(). It would be good to make those consistent as well.

Don't Repeat Yourself

What's the difference between an LCRS tree, a binary tree, a binary search tree, and a multi-walk tree with only 2 siblings per node? They look like the same thing to me. Maybe it makes sense to only have the multi-walk tree, but have a flag the user can set to say "this is an LCRS tree", or whatever type it is? Otherwise, I feel like you're going to write the same code several times.

Answers

To answer your actual questions:

1. Does the code structure that involves conditional compilation, at function level, looks maintainable? If no, can the code get further structured that minimizes conditional compilations?

It's probably maintainable, but I don't feel it's very usable for the reasons stated at the beginning. Mainly that I can't use 2 different types of tree at the same time. Also, having the user of the code pick which type may not be the best idea.

2. As per this declaration, void inOrderTraversal(Tree *, visitFunc); inOrder traversal is applied on N-ary tree(N>2). As per this answer, does it practically make sense to apply on other than a binary tree?

I've never heard of that happening. Do you know of any uses for it? If not, then I'd say YAGNI (You aren't going to need it), so don't make it an option.

3. Further, PriorityQueue abstraction code will not be part of tree directory, by definition. It will sit in codedirectory. Please confirm the correction of this approach.

I think making a PriorityQueue type that internally uses (or even is) a Tree is a fine idea. Users of a priority queue don't care how it's implemented, so long as it works and meets their performance criteria.

EDIT Question from comments:

Do you have any comments on the way every function is conditionally compiled using macros?

I feel like I covered this above, but to make it more clear: personally, I don't like it. If you are working in some sort of constrained environment such as an embedded processor and absolutely need to keep binary size to a minimum, then it's probably worth doing. Otherwise, it makes using the code a lot harder. A user of this code now has to know what type of Tree they're going to use, and what it's going to be backed by (a linked list or array). The savings in code size will be insignificant on a modern desktop or mobile device. Also, maintaining it seems harder than it needs to be. Any time you change the interface, you now have to update each implementation and compile and test them. Because you can only have one at a time, that likely means compiling several different projects. It's very likely to miss something in the process.

Answer 3

I see a number of things that may help you improve your code. I'll mostly leave it to others to review the code itself; I'll concentrate on the meta-issue of code organization and build structure.

Use modern build tools

The build instructions are complex. A complex build should really have a build tool. One could use make, but these days, I prefer to use cmake. A significant advantage of cmake is that it is cross-platform and provides for an easy way to do out-of-tree builds. It's true that autotools does the latter, but is limited to Linux-like environments.

Fix the bugs

The arrayImpl.c file can't compile because of the missing implementation of resizeList. There is also a missing #endif at the end of the file -- perhaps these are related.

The #includes are part of the interface

Don't do this:

#include "type.h"

First, it is too easily confused with <ctype.h>, but more importantly, it's poor practice. Instead, you should think very carefully about which things are required for the interface and only include those in the .h file, and then which things are required for the implementation and only include those in the .c file. This way, the interface and the implementation are less tightly coupled and one can more easily maintain them separately.

Rethink your code structure

The real point to this code appears to be to have multiple implementations, perhaps to be able to choose the one best suited to the task. Unfortunately, the way it's all defined, there is no simple way to test multiple implementations to choose the best one. Also, there are potentially some problems if one wished to use multiple structures simultaneously. For example, Using a tree based on a linked list would prevent using a list based on an array within the same code. That makes this code much harder to reuse than it should be.

Consider the user

A user of this code might want to be able to use the code without necessarily having to worry about all of the details of the implementation. It would also be best if one could easily change the underlying structure and also to be able to use multiple versions in the same code without restriction.

Create libraries

Instead of doing all of this with error prone #if macros, it would probably be better to simply create these different implementations as completely separate implementations (each with .h and .c files) and create them as libraries. If a user wanted to use an array list, they could use an arrayList. Having the List typedef is counterproductive and dangerous because the listDeleteItem() for an arrayList cannot and should not be used on a linkedList type. I'd package each with a unique and appropriate name and then compile each as a shared library, allowing for both dynamic use and simplifying testing.

In particular, compiling everything with conditional macros might be a reasonable idea for code which was intended, say, for an embedded system and there is expected to be only one optimal way to code a particular routine. I've written such code myself, for example, when the code was cryptographic code for which the performance was intended to be optimal, but that would take different forms depending on the exact model of processor on which the code was run. However, that's clearly not the case here, because there are uses for trees of various kinds that are implemented in the current code. For that reason, unless there is a very compelling reason to do otherwise, I'd highly recommend simply using different names for each data structure implementation and allowing the user to pick which combinations are used rather than forcing the user to pick only and exactly one.

Additionally, from a maintenance aspect, it's going to be difficult to maintain and expand, and even more difficult to make sure that everything is tested adequately using the existing framework.