Redis Source Code - DS and Algos - adlist

November 04, 2017 by Abhirath Mahipal

ccode-reading

If you are not aware of the main article, please read it first - Index of Deep Dive into the Source Code of Redis.

Please keep the source code of Redis handy. Also have search commands for your respective text editors handy. You might have to perform quite a few searches :)

Meta Info

  • Difficulty - Very Easy
  • Should be Familiar with -
    • Doubly Linked Lists
    • Pointers in C (specially void*)

adlist.c & .h

This file is quite easy to understand. Perhaps you could try it out yourself even if you consider yourself a noob.

  • It’s a doubly linked list which allows you to store anything. It uses void* in the value field to point to anything. Structures used - listNode, listIter and list.
  • The node struct is a single unit of a list. It has a pointer to next, prev and a void* pointer so that it can store anything.
  • The listIter struct is used to create a neat iterator (cleaner that what you normally would do in C but not as clean as the ones in languages like Python or JavaScript). It’s handy to access the next element, duplicate the list etc. Directions are defined as 0 & 1. 0 goes forward from the head to the tail and vice versa. I’ll explain a bit more about it below.
  • The list struct has three function pointers (free, dup and match). I’ll explain their uses shortly.
  • Macros are used to access the elements inside structs. For instance it’s easier to get the length using a function rather than using a pointer.
/*
 * Remember macros are substituted
 * before compilation. So writing a function is actually
 * less efficient (forget over optimisation for a while) than a macro
 * And why not make use of the elegant features that C has to offer?
 */
#define listLength(l) ((l)->len)

// Cleaner as people prefer using
// functions or member variables rather than pointers
listLength(l) // cleaner than (l)->len
  • free, match & dup
    If you head over to the code you will notice that the node structure’s value parameter is a void *pointer. It means it can point to any value under the sun. You could point it to a struct that represents a client who just sent a request. Say you’re done and want to free the entire doubly linked list. If it were a simple int, just freeing every node in the doubly linked list would do. Remember the node itself is a dynamically allocated object and you have to free it. The value parameter might also point to another dynamically allocated object. The client struct might have arrays for IP, the actual request and so on which need to be freed.

Say now you decide that your doubly linked list should hold dog kennels. It probably has an additional pointer to a dog struct which also should be freed. The freeing mechanism therefore differs for each struct. To generalise the library so that it accommodate any use case you can pass in your custom function to free. It’ll be called for every node when you free the list.

The same logic goes for match and duplicate. ints and chars can be directly compared but what about pointers? What if you want to compare two identical book names but different pointers point to them. A simple == check will return false as the pointers are not equivalent. You would have to follow the pointer and compare the entire string. So you can pass in a custom function that will be called when you have to compare values in the doubly linked list.

I’ll just skip over the very obvious functions. The explanation given above should be sufficient to understand them.

Some things worth noting. Might be useful in case you decide to write a doubly linked list or design an API ;)

//After is an additional parameter that specifies if the node is to be
// after or before the position of *old_node
listInsertNode(list* list, listNode *old_node, void *value, int after);

Nothing fancy but it’s a simple example of using the same function to do many things by modifying the flags you pass in.

// Returns a pointer to the head or tail
// You don't have to use list->next or list->prev to access elements
// one by one. You can pass in an itertor and keep calling next to
// access all the elements of the list. Imagine the ease.
listIter *listGetIterator(list *list, int direction);
listIter *listNext(listIter *iter);

// Say I want to empty a list.
// Without the abstraction above I'd have to

// for forward iteration
for (listNode *temp = list->head; temp != NULL; temp = temp->next) {
    // some operation to perform
}
// for backward iteration
for (listNode *temp = list->tail; temp != NULL; temp = temp->prev) {
    // some operation to perform
    // Example duplicating or emptying a list
}

// With the abstraction above
// 0 is used to set the direction
// either head to tail or tail to head
listIter *studentsIter = listGetIterator(studentList, 0);
while ((node = listNext(studenIter)) != NULL) {
    // some operation
}

If you are not able to appreciate the improvement, let me jump in.

  • Read the two for loops in the code snippet above. Look the number of times I have to deal with the pointer. I also have to increment it. Say I perform such operations 20 times, I’d be writing this for loop 20 times. I could accidentally interchange head and tail while copying and pasting stuff.

  • The for loop is my style of iterating over a doubly linked list. You might prefer a do-while loop for the same. Such small differences can crop up and clutter the mind of the person reading the program. So anyone who wants to iterate over the list should use the function rather than their own style.

  • It thus is common practice to create functions for things even if they are trivial or don’t reduce the number of lines.

  • Another thing to notice. By giving it a name it becomes clearer as to what’s being done. To best elaborate imagine a complex single line statement (eg regex matching after string concatenation and slicing). Wouldn’t it be better to just make a function rather than have the programmer try understanding the various parts of that single line.

// Provides an option to get element at a certain position like how
// you'd do in a normal array. Also supports negative indices found
// in languages like Python. Nothing fancy in this function but I like
// the way he handles negative indices.
// -1 returns the last element, -2 the second last and so on
listNode *listIndex(list *list, long index) {
    listNode *n;

    if (index < 0) {
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
};