2
\$\begingroup\$

Here is the Stack abstraction:

/********* stack.h *********/

#include"../list/list.h"

typedef struct Stack Stack;

Stack *createStack();
void push(Stack *, void *item);
void*pop(Stack *);

/*********** stackImpl.c *******/

#include"../list/list.h"

typedef struct Stack{
  List *stack;
}Stack;

Stack* createStack(){

  Stack *s = malloc(sizeof(Stack));
  s->stack = createList((void *)0, CREATE_NEW_LIST);

  return s;
}

void push(Stack *s, void *item){
  insertItem(s->stack, item);
}

void *pop(Stack *s){
  void *item = deleteLastItem(s->stack);
  return item;
}

that re-uses this List 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
*/

#include<stddef.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>

/***************** Usage-start ************/
typedef enum{false, true}bool;
typedef enum {CREATE_NEW_LIST, DOUBLE_THE_LIST, HALF_THE_LIST}Op;

#if defined(ARRAY)

  /* To ensure Encapsultation(i.e., maintain invariants of array) */
  typedef struct List List;

#elif defined(LINKED_LIST)

  /* To ensure Encapsultation(i.e., maintain invariants of linked list) */
  /* User will not get access to node*/
  typedef struct List List;


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


void insertItem(List *, void *newItem);
void deleteItem(List *, int listIndex);
void * deleteLastItem(List *);

List* createList(List *, Op opType);

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

/***************** arrayImple.c **************/

#if defined(ARRAY)

#include"list.h"


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

  /* Following members for Housekeeping - Array enhancement*/
  int lastItemPosition;
  int size;
}List;

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




/************* Usage - start ***************/
List *createList(List *list, Op opType){



  if(opType == CREATE_NEW_LIST){
    list = malloc(sizeof(List));

    list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));


    /* 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 if(opType == DOUBLE_THE_LIST){

    list->array = realloc(list->array, 2*(list->size)*sizeof(void *));

    list->lastItemPosition = list->lastItemPosition;;
    list->size = 2*(list->size);
  }else if(opType == HALF_THE_LIST){

    list->array = realloc(list->array, ((list->size)/2)*sizeof(void *));

    list->lastItemPosition = list->lastItemPosition;
    list->size = (list->size)/2;
  }

  return list;

}

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

  /* House keeping - Enhance the array */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = createList(arrayList, DOUBLE_THE_LIST);
  }


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


  return;
}

void deleteItem(List *arrayList, int listIndex){

  void * element = arrayList->array[listIndex];
  free(element);

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


  /* House keeping - Half the list */
  if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
      arrayList = createList(arrayList, HALF_THE_LIST);
    }
  }
  return;

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

#endif

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

#if defined(LINKED_LIST)

#include"list.h"


/***************** Representation - start ******************/
  typedef struct DListNode{

    void *item;
    struct DListNode *next;
    struct DListNode *prev;
  }DListNode;

  /*
    Reason to introduce 'List' type:

    Problem 1:
     Say, user code has 'x' and 'y' pointing to the same shopping list that is built using 'Node' type.
     Some part of user code update list with new item using 'x'
     'y' is not in sync with this updation
        Node *x = someCreatedList;
        Node *y = x;
        Node *z = malloc(sizeof(Node));
        z->next = x;
        x = z; //y misses that reference.
    Solution:
     Maintain a List type, whose job is to point to head(first node) of the list.
     User code will go via reference of List type


    Problem 2:
     It make sense to have references of 'Node' type pointing to NULL
     Applying operation[insertItem()] on NULL pointer will cause runtime errors
    Solution:
     Run operations over List type because it does not make sense to have reference of SList type pointing to NULL.

    To solve problem1 & problem2, here is 'List' type
  */

typedef struct List{ /* Circular linked list(prev, next) */

  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 *************/






/********** Helper function - start ***********/
DListNode* createNode(void * value){

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

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

  return newNode;
}

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



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

List *createList(List *list, Op opType ){



  if(opType == CREATE_NEW_LIST){

    /*
      Amidst performing insert/delete operations on 'List',

      To reduce the number of special checks, we designate one node as 'SENTINEL'

      After using sentinel, there will be no NULL assignments/check in code.
    */

    list = (List *)malloc(sizeof(List));

    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{

    fprintf(stderr, "Invalid flag passed to createList() \n");
    return (List *)0;
  }


}


}


        /* O(1) operation - insert() operation */
void insertItem(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;
  }

  return;
}

       /* O(n) - delete() operation*/
