Dev:Source/Blender/Architecture/Dynamic List With Access Array
From BlenderWiki
Contents |
[edit] Two Way Dynamic List With Access Array
Dynamic list with access array is extension of 'classical' DynamicList (widely used in Blender). It includes dynamic allocated access array. You can access every item in dynamic list with some index then.
[edit] Negations
- You have to do realloc of access array, when you are adding item with index higher then array size. You have to do realloc only of small access array as well you can minimalize realloc.
- You can't use unitialized dynamic list with access array.
[edit] Benefits
- You can access every item in Dynamic List with access array using some index or ID. In classical DynamicList you have to go through DynamicList and test each item or increment some assistant variable.
- Visualisation of dynamic list with access array data strucuture:
- dynamic list with access array has benefits of array (you can access each item very fast using some index or ID) and dynamic list (you can easily add/remove items, you can easily access first and last item in list, it saves memory, etc.)
[edit] Strategy of realloc of access array
- We have to do realloc, when access array is too small and is filled or we want to add item with too high index.
- We can create access array twice biggere then before.
- We can add constant size (size of page: 4KB)
[edit] Strategy of Filling Access Array
- We don't care about indexes sometimes, because some other process generates indexes (it is main purpose for dynamic list with access array). Example of such process is verse server.
- When we are 'authors' of indexes, then we can try to have array filled with minimum of gaps. Such effort require finding gaps when we adding new items to the list.
- We can as well decrease size of access array, when the end of array is empty. This operation isn't absolutly neccessary, because we will propably need this space in the future again.
[edit] Declaration of Two Way Dynamic list with Access Array
/*========================================*/
/* Access array using realloc */
/*========================================*/
typedef struct DynamicArray{
unsigned int count;
unsigned int max_item_index;
unsigned int last_item_index;
void **items;
} DynamicArray;
/*========================================*/
/* Two way dynamic list with access array */
/*========================================*/
typedef struct DynamicList {
struct DynamicArray da;
struct ListBase lb;
} DynamicList;
[edit] List of Functions
DynamicList *BLI_dlist_from_listbase(ListBase *lb);
This function allows create DynamicList from ListBase. This function reuse all items of existing ListBase. DynamicList structure and access array are allocated. It could be useful, when you need temporary fast access to items of list.
ListBase *BLI_listbase_from_dlist(DynamicList *dlist, ListBase *lb);
Function converts DynamicList back to ListBase strucure.
void BLI_dlist_find_link(struct DynamicList *dlist, unsigned int index);
Function returns item dlist->da.items[index]. If such item doesn't exist, then function returns NULL pointer;
void BLI_dlist_free_item(DynamicList *dlist, unsigned int index);
Function removes and free item dlist->da.items[index].
void BLI_dlist_rem_item(DynamicList *dlist, unsigned int index);
Function only removes item dlist->da.items[index]. This function doesn't free any data.
void *BLI_dlist_add_item_index(DynamicList *dlist,void *item,unsigned int index);
Function adds item to DynamicList. Selection of non-used index in access array is your business.
void BLI_dlist_destroy(DynamicList *dlist);
Function frees all items in list as well access array. Such DynamicList can't be used anymore!
void BLI_dlist_init(DynamicList *dlist);
Function initializes DynamicList.
void BLI_dlist_reinit(DynamicList *dlist);
Function reinitialize DynamicList.
