Below is the working List abstraction design,

enter image description here

List is a generic abstraction holding any type.

Below is the code directory structure. Currently symbol table(ST) and file api fileIO is using List abstraction.

fileIO  list  ST tinyTale type.h frequencyCounter.c frequencyCounter.exe

file.h  fileReading.c

arrayImpl.c   config.c virtualImplLayer.c linkedListImpl.c  list.h listHandler.h  listInterface.h  

implWithArray.c  ST.h

Below is the relevant code(for improvement),


#ifndef LIST_H /* Header guard */
#define LIST_H

  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 *);



/***********listHandler.h ***********/

typedef struct {

         void(*swim)(List*, int, isLess);
         void(*sink)(List*, int, isLess);
        void*(*listDeleteMaxElement)(List*, isLess);
  const void*(*listGetItem)(List*, const int);
        List*(*sortedListInsertItem)(List*, void*, compareTo);
         void(*listInsertItem)(List*, void*);
        void*(*listDeleteItem)(List*, int);
         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);


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





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

where, listInterface.h is an interface for a user of List abstraction.

All api wth prefix(v) are defined in virtualImplLayer.c.



listInterface.h is not a readable code for user, because it does not possess List typedef which is actually available in list.h and indirectly included via listHandler.h.

2) listInterface.h is not easy to use because user(say fileReading.c) need to pass argv argument to List public api. Public api is given in listInterface.h. User has to run its application passing argv[1] as,

$ ./userapp.exe ARRAY


$ ./userapp.exe LINKEDLIST


Can listInterface.h get more readable & easy to use?

  • How important is it that the end-user can select the implementation of the list abstraction? What would you do if the intended end-user doesn't even know what that means? – Bart van Ingen Schenau Jan 7 '17 at 8:21
  • 1
    @BartvanIngenSchenau ##1) If the end user need list container for his applications then it is important to select the List abstraction. ##2) I would convey the user with documentation. Like java does here. But despite documentation, I feel listInterface.h is a nightmare for user. – overexchange Jan 7 '17 at 8:25
  • I used the term 'end-user' to refer to the person who uses the final application, not the person writing that application. If that application is an e-mail client, then the end-user could be your mother wanting to read her mail. Do you want to bother them with the choice between a linked-list or array implementation? – Bart van Ingen Schenau Jan 7 '17 at 8:32
  • @BartvanIngenSchenau You are right!! But any one implementation(array or linkedlist) has to be picked at run time. What is the approach? – overexchange Jan 7 '17 at 8:38
  • 2
    Why are conditional compilations a disadvantage, and what makes reinventing C++'s vtable wheel an advantage? – Blrfl Jan 7 '17 at 12:09

There are several ways to make listInterface.h easier to use. One of the easiest ways is to combine list.h and listInterface.h into one file and to move the declarations of the vXXX functions there as well.

As a second refactoring, you should remove the implementation selector ("ARRAY" or "LINKEDLIST" string) from all interface functions. If you want to have run-time selection of the implementation, then you should either have a single function to select the implementation to use for the whole program, or you should specify it only on the createList function as an explicit argument.
That way, users of the list abstraction can't accidentally create a linked list and then call the array implementation on it.
Having the argument explicitly, and not implicitly as argv[1], makes it clear that there is a choice here and gives the possibility to base the choice on something else than the first program argument.

  • How socket() calls makes you pick AF_INET family implementation by passing AF_INET as first argument to socket() api? Do you see the analogy? – overexchange Jan 7 '17 at 12:59
  • static const struct net_proto_family __rcu *net_families[NPROTO] __read_mostly;int sock_register(const struct net_proto_family *ops){..} If I see this code in socket.c, I think sock_register() gets called when af_inet/af_unix/any family .so file is loaded in memory. For example, (void)sock_register(&inet_family_ops); is being called from af_inet.c by overriding _init() runtime code. Have a look at it – overexchange Jan 7 '17 at 13:15
  • This code is the inspiration of writing List abstraction which is yet to reach in next design by overriding _init() in arrayImpl.so and linkedListImpl.so going further. Currently, my code has implementations(ListHandler) connected at link time unlike sock_register() that is called at load time of af_inet library(.so) – overexchange Jan 7 '17 at 13:18
  • 1
    @overexchange: I see the intended analogy with sockets. Do you also see that you only have to specify AF_INET once when creating a socket and not over and over again when using the socket? That would correspond to specifying the List implementation only when creating a new list. – Bart van Ingen Schenau Jan 7 '17 at 13:50

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.