Dev:Source/Data Structures/BLI linklist Tutorial

Using BLI_linklist

BLI_linklist is a basic implementation of a singly linked list. This BLI was originally coded by Daniel Dunbar (zr).

Initialization, Addition and Destruction

 #include "BLI_linklist.h"

We need to include this header to use the linked list

 LinkNode *linklist = NULL;

This is our empty list. It is ready to be used.

 void BLI_linklist_prepend(struct [[BlenderDev/LinkNode|LinkNode]] ''''''listp, void *ptr);

This is the function to add an entry to the begining of the list. The linked list can hold any type of pointer as it's value. So if we were making a list of EditEdge pointers, and we had one called eed to add to the list, we would do it like this...

 BLI_linklist_prepend(linklist,eed);

 void BLI_linklist_prepend_arena(struct [[BlenderDev/LinkNode|LinkNode]] ''''''listp, void '''ptr, struct [[BlenderDev/MemArena|MemArena]] '''ma);

This function is for adding items to the link list using memory from a memarena rather that allocation memory each time you need to add 1 item. It reduces the number of calls to the system for more dynamic memory. Its use is not covered on this page at the moment.

 void BLI_linklist_free(struct [[BlenderDev/LinkNode|LinkNode]] *list, [[BlenderDev/LinkNodeFreeFP|LinkNodeFreeFP]] freefunc);

When we are done with our list, we will need to call this function. The first parameter is obviously the list we would like to get rid of. If we did not allocate any dynamic memory for the list entries, we can pass NULL as the second parameter

like this...

 BLI_linklist_free(linklist,NULL);

This will clean up our linked list. But if you need to do something to each entry before destroying the list, you can use the the second parameter. This is a pointer to a function that will be called for each node in the linked list, passing the value in the the linked list as a parameter. So if you needed to call MEM_freeN() on each member of the linklist you would do this

 BLI_linklist_free(linklist, MEM_freeN);

Utility Functions

 int BLI_linklist_length(LinkNode *list)

This one is pretty self explanatory, call it with the linked list as the parameter and get and int with the number of entries in the list.

 void BLI_linklist_reverse   (struct [[BlenderDev/LinkNode|LinkNode]] ''''''listp);

Again, another simple one, call this function with the linked list as the parameter and its contents will be reversed.

 void BLI_linklist_apply(LinkNode *list, [[BlenderDev/LinkNodeApplyFP|LinkNodeApplyFP]] applyfunc)

This is a nice one if you have a funtion that you would like to apply to each entry, much like the 2nd parameter in BLI_linklist_free. So if you had a function print(list_entry_type) that you wanted to call on each entry in the list, it would be this simple

 BLI_linklist_apply(linklist, print);

A Small Editmesh Example

#include "BLI_linklist.h"
LinkNode *linklist = NULL;

void foo(){ 
     EditMesh *em = G.editMesh;
     EditEdge *eed; 
     LinkNode '''linklist = NULL, '''iter;
     
     // Put all selected edges in a linked list 
     for(eed=em->edges.first;eed;eed = eed->next){ 
          if(eed->f & SELECT){   BLI_linklist_prepend(linklist,eed);
          }
     }
     // reverse the list for giggles
     BLI_linklist_reverse(linklist);
     // Now we can go through our linklist of edges in the same way 
     for(iter = linklist;iter;iter = iter->next){ 
          eed = iter->link; // Now eed is equal to the eed we put in the list 
     }
     BLI_linklist_free(linklist,NULL);
}