notebook/notes/data-structures/intrusive.md

title	TARGET DECK	FILE TAGS	tags
Intrusive Containers	Obsidian::STEM	data_structure::intrusive	data_structure

Overview

An intrusive container is a data structure used to hold a collection of objects in which membership bookkeeping is stored in the objects themselves rather than a separate structure. For example, consider the following struct:

struct Point {
  float x, y;
}

A non-intrusive implementation of a linked-lists would look as follows:

struct ListNode {
  struct Point val;
  struct ListNode *next, *prev;
}

An intrusive implementation would instead modify Point like so:

struct Point {
  float x, y;
  struct Point *next, *prev;
}

%%ANKI Basic What is an intrusive container? Back: A collection of objects in which membership bookkeeping is stored in the objects themselves. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic What is the opposite of an "intrusive container"? Back: A non-intrusive container. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Given the following struct, implement an intrusive doubly linked list.

struct Point {
  float x, y;
}

Back:

struct Point {
  float x, y;
  struct Point *next, *prev;
}

Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: c17 data_structure::linked_list

END%%

%%ANKI Basic Is the following considered an intrusive container or non-intrusive container?

struct Point {
  float x, y;
  struct Point *next, *prev;
}

Back: Intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: c17 data_structure::linked_list

END%%

%%ANKI Basic Is the following considered an intrusive container or non-intrusive container?

struct ListNode {
  struct Point val;
  struct ListNode *next, *prev;
}

Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Given the following struct, implement a non-intrusive doubly linked list.

struct Point {
  float x, y;
}

Back:

struct ListNode {
  struct Point val;
  struct ListNode *next, *prev;
}

Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: c17 data_structure::linked_list

END%%

%%ANKI Basic Given the following struct, how many linked lists can a Point exist in?

struct Point {
  float x, y;
  struct Point *next, *prev;
}

Back: Zero or one. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: c17 data_structure::linked_list

END%%

%%ANKI Basic Given the following struct, how many linked lists can a Point exist in?

struct ListNode {
  struct Point *val;
  struct ListNode *next, *prev;
}

Back: Zero or more. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: c17 data_structure::linked_list

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers allow a struct to exist in an arbitrary number of linked lists? Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction. Tags: data_structure::linked_list

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers perform more allocations? Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers perform more de-allocations? Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers has better spatial locality? Back: Intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers avoid modifying object definitions? Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers allow implicitly finding all containers an object is contained in? Back: Intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers cannot be used for opaque types? Back: Intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

%%ANKI Basic Which of intrusive or non-intrusive containers requires searching in each container for the same reference? Back: Non-intrusive. Reference: Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.

END%%

Bibliography

• Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.