Yamyam: 1版をインポートしました

2018-06-28T17:45:30Z

1版をインポートしました

wiki>Jby601: /* Two Way Linked Dynamic List */ minor grammar tweaks

2012-01-08T09:02:24Z

‎Two Way Linked Dynamic List: minor grammar tweaks

新規ページ

==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).

<source lang="cpp">

/* 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;

</source>

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: <br />
[[File:Dev-two_way_dynamic_list.png|DynamicList]]

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

<source lang="cpp">
for (item = lb.first; item; item= item->next) {
do_some_operation_with_item();
}
</source>

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 lang="cpp">
./source/blender/blenlib/intern/util.c
</source>

.h file with function prototypes:

<source lang="cpp">
./source/blender/blenlib/BLI_blenlib.h
</source>

List of functions:

<source lang="cpp">
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);
</source>

==== Adding Item ====

Simple example demonstrating adding new item to list:

<source lang="cpp">

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);
}
</source>

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 [[Dev:Source/Data Structures/Dynamic List|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 lang="cpp">
./source/blender/blenloader/intern/writefile.c
</source>

and add construction like this:

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

=== Reading List from .blend file ===

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

<source lang="cpp">
FileData *fd;
ListBase *lb;
link_list(fd, lb);
</source>

[[Category:Script]]

← 古い版	2018年6月28日 (木) 17:45時点における版
(相違点なし)

Dev:Source/Data Structures/Double Linked List - 版の履歴

Yamyam: 1版 をインポートしました

wiki>Jby601: /* Two Way Linked Dynamic List */ minor grammar tweaks

Yamyam: 1版をインポートしました