Dev:Source/Blender/Architecture/Double Linked List

From BlenderWiki

[edit] 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 has 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 include "next" and "prev" pointer (in this order) in two way dynamic list. "prev" pointer points at previous item in the list and "next" pointer points at the next item in the list. First item in list has NULL "prev" pointer and last item in list has NULL "next" pointer.

• Visualisation of Two Way Linked Dynamic List data strucuture:
  

We can simply "go" throught the whole list and do some testing or some other operations:

item = lb.first;

while(item){ do_some_operation_with_item(); item = item->next;
}

You can see this construction in source code very often.

[edit] List of Available Functions

We can use several functions, when we work with 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);

[edit] 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_mallocN(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).

[edit] 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.

[edit] 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 = lb->first;
 while(item){ writestruct(wd, DATA, "MyItem", 1, item); item = item->next; }
}

[edit] 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);

Jiří Hnídek 05 Jul 2005

---

Nice tut. Couple of weeks back, I tried to understand blender's list architecture and created a demo program. Check it here.

Satish Goda 24 Jul 2005

---