3 ms·
A word has been dropped from the title. The title at the site is: "A library of generic intrusive data structures and algorithms in ANSI C" (emphasis added). F
by tzs 9y ago
A word has been dropped from the title. The title at the site is: "A library of generic intrusive data structures and algorithms in ANSI C" (emphasis added).
For those, like me, who did not know what makes a data structure "intrusive", it means that the things needed for the data structure are stored together with the data.
For example, suppose our application needs to keep track of people. As far as we are concerned, a person looks like this:
struct person
{
int age;
const char * name;
};
If we want to make a linked list of people, and do so by adding a link field to our person struct, like this:
struct person
{
person * next_person;
int age;
const char * name;
};
and then make our list by linking our person structures through the next_person field, that would be an intrusive linked list.
A non-intrusive linked list would be to do something like this:
struct list_element
{
list_element * next;
void * data;
};
and then make our linked list by making a linked list of list_element structures, with their data pointers pointing to our person structures. If we were using C++, another way to do a non-intrusive linked list of people would be to use std::list<person>.
- DSMan195276 9y agoYes, that word is extremely important. With that, intrusive data-structures really are great in a lot of cases, it's unfortunate that most languages can't really handle them. That said, for languages with a GC they aren't really as useful from a programming standpoint (They may still be useful from a speed standpoint). Still, they allow you avoid tons of small allocations, as well as avoid the extra 'hop' necessary when you store the node information separate form the data. Another great part about intrusive data structures is that you can place an object on multiple structures without having to allocate any separate data for them. So to give an example, `std::list<person>` will actually create an 'intrusive' list - it will store the node information along with `person`. However, that `person` is completely tied to the list. If you want to take a `person` off of that list and place it into another one, you can't, you would have to either copy it into a node on the other list, or make the all the lists `std::list<person *>` and then store a pointer to the same person in both lists. With intrusive structures, you can instead use the same set of node information for every list, so you can detach a node from the first list, and then attach it to the second one without having to do any allocations. As a note, the Linux Kernel makes fairly extensive use of intrusive data-structures, which is an area they particularly shine in since you really want to avoid all those small allocations if you can.
- ozzmotik 9y agoi highly appreciate you explaining what was meant by intrusive as I was wondering what it meant and i was pretty sure I wasn't going to get good results asking Google considering how intrusive tends to map to things of a more illicit nature c:
- MaxBarraclough 9y agoBoost, too, provides a number of intrusive data-structures, if you're in C++ land. http://www.boost.org/doc/libs/1_66_0/doc/html/intrusive.html http://www.boost.org/doc/libs/1_66_0/doc/html/intrusive.html There's also intrusive_ptr, an intrusive reference-counted smart-pointer class template. http://www.boost.org/doc/libs/1_66_0/libs/smart_ptr/doc/html/smart_ptr.html#intrusive_ptr http://www.boost.org/doc/libs/1_66_0/libs/smart_ptr/doc/html...