void deleteItem(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;

     free(nodeToDelete);
  }else{

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


  return;
}

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



  if(linkedList->size){

    DListNode *nodeToDelete = linkedList->head->prev;
    nodeToDelete->prev->next = nodeToDelete->next;
    nodeToDelete->next->prev = nodeToDelete->prev;
    return nodeToDelete;
  }else{
    return (void*)0;
  }
}


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

#endif

Compilation procedure:

  1. Stack using array:

    In the ../list directory:

    $ gcc -DARRAY -c arrayImpl.c -o arrayImpl.o
    

    In the ../stack directory:

    $ gcc -DARRAY main.c stackImpl.c ../list/arrayImpl.o
    
  2. Stack using linked list:

    In the ../list directory:

    $ gcc -DLINKED_LIST -c linkedListImpl -o linkedListImpl.o
    

    In the ../stack directory:

    $ gcc -DLINKED_LIST main.c stackImpl.c ../list/linkedListImpl.o
    

Questions:

  1. Are there any leaks in code re-usability? Leak in terms of ability to re-use code.
  2. How can I avoid declaring List multiple times in List.h?
\$\endgroup\$
  • \$\begingroup\$ "any leaks in code re-usability" --> Are your asking about 1) memory leaks or 2) ability to re-use code? \$\endgroup\$ – chux - Reinstate Monica Dec 21 '16 at 2:56
  • 1
    \$\begingroup\$ @chux ability to re-use code \$\endgroup\$ – overexchange Dec 21 '16 at 3:07
  • 4
    \$\begingroup\$ The term "leak" in a programming context typically reminds of memory leaks or other resource leaks, such as file handles. To avoid confusion, I suggest to avoid using that term for other meanings. \$\endgroup\$ – Stop ongoing harm to Monica Dec 21 '16 at 7:32
4
\$\begingroup\$

Header guards

As has been pointed out in previous reviews you aren't using header guards in your include files. This can cause problems, in addition to slowing down your compile time.

static static static

If you're not planning on exporting functions then you should be declaring them as static to confine them to a translation unit. createNode for example is only used from within 'LinkedListImpl.c'.

Naming

Naming is important to make your code easier to read. It should reflect what is represented. This is particularly important when you're naming types as they are likely to have a longer lifetime / higher visibility than variables. You're defining an enum Op which is passed into createList. The name tells me nothing about what it is the enum is used for.

Leaky abstraction - createList

Your public list interface seems leaky to me. You pass in an Op parameter to your createList method. This parameter has to be CREATE_NEW_LIST for the linked list version, however it can be any of the values for the array implementation. This feels wrong, if you're going to try to allow the type to be changed without the client knowing then the interface needs to work consistently across the different implementations. For this particular issue, I would drop the extra parameter from createList, it makes no sense anyway. The resize functionality should be moved into a static resizeList method in the arrayImpl.c.

Resize

At the moment, resizing is part of your public api, which means that the list clients might perform the action. There are some assumptions built in to the way this resize is performed which means if the client calls it you could get into trouble. What happens if the list is full and the client resizes it to half size, then starts pushing more items?

List is incomplete

Your list advertises 'createList', 'insertItem', 'deleteItem' and 'deleteLastItem'. There's no way to actually access the items in the list. This seems like a critical bit of functionality. The only way to access the items is by calling 'deleteLastItem'.

Missing function

'arrayImpl.c' doesn't contain the function 'deleteLastItem'. As this is a critical method for the stack to work, this should be causing a compilation error.

Leaky abstraction - deleteLastItem

The linked list version of deleteLastItem returns a pointer to the node. It should probably be returning a pointer to the item contained within the node. As a consequence the client is either required to know what the node looks like, or expected to ignore the value.

Inconsistent API

The array list implementation cleans up after inserted elements by calling 'free' on the element when it is removed from the list. The linked list version on the other hand does not perform a free on the item, it only performs a free on the node. This means it's unclear if the list is supposed to be responsible for freeing memory of items contained within it or not.

#if this #elif that

I honestly don't get the point of this. You're essentially doing the same thing in both branches typedef struct List List; You're aborting the build if a macro isn't defined, but you might as well just put the typedef in and let the compiler/linker fail if it needs to.

Other

  • There may typo in the comment in 'arrayImpl.c', which refers to the file as 'arrayImple.c' which is it?
  • It seems strange to me that stackImpl.c includes 'list.h' but not 'stack.h'.
