Dev:Source/Data Structures/Double Linked List

Two Way Linked Dynamic List

Two Way Linked Dynamic List (later only "list") is special dynamic data structure. You can see it very often in Blender source code. This dynamic data structure allows to add/remove dynamicaly allocated data structures. These data structures have to have special pointers (prev, next).

/* dynamicaly allocated dat structures has to include next and prev pointers */
typedef struct Link
{ 
    struct Link *next,*prev;
} Link;

/* ListBase points at the first and last pointer in dynamic list */
typedef struct ListBase 
{ 
    void *first, *last;
} ListBase;

Every item has "next" and "prev" pointers (in this order) to make a two way dynamic list. "prev" points at the previous item in the list and "next" points to the next item in the list. The first item in the list has a NULL "prev" pointer and the last item in the list has a NULL "next" pointer.

• Visualisation of Two Way Linked Dynamic List data strucuture:
  

We can simply "go" through the whole list (traverse the list) and do some testing or other operations:

for (item = lb.first; item; item= item->next) {
    do_some_operation_with_item();
}

You can see this construction in source code very often.

List of Available Functions

We can use several functions, when we work with a list. You can find all of them in:

./source/blender/blenlib/intern/util.c

.h file with function prototypes:

./source/blender/blenlib/BLI_blenlib.h

List of functions:

void addlisttolist(ListBase *list1, ListBase *list2);
void BLI_insertlink(struct ListBase *listbase, void *vprevlink, void *vnewlink);
void * BLI_findlink(struct ListBase *listbase, int number);
void BLI_freelistN(struct ListBase *listbase);
void BLI_addtail(struct ListBase *listbase, void *vlink);
void BLI_remlink(struct ListBase *listbase, void *vlink);
void BLI_addhead(struct ListBase *listbase, void *vlink);
void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink);
void BLI_freelist(struct ListBase *listbase);
int BLI_countlist(struct ListBase *listbase);
void BLI_freelinkN(struct ListBase *listbase, void *vlink);

Adding Item

Simple example demonstrating adding new item to list:

typedef struct MyItem { 
    struct MyItem *prev, *next; /* some other struct elements */ 
    float vec[3];
} MyItem;

struct ListBase lb={0,0};

void my_function(void)
{ 
    item = (Item*)MEM_callocN(sizeof(Item), "Item");
     
    /* BLI_addtail will add item at the end of DynamicList */
    BLI_addtail(&lb, item);
}

We can add item at the begining of list using BLI_addhead(&lb, item).

Freeing of List

We can free list using two different functions.

BLI_freelist(ListBase *listbase) is used, when all items are allocated with malloc() function.

BLI_freelistN(ListBase *listbase) is used, when all items are allocated with MEM_mallocN() function. MEM_mallocN() function is part of GuardedMalloc library. If you allocate items with MEM_mallocN() function, but you free DynamicList only with BLI_freelist() function, then Blender will print lot of debug messages about memory leaks.

Writing List to .blend file

You will have to modify some function in:

./source/blender/blenloader/intern/writefile.c

and add construction like this:

static void write_myitems(WriteData *wd, ListBase *lb) 
{ 
    Item item;
    for(item= lb->first; item; item= item->next)
        writestruct(wd, DATA, "MyItem", 1, item);
}

Reading List from .blend file

Reading List is quite simple. You have to add one function at right place:

FileData *fd;
ListBase *lb;
link_list(fd, lb);