Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/linked_list.h.md

docs/Writerside/topics/linked_list.h.md

changeset 1537
f60a73d2ad01
parent 1424
563033aa998c
equal deleted inserted replaced
1536:b65c05e7be3c 1537:f60a73d2ad01
6 The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used 6 The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used
7 that are created by one of the following functions. 7 that are created by one of the following functions.
8 8
9 ```C 9 ```C
10 #include <cx/linked_list.h> 10 #include <cx/linked_list.h>
11
12 typedef struct cx_linked_list_s cx_linked_list;
11 13
12 CxList *cxLinkedListCreate(const CxAllocator *allocator, 14 CxList *cxLinkedListCreate(const CxAllocator *allocator,
13 cx_compare_func comparator, size_t elem_size); 15 cx_compare_func comparator, size_t elem_size);
14 16
15 CxList *cxLinkedListCreateSimple(size_t elem_size); 17 CxList *cxLinkedListCreateSimple(size_t elem_size);
16 ``` 18 ```
17 19
18 The remaining content of this page concentrates on the low-level functions. 20 If you are using high-level linked lists to implement your own list structure,
21 it might be necessary to store additional data in each node that does not belong to the elements.
22 For this purpose, there exists the following function.
23
24 ```C
25 void cx_linked_list_extra_data(cx_linked_list *list, size_t len);
26 ```
27
28 It instructs the linked list to allocate `len` bytes of extra data when allocating a node.
29 The location offset of the extra data is stored in the `loc_extra` field of the linked list.
30
31 > The [key/value list](kv_list.h.md) uses this technique to store the `CxHashKey` as extra data in each node.
19 32
20 ## Basic Structure 33 ## Basic Structure
21 34
22 All functions described on this page work with nodes that have the following structure. 35 This section and the remaining content of this page describe the low-level functions for linked lists.
36
37 Those work with nodes that have the following structure.
38
23 ```C 39 ```C
24 struct node { 40 struct node {
25 node *next; 41 node *next;
26 node *prev; // optional 42 node *prev; // optional
27 // ... the element data goes here ... 43 // ... the element data goes here ...
28 }; 44 };
29 ``` 45 ```
30 46
31 Each node must have at least one pointer that contains the address of the subsequent node. 47 Each node must have at least one pointer that contains the address of the subsequent node.
32 Optionally, for doubly-linked lists, there may be a second pointer that points to the predecessor. 48 Optionally, for doubly linked lists, there may be a second pointer that points to the predecessor.
33 49
34 The functions usually expect a `loc_prev` and a `loc_next` offset. 50 The functions usually expect a `loc_prev` and a `loc_next` offset.
35 In the example structure from above you can obtain them with `offsetof(struct node, next)` and `offsetof(struct node, prev)`. 51 In the example structure from above you can obtain them with `offsetof(struct node, next)` and `offsetof(struct node, prev)`.
36 In all functions, `loc_prev` is optional in the sense, that when you do not have a `prev` pointer, you can specify a negative value. 52 In all functions, `loc_prev` is optional in the sense, that when you do not have a `prev` pointer, you can specify a negative value.
37 When a function expects a `loc_advance` offset, you can freely choose if you want to pass the offset of the `next` or the `prev` pointer, 53 When a function expects a `loc_advance` offset, you can freely choose if you want to pass the offset of the `next` or the `prev` pointer,
41 If non-`NULL`, they point to the variables where the addresses of the first, or the last, node of a list are stored, respectively. 57 If non-`NULL`, they point to the variables where the addresses of the first, or the last, node of a list are stored, respectively.
42 When a list operation results in a new first (or last) node, the addresses are overwritten. 58 When a list operation results in a new first (or last) node, the addresses are overwritten.
43 In simple scenarios, you usually keep a pointer to the beginning of a list, and hence you would usually pass `NULL` to the `end` argument. 59 In simple scenarios, you usually keep a pointer to the beginning of a list, and hence you would usually pass `NULL` to the `end` argument.
44 If you are designing a stack-like linked-list, it may happen that you only want to store the last node of a list (the top of stack), 60 If you are designing a stack-like linked-list, it may happen that you only want to store the last node of a list (the top of stack),
45 hence passing `NULL` to the `begin` argument and the address of your top-of-stack pointer to the `end` argument. 61 hence passing `NULL` to the `begin` argument and the address of your top-of-stack pointer to the `end` argument.
46 Either way, most functions allow you a big deal of flexibility - please still read the documentation of each function carefully to learn which combinations are allowed. 62 Either way, most functions allow you a big deal of flexibility — please still read the documentation of each function carefully to learn which combinations are allowed.
47 63
48 When you are working with a singly-linked list, it is still sometimes necessary to access the predecessor of a node. 64 When you are working with a singly linked list, it is still sometimes necessary to access the predecessor of a node.
49 In the absence of a `prev` pointer, the only chance is to start at the beginning of the list and search for that node. 65 In the absence of a `prev` pointer, the only chance is to start at the beginning of the list and search for that node.
50 This is exactly what `cx_linked_list_prev()` does. 66 This is exactly what `cx_linked_list_prev()` does.
51 ```C 67 ```C
52 #include <cx/linked_list.h> 68 #include <cx/linked_list.h>
53 69

Mercurial Repository: ucx

mercurial