\$\endgroup\$
  • \$\begingroup\$ In include files, I have function declaration and some system headers, which one should be guarded? \$\endgroup\$ – overexchange Dec 22 '16 at 19:34
  • \$\begingroup\$ @overexchange typically, the entire contents of the header is contained in the guard. \$\endgroup\$ – forsvarir Dec 22 '16 at 19:38
  • \$\begingroup\$ From other technician, I learnt this regarding header guard \$\endgroup\$ – overexchange Dec 22 '16 at 19:46
  • \$\begingroup\$ @overexchange It's strange to have a header guard that only guards system includes which is what you've go in your tree.h. I suspect if your #endif /*TREE_H*/ was on line 39 and you hadn't defined a separate TREE_OP guard, you wouldn't have got that comment. \$\endgroup\$ – forsvarir Dec 22 '16 at 20:04
  • \$\begingroup\$ ##1) Line 39, you mean function declaration does not require header guard? ##2) One supplementary question, For rooted tree, I considered lcrs and multi-walk representation.For further coding, How to represent tree that has no root, shown here? \$\endgroup\$ – overexchange Dec 22 '16 at 20:12
5
\$\begingroup\$

1. Reusability:

First of all, if I read the code it, is clear that the writer applied the basic abstraction principles.

  • The main interface (stack) is clearly visible
  • Implementation strictly separated from declaration
  • It is easily possible to modify the implementation without the user of stack noticing the change

Things that might be improved:

  • Check pointers that are passed into stackImpl.c because these functions are used by the user of your implementation and you can't trust it. You might even want to check the pointers passed into your list implementations but that's debateable.
  • Check pointer returned by malloc
  • Use a function deleteStack(stack *s) to ensure that no memory leaks exist
  • int doesn't have a fixed size, it depends on the architecture, therefore a typedef like uint32_t would make sense here.
  • You should have a max size for your stack. Of course, your implementation allows "infinite" entries but somewhere is the physical limit. And you could even implement a warning, e.g. "80% full" so that the user gets a warning that she might want to increase the max stack size (just an idea)
  • ARRAY and LINKED_LIST are very generic terms, be more specific.
  • The #if defined(ARRAY)... #elif... is a bit cumbersome, imagine you have many things to switch on for the implementation of a large project. Then it is just difficult to handle such compiler switches in the compiler statement. There are two solutions for that (maybe more): 1) just define it in list.h which implementation you want to use, but thats problably not what you want. 2) If you want to define in the compiler statement, then keep the name of the implementation the same, e.g. list.c and put them in different folders.
  • Include guards are missing

2. Avoiding declaring List multiple times:

You can use

    #if defined(LINKED_LIST) || defined(ARRAY)

Misc:

Just a few things that I have seen:

  • Keep the style consistent (indentation, brackets)
  • return is not needed when a function doesn't return anything
  • (void*)0 why not just use NULL? It's just easier to read and also to write
  • in createNode newNode->next = newNode and newNode->prev = newNode are superfluous.
  • instead of #if defined(xyz) you can use #ifdef xyz
\$\endgroup\$
  • \$\begingroup\$ Thank you for your point 1. I realized that aspect, but did not include. Point 1 is asking about the ability to re-use code \$\endgroup\$ – overexchange Dec 21 '16 at 3:15
  • \$\begingroup\$ No worries, I associated leak with memory leak, as others already pointed out. I will look into the re-usability later. \$\endgroup\$ – Frode Akselsen Dec 21 '16 at 22:50
  • \$\begingroup\$ Another point, when the user need to pass the objects thru push that in-turn calls insertItem() in List, User need to make sure the data is complete, I mean string is NULL terminated etc.. \$\endgroup\$ – overexchange Dec 22 '16 at 18:18
  • \$\begingroup\$ @overexchange I'm not sure what you want to say with this statement. That fact is clear because the List implementation only stores pointers to the data, not the data itself. btw a string must be '/0' (or NUL, ascii 0x00) terminated, which is not the same as NULL (NULL pointer) \$\endgroup\$ – Frode Akselsen Dec 22 '16 at 22:31
  • \$\begingroup\$ ##1) Yes, List impementation only stores pointer to data. Ideally, Do you think, insertItem() is suppose to make sure that data is complete(consistent)? Because, syntactically, insertItem() accepts any type of data(complete/in-complete). Who owns the responsibility? ##2) Sorry, due to ignorance, I was say Null pointer[(void*)0] instead of NUL ascii character('\0'), in my previous comment \$\endgroup\$ – overexchange Dec 23 '16 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.