Symbol tableIt is key-value pair abstractionInsert a value with specified keyGiven a key, search for the corresponding valueHere is the design for symbol table implementation for frequency counting of words:Code directory structure:./Code$.:fileIO  list  ST tinyTale type.h frequencyCounter.c frequencyCounter.exe./fileIO:file.h  fileReading.c./list:arrayImpl.c   config.c virtualImplLayer.c linkedListImpl.c  list.h listHandler.h  listInterface.h  ./ST:implWithArray.c  ST.hData input:tinyTale(data)it was the best of timesit was the worst of timesit was the age of wisdomit was the age of foolishnessit was the epoch of beliefit was the epoch of incredulityit was the season of lightit was the season of darknessit was the spring of hopeit was the winter of despairtype.h/********* type.h ********/ #include<stdbool.h> #include<stddef.h> #include<stdlib.h> #include<stdio.h> #include<string.h> #include<time.h>list.h/************ 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#includetype.h/***************** Usage-start ************/  /* 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; typedef int (*compareTo)(const void *, const void *); typedef bool (*isLess)(const void *, const void *); typedef bool (*isEqual)(const void *, const void *);#endiflistHandler.h/***********listHandler.h ***********/#ifndef LISTHANDLER_H#define LISTHANDLER_H#includelist/list.htypedef struct {         bool(*canHandle)(char*);        List*(*createList)(void);         void(*freeList)(List*);         void(*swim)(List*, int, isLess);         void(*sink)(List*, int, isLess);        void*(*listDeleteMaxElement)(List*, isLess);        void*(*sortedListDeleteMaxElement)(List*);          int(*listGetSize)(List*);  const void*(*listGetItem)(List*, const int);        List*(*sortedListInsertItem)(List*, void*, compareTo);         void(*listInsertItem)(List*, void*);        void*(*listDeleteItem)(List*, int);        void*(*listDeleteLastItem)(List*);        void*(*listDeleteFirstItem)(List*);         int(*linearSearch)(const void*, List*, size_t, compareTo);        void*(*binarySearch)(const void*, List*, size_t, compareTo);         void(*insertionSort)(List*, size_t, isLess);         void(*mergeSort)(List*, size_t, isLess);         void(*swap)(List*, int, int);}ListHandler;/*  config.c lookup below 2 global symbols created in impl handlers,   before linking time, so extern keyword*/extern ListHandler arrayImplHandler;extern ListHandler linkedListImplHandler;/*  viml.c lookup below global symbol created in config.c,   before linking time, so extern keyword*/extern ListHandler *listHandlers[];/* Prototypes for definitions in viml.c - start ********/        List* vCreateList(char *);         void vFreeList(List*, char *);         void vSwim(List*, int, isLess, char *);         void vSink(List*, int, isLess, char *);        void* vListDeleteMaxElement(List*, isLess, char *);        void* vSortedListDeleteMaxElement(List*, char *);          int vListGetSize(List*, char *);  const void* vListGetItem(List*, const int, char *);        List* vSortedListInsertItem(List*, void*, compareTo, char *);         void vListInsertItem(List*, void*, char *);        void* vListDeleteItem(List*, int, char *);        void* vListDeleteLastItem(List*, char *);        void* vListDeleteFirstItem(List*, char *);          int vLinearSearch(const void*, List*, size_t, compareTo, char *);        void* vBinarySearch(const void*, List*, size_t, compareTo, char *);         void vInsertionSort(List*, size_t, isLess, char *);         void vMergeSort(List*, size_t, isLess, char *);         void vSwap(List*, int, int, char *);/*****End ***********************************************/#endiflistInterface.h#includelist/listHandler.h#ifndef LISTINTERFACE_H#define LISTINTERFACE_H/*********** User Interface - start *****************/#define createList()                   vCreateList(argv[1])#define freeList(a)                    vFreeList(a, argv[1])#define swim(a, b, c)                  vSwim(a, b, c, argv[1])#define sink(a, b, c)                  vSink(a, b, c, argv[1])#define deleteMax(a, b)                vListDeleteMaxElement(a, b, argv[1])#define sortDeleteMax(a)               vSortedListDeleteMaxElement(a, argv[1])#define getSize(a)                     vListGetSize(a, argv[1])#define getItem(a, b)                  vListGetItem(a, b, argv[1])#define sortInsertItem(a, b, c)        vSortedListInsertItem(a, argv[1])#define insertItem(a, b)               vListInsertItem(a, b, argv[1])#define deleteItem(a, b)               vListDeleteItem(a, b, argv[1])#define deleteLastItem(a)              vListDeleteLastItem(a, argv[1])#define deleteFirstItem(a)             vListDeleteFirstItem(a, argv[1])#define lSearch(a, b, c, d)            vLinearSearch(a, b, c, d, argv[1])#define bSearch(a, b ,c, d)            vBinarySearch(a, b, c, d, argv[1])#define callInsertionSort(a, b, c)     vInsertionSort(a, b, c, argv[1])#define callMergeSort(a, b, c)         vMergeSort(a, b, c, argv[1])#define swap(a, b, c)                  vSwap(a, b, c, argv[1])/*********** User Interface - end *****************/#endifvirtualImplLayer.c#include list/listHandler.h/*****Private symbol - start *****************/static ListHandler * findListImplHandler(char *);/*****Private symbol - end   *****************//***** User interface - start *************/List* vCreateList(char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    List *list = listHandler->createList();    return list;  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void vFreeList(List *list, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->freeList(list);    return;  }  fprintf(stderr, No implementation for this feature\n);}void vSwim(List *list, int parentIndex, isLess less, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->swim(list, parentIndex, less);    return;  }  fprintf(stderr, No implementation for this feature\n);}void vSink(List *list, int index, isLess less, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->sink(list, index, less);    return;  }  fprintf(stderr, No implementation for this feature\n);}void* vListDeleteMaxElement(List *list, isLess less, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listDeleteMaxElement(list, less);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void* vSortedListDeleteMaxElement(List *list, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->sortedListDeleteMaxElement(list);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}int vListGetSize(List *list, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listGetSize(list);  }  fprintf(stderr, No implementation for this feature\n);  return -1;}const void* vListGetItem(List *list, const int index, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listGetItem(list, index);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}List* vSortedListInsertItem(List *list, void *item, compareTo compare, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    list = listHandler->sortedListInsertItem(list, item, compare);    return list;  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void vListInsertItem(List *list, void *item, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->listInsertItem(list, item);    return;  }  fprintf(stderr, No implementation for this feature\n);}void* vListDeleteItem(List *list, int listIndex, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listDeleteItem(list, listIndex);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void* vListDeleteLastItem(List *list, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listDeleteLastItem(list);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void* vListDeleteFirstItem(List *list, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->listDeleteFirstItem(list);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}int vLinearSearch(const void *key, List *list, size_t size, compareTo compare, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->linearSearch(key, list, size, compare);  }  fprintf(stderr, No implementation for this feature\n);  return -1;}void* vBinarySearch(const void *key, List *list, size_t size, compareTo compare, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    return listHandler->binarySearch(key, list, size, compare);  }  fprintf(stderr, No implementation for this feature\n);  return NULL;}void vInsertionSort(List *list, size_t size, isLess less, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->insertionSort(list, size, less);    return;  }  fprintf(stderr, No implementation for this feature\n);}void vMergeSort(List *list, size_t size, isLess less, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->mergeSort(list, size, less);    return;  }  fprintf(stderr, No implementation for this feature\n);}void vSwap(List *list, int i, int j, char *argvOneOption){  ListHandler *listHandler = findListImplHandler(argvOneOption);  if(listHandler != NULL){    listHandler->swap(list, i, j);    return;  }  fprintf(stderr, No implementation for this feature\n);}/***** User interface -end *************//*****Private symbol - start *****************/static ListHandler * findListImplHandler(char *argvOneOption){  ListHandler *implHandler = NULL;  int handlerIndex = 0;  while(listHandlers[handlerIndex] !=NULL){    implHandler = listHandlers[handlerIndex];    if(implHandler->canHandle(argvOneOption)){      return implHandler;    }    handlerIndex++;  }  return NULL;}/*****Private symbol - end *****************/config.c#includelist/listHandler.hListHandler *listHandlers[] ={  &arrayImplHandler,  &linkedListImplHandler,  NULL // to indicate end of array};arrayImpl.c/***************** arrayImpl.c **************/#includelist/listHandler.h // for 'ListHandler' type/*  typedefs are always local to a file.  'ListResizeOperation' type is used only in array implementation*/typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;/****** Private symbols - start - Not visible to Linker*************/static List *resizeList(List *, ListResizeOperation);static void *bSearchRecur(const void *, void**, int, int, compareTo);static void *bSearchIter(const void *, void **, int, int, compareTo);static void insSort(List *, size_t, isLess);static void merge(void **, void **, int, int, int, isLess);static void mSort(void **, void **, int, int, isLess);static void *delMaxListElem(void **, size_t, isLess);/****** Private symbols - end ********************//*  Representation - start  Public symbol with restricted access to user to its details*/typedef struct List{  void **array;  /* For housekeeping - Array enhancement/shrink */  int lastItemPosition;  int size;}List;#define INITIAL_LIST_SIZE 50#define FIRST_ITEM_INDEX 0/********************* Representation - end ************//************* Public symbols - start ***************/bool canArrayImplHandle(char *argvOneOption){  if(strcmp(argvOneOption, ARRAY) == 0){    return true;  }else{    return false;  }}List *arrayCreate(void){    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;}void arrayFree(List *list){  if(list != NULL){    if(list->array != NULL){      int index = 0;      while( index <= list->lastItemPosition){        free(list->array[index++]);      }      free(list->array);    }else{      fprintf(stderr, Invalid list sent to freeList()\n);    }    free(list);  }}int arrayGetSize(List *list){  if(list != NULL){    return list->lastItemPosition + 1;  }else{    fprintf(stderr, List is NULL\n );    return -1;  }}void *arrayDeleteItem(List *arrayList, int listIndex){  if(arrayList == NULL){    fprintf(stderr, Invalid list \n);    return NULL;  }  void *returnElement = NULL;  if(listIndex < arrayGetSize(arrayList)){    returnElement= arrayList->array[listIndex];  }else{    fprintf(stderr, Invalid index\n);    exit(EXIT_FAILURE);  }  /* 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 * arrayDeleteLastItem(List *arrayList){  return arrayDeleteItem(arrayList, arrayList->lastItemPosition);}void *arrayDeleteFirstItem(List *arrayList){  return arrayDeleteItem(arrayList, FIRST_ITEM_INDEX);}void arraySwap(List *list, int i, int j){  void **array = list->array;  void *tempPointer = array[i];  array[i] = array[j];  array[j] = tempPointer;}void arraySwim(List *list, int index, isLess less){  void **array = list->array;  while(index > 1 &&  less(array[index/2], array[index]) ){    arraySwap(list, index/2, index);    index/=2;  }}void arraySink(List *list, int parentIndex, isLess less){  void **array = list->array;  while( 2*parentIndex <= list->lastItemPosition ){    int childIndex = 2*parentIndex;    if( childIndex < list->lastItemPosition && //larger child                (less(array[childIndex], array[childIndex+1])) ){      childIndex = childIndex + 1;    }    if(!less(array[parentIndex], array[childIndex])) break;    arraySwap(list, parentIndex, childIndex);    parentIndex = childIndex;  }}void *arrayDeleteMaxElement(List *list, isLess less){  if(list != NULL){    void *maxElement= delMaxListElem(list->array, arrayGetSize(list), less);    list->lastItemPosition--;    return maxElement;  }else{    fprintf(stderr, listDeleteMaxElement() - NULL is passed\n);    return NULL;  }  return NULL;}void *sortedArrayDeleteMaxElement(List *list){  if(list != NULL){    void *maxElement= arrayDeleteLastItem(list);    return maxElement;  }else{    fprintf(stderr, sortedListDeleteMaxElement() - NULL is passed\n);    return NULL;  }  return NULL;}const void *arrayGetItem(List *list, const int index){  if((index >=0) && (index < arrayGetSize(list))){    return (const void *)list->array[index];  }else{    return NULL;  }}void arrayInsertItem(List *arrayList, void *newItem){  if(arrayList == NULL){    fprintf(stderr, listInsertItem() -Invalid list \n);    return;  }  /* 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;}List * sortedArrayInsertItem(List *arrayList, void *newItem, compareTo compare){  if(arrayList == NULL){    fprintf(stderr, listInsertItem() -Invalid list \n);    return NULL;  }  List *newlist = arrayCreate();  /* Insert new element - O(n) operation */  int index =0;  for(; index <= arrayList->lastItemPosition; index++){    if( compare(newItem, arrayList->array[index]) > 0){      arrayInsertItem(newlist, arrayList->array[index]);    }    arrayList->array[index] = NULL;  }//end for-loop  arrayInsertItem(newlist, newItem);  for(;index <= arrayList->lastItemPosition; index++){    arrayInsertItem(newlist, arrayList->array[index]);    arrayList->array[index] = NULL;  }  free(arrayList);  arrayList = newlist;  return arrayList;}/**************Searching & Sorting -start **************/int arrayLinearSearch(const void *keyItem, List *list, size_t listSize, compareTo compare){  //printf(arrayLinearSearch() - List size:%d\n, listSize);  if(list != NULL && (listSize > 0)){    void ** array = list->array;    for(int index =0; index < listSize; index++){      if(compare(keyItem, array[index] ) == 0){        //printf(Same key\n);        return index;      }    }  }  return -1;}void *arrayBinarySearch(const void *key, List *list, size_t listSize, compareTo compare){  if(list != NULL && (listSize > 0)){    return bSearchIter(key, list->array, 0, listSize-1, compare);    return bSearchRecur(key, list->array, 0, listSize-1, compare);  }  return NULL;}void arrayInsertionSort(List *list, size_t listSize, isLess less){  if(list!=NULL && (listSize > 0)){    insSort(list, listSize, less);  }}void arrayMergeSort(List *list, size_t listSize, isLess less){  if(list != NULL){    void **aux = malloc(arrayGetSize(list) * sizeof(void*)); //Auxillary shadow copy    if(aux != NULL){      printf(Size of list: %d\n, listSize);      mSort(list->array, aux, 0, listSize-1, less);    }else{      fprintf(stderr, mergeSort() - Malloc failure);      exit(EXIT_FAILURE);    }  }else{    fprintf(stderr, mergeSort() - List is NULL);  }}/****************Public symbols - end *******************//* Private symbols - start - Not visible to Linker****/static void *delMaxListElem(void **array, size_t size, isLess less){  if(size >0){    const void *maxElement = array[0];    int maxElementIndex = 0;    printf(size of list: %d\n, size);    for(int index = 1; index < size; index++){      if( less(maxElement, array[index]) ){        maxElement = array[index];        maxElementIndex = index;      }    }    for(int index = maxElementIndex; index < size-1; index++){      array[index] = array[index+1];// Rearrange array    }    return (void *)maxElement;  }else{    return NULL;  }}static void mSort(void **array, void **aux, int low, int high, isLess less){  if(high <= low) return;  int mid = (low + high)/2;  mSort(array, aux, low, mid, less);  mSort(array, aux, mid+1, high, less);  merge(array, aux, low, mid, high, less);}static void merge(void **array, void **aux, int low, int mid, int high, isLess less){  for(int index = low; index <= high; index++){    aux[index] = array[index]; //Shallow copy  }  printf(Low-%d, Mid-%d, High-%d\n, low, mid, high);  int leftIndex = low; int rightIndex = mid+1;  printf(leftIndex-%d, rightIndex-%d\n, leftIndex, rightIndex);  for(int index = low; index <= high; index++){    if(leftIndex > mid)    /* right array exhausted */  array[index] = aux[rightIndex++];    else if(rightIndex > high) /*left array exhausted*/ array[index] = aux[leftIndex++];    else if( less(aux[rightIndex], aux[leftIndex]) )    array[index] = aux[rightIndex++];    else                                                array[index] = aux[leftIndex++];  }}static void insSort(List *list, size_t listSize, isLess less){  for(int sortedBoundaryIndex = -1; sortedBoundaryIndex < (long long)listSize - 1; sortedBoundaryIndex++){    /*      -1 mean sorted pool is yet to form.       0 mean first element is in sorted pool    */    for(int unSortedElementIndex = sortedBoundaryIndex + 1; unSortedElementIndex > 0; unSortedElementIndex--){      /* Within this loop, sorted pool does not exist, as new element is being compared*/      if(less(list->array[unSortedElementIndex], list->array[unSortedElementIndex-1])){        arraySwap(list, unSortedElementIndex, unSortedElementIndex-1);      }else{        break; //If the unsorted element is > or ==, no swap, Stable sort      }    }  }}static void *bSearchIter(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){  int mid =0;  while(lowerBound <= upperBound){    mid = (lowerBound + upperBound)/2;    if(compare(key, array[mid]) == 0){      return array[mid];    }else if(compare(key, array[mid]) < 0){      upperBound = mid-1;    }else if(compare(key, array[mid]) > 0){      lowerBound = mid + 1;    }  }/* end while */  return NULL;}static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){  if(lowerBound > upperBound) return NULL;  int mid = (lowerBound + upperBound)/2;  if(compare(key, array[mid]) == 0){    return array[mid];  }else if(compare(key, array[mid]) < 0){    return bSearchRecur(key, array, lowerBound, mid-1, compare);  }else { // compare() > 0    return bSearchRecur(key, array, mid+1, upperBound, compare);  }}/* resizeList() is not visible to Linker (ld) */static List *resizeList(List *list, ListResizeOperation opType){  if(opType == DOUBLE_THE_LIST){    list->array = realloc(list->array, 2*(list->size)*sizeof(void *));    if(list->array == NULL){ return NULL; }    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 *));    if(list->array == NULL){ return NULL; }    list->lastItemPosition = list->lastItemPosition;    list->size = (list->size)/2;  }  return list;}/************* helper symbols - end  ************//* config.c requires below symbol */ListHandler arrayImplHandler = {  canArrayImplHandle,  arrayCreate,  arrayFree,  arraySwim,  arraySink,  arrayDeleteMaxElement,  sortedArrayDeleteMaxElement,  arrayGetSize,  arrayGetItem,  sortedArrayInsertItem,  arrayInsertItem,  arrayDeleteItem,  arrayDeleteLastItem,  arrayDeleteFirstItem,  arrayLinearSearch,  arrayBinarySearch,  arrayInsertionSort,  arrayMergeSort,  arraySwap,};linkedListImpl.c/**********linkedListImpl.c ***********/#includelist/listHandler.h // for 'ListHandler' type  /* typedef is alway local to file */  typedef struct DListNode DListNode;  /******Private symbol - start - Not visible to linker *****/  static DListNode* createNode(void *);  /******Helper function - end ******************//***************** Representation - start ******************/  /* Private structure */  typedef struct DListNode{    void *item;    struct DListNode *next;    struct DListNode *prev;  }Node;  /*    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  */  /* Public structure with restricted access to user */  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 *************//****Public symbols - start **********/bool canLinkedListImplHandle(char *argvOneOption){  if(strcmp(argvOneOption, LINKEDLIST) == 0){    return true;  }else{    return false;  }}List *linkListCreate(){    /*      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 = (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;    }}void linkListFree(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;    }else{      return;    }  }else{    fprintf(stderr, Unable to free()\n);    return;  }}void linkListSwim(List *list, int index, isLess less){  return;}void linkListSink(List *list, int parentIndex, isLess less){  return;}void * linkListDeleteMaxElement(List *list, isLess less){  return NULL;}void* sortedLinkListDeleteMaxElement(List *list){  return NULL;}int linkListGetSize(List *list){  if(list != NULL){    return list->size;  }else{    fprintf(stderr, List is NULL\n );    return -1;  }}const void *linkListGetItem(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 linkListInsertItem(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;  }  linkedList->size++;}List* sortedLinkListInsertItem(List *list, void *item, compareTo compare){  return NULL;}       /* O(n) - delete() operation*/void *linkListDeleteItem(List *linkedList, int listIndex){  int nodeIndex = 0;  DListNode *nodeToDelete = linkedList->head->next;  if(listIndex < linkedList->size){     while(nodeIndex++ < 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 free(item); */  }else{    fprintf(stderr, linkListDeleteItem() - List is empty);    return NULL;  }}/* O(1) - deleteLastItem() operation */void *linkListDeleteLastItem(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 *linkListDeleteFirstItem(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;  }}int linkListLinearSearch(const void *keyItem, List *list, size_t listSize, compareTo compare){  Node *nodeToSearch = NULL;  if(listSize > 0){    nodeToSearch = list->head->next;  }else{    return -1;  }  for(int index=0; index < listSize; index++){    if(compare(keyItem, nodeToSearch->item) ==0){      return index;    }    nodeToSearch = nodeToSearch->next;  }  return -1;}void* linkListBinarySearch(const void *key, List *list, size_t size, compareTo compare){  return NULL;}void linkListInsertionSort(List *list, size_t size, isLess less){  return;}void linkListMergeSort(List *list, size_t size, isLess less){  return;}void linkListSwap(List *list, int i, int j){  return;}/******Public symbols - end *************//******Private symbols - start - Not visible to linker*******/static DListNode *createNode(void * value){  DListNode *newNode= malloc(sizeof(DListNode));  newNode->next = newNode;  newNode->prev = newNode;  newNode->item = value;  return newNode;}/****Private symbols - end ********//* 'config.c' lookup below global symbol */ListHandler linkedListImplHandler = {  canLinkedListImplHandle,  linkListCreate,  linkListFree,  linkListSwim,  linkListSink,  linkListDeleteMaxElement,  sortedLinkListDeleteMaxElement,  linkListGetSize,  linkListGetItem,  sortedLinkListInsertItem,  linkListInsertItem,  linkListDeleteItem,  linkListDeleteLastItem,  linkListDeleteFirstItem,  linkListLinearSearch,  linkListBinarySearch,  linkListInsertionSort,  linkListMergeSort,  linkListSwap,};file.h#includelist/listInterface.h#ifndef FILE_H#define FILE_H#define MAX_RECORD_SIZE 256/***************Usage -start **********/typedef void (*PrintCacheItem)(const void *);typedef struct DBCache DBCache;void readDataIntoCache(FILE *, DBCache *, char[], char *, char*[]);void readHeader(FILE *, DBCache *, char[]);DBCache* initCache(FILE *, char *[]);List* getItemList(DBCache*);void printCache(DBCache*, PrintCacheItem, char*[]);void freeCache(DBCache*, char *[]);/***************Usage - end ***********/#endiffileReading.c#includefileIO/file.h#define MALLOC_FAILURE malloc() failed#define FILE_HANDLE_FAILURE Unable to open file#define DELIMITER ,/***************Repr-start ***************/typedef struct DBCache{  List *records;  char *header;  size_t fileSize;  char  *fileDataStream;}DBCache;/*************** Repr-end ******************/static void checkHandleFailure(void *, char *);static void noNewLine(char[]);static void copyData(List *, char [], char *, char *[]);/**************Usage-start **************/List * getItemList(DBCache *cache){  return cache->records;}void readDataIntoCache(FILE *pFile, DBCache *cache, char buf[], char *delim, char *argv[]){  if(pFile == NULL){    checkHandleFailure(pFile, FILE_HANDLE_FAILURE);  }  fseek(pFile, 0, SEEK_SET);  while(fgets(buf, MAX_RECORD_SIZE, pFile) != NULL){    noNewLine(buf);    copyData(cache->records, buf, delim, argv);  }}void readHeader(FILE *pFile, DBCache* cache, char buf[]){  if(pFile == NULL){    checkHandleFailure(pFile, FILE_HANDLE_FAILURE);  }  fseek(pFile, 0, SEEK_SET);  if(fgets(buf, MAX_RECORD_SIZE, pFile) == NULL){    fprintf(stderr, EOF encountered\n);    exit(EXIT_FAILURE);  }  noNewLine(buf);  cache->header = malloc(strlen(buf) + 1);  checkHandleFailure(cache->header, MALLOC_FAILURE);  strcpy(cache->header, buf);  memset(buf, 0, MAX_RECORD_SIZE);}DBCache *initCache(FILE *pFile, char *argv[]){  DBCache *cache = malloc(1*sizeof(DBCache));  checkHandleFailure(cache, MALLOC_FAILURE);  cache->records = createList();  checkHandleFailure(cache->records, MALLOC_FAILURE);  cache->header = NULL;  fseek(pFile, 0, SEEK_END);  cache->fileSize = ftell(pFile) + 1;  cache->fileDataStream = malloc(cache->fileSize * sizeof(char));  fseek(pFile, 0, SEEK_SET);  fgets(cache->fileDataStream, cache->fileSize, pFile);  fseek(pFile, 0, SEEK_SET);  return cache;}void freeCache(DBCache *cache, char *argv[]){  printf(Before freeList());  freeList(cache->records);  printf(After freeList());  if(cache->header != NULL)    free(cache->header);  free(cache->fileDataStream);}void printCache(DBCache * cache, PrintCacheItem printItem, char *argv[]){  List *list = cache->records;  for(int index =0; index < getSize(list); index++){    getItem(list, index);  }  printf(Size of list: %d\n, getSize(list));}/***************Usage-end ***************//******************Helper -start ***********/static void copyData(List *records, char buf[], char *delim, char *argv[]){    char *token =  strtok(buf, delim);    void *item = malloc(strlen(token) +1);    item = memcpy(item, token, strlen(token)+1);    //printf(token-%s\n, token);    while(token != NULL){      insertItem(records, item);      token = strtok(NULL, delim);      //printf(token-%s\n, token);      if(token != NULL){        item = malloc(strlen(token));        memcpy(item, token, strlen(token)+1);      }    }}static void noNewLine(char buf[]){  int len = strlen(buf);  if(len > 0){    if(buf[len-1] == '\n'){      buf[len-1] = '\0';    }  }}static void checkHandleFailure(void *ptr, char *msg){  if(ptr == NULL){    fprintf(stderr, %s\n, msg);    exit(EXIT_FAILURE);  }}/******************Helper - end ***********/ST/ST.h#includelist/listInterface.h#ifndef ST_H#define ST_Htypedef struct ST ST;typedef void *(*UpdateValue)(const void *, const void *);typedef void (*PrintItem)(const void *, const void *);ST* createST(char *[]);void freeST(ST*, char *[]);void *get(ST *, void *, compareTo, char *[]);void put(ST *, void *key, void *value, compareTo, UpdateValue, char *[]);void printKeys(ST *, PrintItem, char *[]);#endifST/implWithArray.c#includeST.h/******* Representation - start *************//*** Private key-value pair structure *******/typedef struct{  void *key;  void *value;  int (*compareKey)(const void *, const void *);}Pair;typedef struct ST{  List *keyValuePairList;}ST;#define MALLOC_FAILURE malloc() failed\n#define NULL_POINTER   Null pointer passed\n/********Representation - end *************/static Pair* createPairItem(void *, void *, compareTo);static int compareItem(const void *, const void *);static void *getValue(const Pair *);static int findItemInST(ST *st, void *, compareTo, char *[]);/***********Public symbol - start ************/ST *createST(char *argv[]){  ST *st = malloc(sizeof(ST));  if(st != NULL){    st->keyValuePairList = createList();    return st;  }  fprintf(stderr, MALLOC_FAILURE);  return NULL;}void freeST(ST *st, char *argv[]){  if(st != NULL){    freeList(st->keyValuePairList);    free(st);    return;  }  fprintf(stderr, NULL_POINTER);}void *get(ST *st, void *key, compareTo compareKey, char *argv[]){  int index = findItemInST(st, key, compareKey, argv);  if(index != -1){    List *list = st->keyValuePairList;    const Pair *listItem = getItem(list, index);    return getValue(listItem);  }  return NULL;}void put(ST *st, void *key, void *value, compareTo compareKey, UpdateValue updateValue, char *argv[]){  void *oldValue = get(st, key, compareKey, argv);  if(oldValue != NULL){    int index = findItemInST(st, key, compareKey, argv);    deleteItem(st->keyValuePairList, index);    value = updateValue(value , oldValue);  }  //Create Pair item only after finalising value  void * newItem = createPairItem(key, value, compareKey);  insertItem(st->keyValuePairList, newItem);}void printKeys(ST *st, PrintItem printItem, char *argv[]){  if(st != NULL){    List *list = st->keyValuePairList;    for(int index = 0; index < getSize(list); index++){      const Pair *pair = getItem(list, index);      printItem(pair->key, pair->value);    }  }}/***********Public symbol - end************/static int findItemInST(ST *st, void *key, compareTo compareKey, char *argv[]){  const Pair * item = createPairItem(key, NULL, compareKey);  List *list = st->keyValuePairList;  int index = lSearch(item, list, getSize(list), compareItem);  return index;}static void *getValue(const Pair *item){  if(item != NULL){    return item->value;  }  return NULL;}static Pair * createPairItem(void *key, void *value, compareTo compareKey){  Pair *item = malloc(sizeof(Pair));  item->key = key;  item->value = value;  item->compareKey = compareKey;  return item;}static int compareItem(const void *item1, const void *item2){  if(item1 != NULL && (item2 != NULL)){    return ((Pair *)item1)->compareKey( ((Pair *)item1)->key,                                        ((Pair *)item2)->key  );  }  return false;}frequencyCounter.c#includeST/ST.h#includefileIO/file.hint compareKey(const void *key1, const void *key2){  return strcmp( (const char *)key1, (const char *)key2 );}void * updateValue(const void *value1, const void *value2){ int sum = *(int *)value1 + *(int *)value2; int *newValue = malloc(sizeof(int)); *newValue = sum; return newValue;}void printItem(const void *key, const void *value){  fprintf(stdout, Key is:'%s', , (const char *)key);  fprintf(stdout, Frequency is:%d\n, *(const int *)value);}int main(int argc, char *argv[]){  if(argc == 1){    fprintf(stderr, usage:\n);    exit(EXIT_FAILURE);  }  FILE *pFile = fopen(tinyTale, r);  if(pFile!= NULL){    DBCache *cache = initCache(pFile, argv);    char buf[MAX_RECORD_SIZE];    readDataIntoCache(pFile, cache, buf,  , argv);    List *list = getItemList(cache);    ST *st = createST(argv);    if(st != NULL){      int *value = malloc(sizeof(int)); *value = 1;      for(int index =0; index < getSize(list); index++){        printf(item:%s\n, (char *)getItem(list, index));        put(st, (void *)getItem(list, index), value, compareKey, updateValue, argv);      }    }    printKeys(st, printItem, argv);    freeST(st, argv);    freeCache(cache, argv);  } //end pFile  fclose(pFile);}Compilation proceduregcc -Wall -Werror -I. ./list/*.c ./fileIO/*.c ./ST/*.c frequencyCounter.c -o frequencyCounterOutput$ ./frequencyCounter.exe ARRAYitem:ititem:wasitem:theitem:bestitem:ofitem:timesitem:ititem:wasitem:theitem:worstitem:ofitem:timesitem:ititem:wasitem:theitem:ageitem:ofitem:wisdomitem:ititem:wasitem:theitem:ageitem:ofitem:foolishnessitem:ititem:wasitem:theitem:epochitem:ofitem:beliefitem:ititem:wasitem:theitem:epochitem:ofitem:incredulityitem:ititem:wasitem:theitem:seasonitem:ofitem:lightitem:ititem:wasitem:theitem:seasonitem:ofitem:darknessitem:ititem:wasitem:theitem:springitem:ofitem:hopeitem:ititem:wasitem:theitem:winteritem:ofitem:despairKey is:'best', Frequency is:1Key is:'worst', Frequency is:1Key is:'times', Frequency is:2Key is:'wisdom', Frequency is:1Key is:'age', Frequency is:2Key is:'foolishness', Frequency is:1Key is:'belief', Frequency is:1Key is:'epoch', Frequency is:2Key is:'incredulity', Frequency is:1Key is:'light', Frequency is:1Key is:'season', Frequency is:2Key is:'darkness', Frequency is:1Key is:'spring', Frequency is:1Key is:'hope', Frequency is:1Key is:'it', Frequency is:10Key is:'was', Frequency is:10Key is:'the', Frequency is:10Key is:'winter', Frequency is:1Key is:'of', Frequency is:10Key is:'despair', Frequency is:1My questions:Can listInterface.h get more readable/easy_to_use for user of List abstraction? Easy to use, because user of List abstraction has to pass its argv parameter to List public API.From a code elegance aspect, can I improve List abstraction?From a code elegance aspect, can I improve ST abstraction?Note: Going further, multiple implementations of ST will adapt the same design as List is implemented.
Word frequency counter - symbol table - array implementation
algorithm;c;object oriented