Coding a simple look-up-table in C – without Linked lists and a binary search

Linked-lists is one of the most commonly used data-structures to store linear dynamic items such as while commonly coding in C/C++ which is also the case in the Linux Kernel Programming. However linked-lists have their own drawbacks as they dynamically (i.e runtime) tend to shrink and grow in size thus the memory allocation and deallocation steps which need to be done. If we fail to do the same properly, it can lead to a nasty runtime crash. This is somewhat tolerable in user-space code which is quite easy to debug and fix, but it is extremely lethal in kernel programming, as it can bring down an entire system the moment any kernel crash happens. So at times these days we don’t need self do these as we may use any third-party library to manage the same. And in the case of kernel, depending upon the context chances are you may find one or multi-level multidimensional data-structure management APIs. What I really meant “multi-level” APIs is, it can be primitive list management data-structure APIs or one more level of wrapper APIs. For example sk_buff, net_device data-structures.

Having said, my most preferred choice when it comes to multidimensional data-structure is still plain simple fail-proof “arrays”. I use strictly arrays whenever I need a multidimensional data-structure. Say a packet queue, some items to store, instructions, jobs, so on. So what I do is a simple look-up-table without Linked lists. Since here the memory is statically allocated (not runtime), it is pretty safe. Of course you cannot resize while in operation. But it guarantees a crash proof rock solid code-base for any critical applications. Here is my detailed video episode on the same. Kindly feel free to reach me if you need any further help of any queries on this regard.

Download this episode my entire sample code which I hosted in my GitHub Repo. And here is the source code for a quick reference.

/* lookuptable.c - coding a look-up-table in C
 * The Linux Channel
 * Author: Kiran Kankipati
 * Updated: 16-mar-2017
 */
 
#include <stdio.h>
#include <stdbool.h>

typedef struct __mytable_
{	int value;
	char name[50];
	bool enable;
} mytable_t;

#define MAX_ENTRIES 100
mytable_t mytable_array[MAX_ENTRIES];

bool init_mytable()
{	int i=0;
	for(i=0;i<MAX_ENTRIES;i++) { mytable_array[i].enable=false; }
}

void print_mytable()
{	int i=0;
	printf("mytable_array[] contents\n");
	for(i=0;i<MAX_ENTRIES;i++) { if(mytable_array[i].enable==true) printf("[%d] - value: %d\n", i, mytable_array[i].value); }
	printf("------------------------\n\n");
}

void add_item_mytable(int value)
{	int i=0;
	//check for duplicate ?
	for(i=0;i<MAX_ENTRIES;i++) { if(mytable_array[i].enable==true) { if(mytable_array[i].value==value) { return; } } }
	
	//add item
	for(i=0;i<MAX_ENTRIES;i++) { if(mytable_array[i].enable==false) { mytable_array[i].value=value; mytable_array[i].enable=true; return; } }
}

void del_item_mytable(int value)
{	int i=0;
	//check for match ?
	for(i=0;i<MAX_ENTRIES;i++) { if(mytable_array[i].enable==true) { if(mytable_array[i].value==value) { mytable_array[i].enable=false; return; } } }
}

int find_item_mytable(int value)
{	int i=0;
	//check for match ?
	for(i=0;i<MAX_ENTRIES;i++) { if(mytable_array[i].enable==true) { if(mytable_array[i].value==value) { return i; } } }
}

void main()
{
	init_mytable(); print_mytable();
	
	add_item_mytable(5); print_mytable();
	add_item_mytable(3); print_mytable();
	add_item_mytable(1); print_mytable();
	add_item_mytable(2); print_mytable();
	
	del_item_mytable(3); print_mytable();
	
	printf("value: %d is in position [%d]\n", 1, find_item_mytable(1));
}

I also conduct sessions/classes on Systems and Network Software Programming, Linux Kernel Programming and Architecture. If you are interested, click HERE for more details.

If you have any queries or anything to discuss further kindly feel free to contact me.