Tree abstraction

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
 #include
 #include
 #include
 #include
#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 /
in

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 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 List(), while this and the remaining functions are all named list(). 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

StackExchange Code Review Q#150830, answer score: 4