Inlist, which is a sort of the Linked List, is an optimized linked list for the data structure and it's behavior performance. The key point of Inlist is, it embeds a user data in its own data structure, does not have a user data separately. Let's see an example quickly.
Firstly, let me describe a normal Linked List data structure. We can suppose that data structure would be provided with an API like a useful library.
It's just a common Linked List data structure. No problems even though no explanation. See next.
list_create() generates a list and the other one appends a new node in the list. I believe you already know Linked List so we won't look at the above code in detail. (Just in case, you can easily find a Linked List concept by googling.)
So far, it looks nice. We can provide a sort of free functions with regard to the above additionally but I'd like to skip them because they are actually at outside of the stake.
Then, we can suppose a user uses our functions in this scenario.
Seems very well. But for some people who are likely to ask me how to implement list_foreach(), I'm adding the function code here.
The code won't be the perfect however at least, we can imagine such that code we can define.
_prev_get_next() is an internal function which returns a next node, _get_user_data() is an internal function which returns user data from a node. Both of them actually are not important, we don't need to waste time by diving them to dig. So let's skip them.
So far, we've looked a normal Linked List and its peripheral functions usage. Here point we have to notice again is the next sequence that builds up a working Linked List.
1. Create a list(list_create()).
2. Create a user data(create_userdata())
3. After creating a node, store user data in that node(list_append_item()).
4. Append a new node in the list(list_append_item()).
By this time, if we see a figure of its structure, it must be looked like this.
Like above the figure, modified UserData to include ListNode data fields. Next, let's modify List and ListNode.
Now, it doesn't need to allocate ListNode but build Linked List via UserData.
No big changes, but just use void* type data(exactly for UserData) instead of the ListNode* to construct the list.
Lastly, let's take a look at the code which describes the iterator body of the list.
You might be noticed that it is simpler than previous one because it doesn't need to access a user data from a node anymore. But, of course, it has a con that user needs to declare LISTNODE field in the first line of the UserData structure. But actually it is not big deal. Other than that, we can still provide utility functions for user convenience.
So far, we've taken a look at the Inlist. It is a compact data structure across the nodes, also it's possible to access to user data faster than normal version. But it must be used when the data is designed to work along with the list. Actually, this Inlist concept was introduced in Enlightenment open-source project years ago. If you are interested in it more than this, you can visit here to look the whole functionalities and its implementation bodies.
Firstly, let me describe a normal Linked List data structure. We can suppose that data structure would be provided with an API like a useful library.
//A list node information. data field points actual user data.
struct ListNode {
ListNode *prev;
ListNode *next;
void *data;
};
//A data structure for accessing list nodes.
struct List {
ListNode *head;
ListNode *last;
};
It's just a common Linked List data structure. No problems even though no explanation. See next.
//Create a new list.
List* list_create() {
return (List*) calloc(1, sizeof(List));
};
//Append a new item(node) in a list.
bool list_append_item(List* list, void *data ) {
if (list == null) return false;
//Create a new node.
ListNode *node = (ListNode*) calloc(1, sizeof(ListNode));
if (node == null) return false;
node->data = data;
//In case of the first node.
if (list->last == null) {
list->head = list->last = node;
return true;
}
//Append a new node in the list.
ListNode *last = list->last;
last->next = node;
node->prev = last;
list->last = node;
return true;
}
list_create() generates a list and the other one appends a new node in the list. I believe you already know Linked List so we won't look at the above code in detail. (Just in case, you can easily find a Linked List concept by googling.)
So far, it looks nice. We can provide a sort of free functions with regard to the above additionally but I'd like to skip them because they are actually at outside of the stake.
Then, we can suppose a user uses our functions in this scenario.
//User data structure
struct UserData {
int idx;
int val;
};
void main() {
List *list = list_create();
//Set up a list.
//Create arbitrary 100 items. Skiping here, but create_userdata() creates a UserData data and returns it.
for (int idx = 0; idx < 100; ++idx) {
UserData *usrdat = create_userdata(idx, idx * 100);
list_append_item(list, usrdat);
}
//Verify that list is correct or not.
//It would be better if we provide a function, list_foreach(), to iterate a list...
ListNode *node = null;
UserData *usrdat = null;
list_foreach(list, node, usrdat, UserData) {
if (usrdat)
printf("%d %d\n", usrdat->idx, usrdat->val );
}
//Skip the free sequence..
}
Seems very well. But for some people who are likely to ask me how to implement list_foreach(), I'm adding the function code here.
#define list_foreach( list, node, usrdat, DATA_TYPE ) \
for (node = list->head, usrdat = (DATA_TYPE*) _get_usr_data(node); node; node = _prev_get_next(node), usrdat = (DATA_TYPE*) _get_usr_data(node))
The code won't be the perfect however at least, we can imagine such that code we can define.
_prev_get_next() is an internal function which returns a next node, _get_user_data() is an internal function which returns user data from a node. Both of them actually are not important, we don't need to waste time by diving them to dig. So let's skip them.
So far, we've looked a normal Linked List and its peripheral functions usage. Here point we have to notice again is the next sequence that builds up a working Linked List.
1. Create a list(list_create()).
2. Create a user data(create_userdata())
3. After creating a node, store user data in that node(list_append_item()).
4. Append a new node in the list(list_append_item()).
By this time, if we see a figure of its structure, it must be looked like this.
The key point here is, on building the structure, it needs to allocate 2 pieces of fragmented data memory per one item. Plus, every loop, it requires referring pointers, node->data, to access user data.
Then, let's take a look at the difference with Inlist. Inlist reduces memory allocation count as well as pointer access count by merging Node and UsrData like the next figure.
Someone may think, it's a piece of cake. If user implements the list manually, they could have implemented it like the above. On the other hands, if you provide the list function to users or implement it internally as a re-usable function for yourself, you are possibly somewhat impressed.
Now, we understand the concept of the Inlist. Let's start to implement it quickly. I will modify the previous list code and here I will show you the just different parts of the code. Let's take a look at UsrData first.
#define LISTNODE ListNode node; //Define for user convenience.
//User data structure
struct UserData {
//Firstly, adds a field using that macro.
LISTNODE;
int idx;
int val;
};
Like above the figure, modified UserData to include ListNode data fields. Next, let's modify List and ListNode.
struct ListNode {
ListNode *prev;
ListNode *next;
void *data; //No more use.
};
struct List {
//Nothing changed.
ListNode *head;
ListNode *last;
};
Now, it doesn't need to allocate ListNode but build Linked List via UserData.
//Append a new item(node) in the list.
bool list_append_item(List* list, void *data) {
if (list == null || data == null) return false;
//Create a new node. Not necessary anymore.
ListNode *node = (ListNode*) calloc(1, sizeof(ListNode));
if( node == NULL ) return false;
node->data = data;
//Convert to ListNode.
//In fact, simply use typename to access list node from user data if it is C++...
ListNode* node = (ListNode*) data;
//In case of the first node.
if (list->last == null) {
list->head = list->last = data;
return true;
}
//Append a new node in the list.
ListNode *last = list->last;
last->next = node;
node->prev = last;
list->last = node;
return true;
}
No big changes, but just use void* type data(exactly for UserData) instead of the ListNode* to construct the list.
Lastly, let's take a look at the code which describes the iterator body of the list.
#define list_foreach(list, usrdat) \
for (usrdat = list->head, usrdat; usrdat = _prev_get_next(usrdat))
void main() {
//Create a list and set it up here...
UserData *usrdat = null;
list_foreach(list, usrdat) {
printf("%d %d\n", usrdat->idx, usrdat->val);
}
}
You might be noticed that it is simpler than previous one because it doesn't need to access a user data from a node anymore. But, of course, it has a con that user needs to declare LISTNODE field in the first line of the UserData structure. But actually it is not big deal. Other than that, we can still provide utility functions for user convenience.
So far, we've taken a look at the Inlist. It is a compact data structure across the nodes, also it's possible to access to user data faster than normal version. But it must be used when the data is designed to work along with the list. Actually, this Inlist concept was introduced in Enlightenment open-source project years ago. If you are interested in it more than this, you can visit here to look the whole functionalities and its implementation bodies.