blog

Top secret science experience with triple ref pointers

I recently watched a very interesting video from Computerphile on YouTube about triple ref pointers, and I decided to play a little bit with them and doing something practical. Putting it in simple terms, triple ref pointers are pointers to pointers - I had no idea they actually had a name for this. Their usage is very situational (although you could argue that they are very similar to 2d arrays - arrays in C are close to pointers, but not really pointers), but they can be very useful, although a bit hard to master. If people already get confused by pointers, pointers to pointers are much worst, and I think most people will agree that more than two "layers" of pointers should be avoided (or good luck understanding what `void **** something` does!). That video I linked from Computerphile is really great at explaining one situation when they are useful, but they did not show any code - I will do this now! First, I made a very simple linked list in C - you don't really need to see the full code, but I will show it in the code block below. The program below creates a list of integers, append the numbers 2, 4, 6, 8, 10, 12, 14, 16 and 18 in the list, and then insert the numbers 1, 5, and 17 in their respective places. Here it is: ```c #include #include // Describes a "node" struct node { int data; struct node *next; }; // Describes the linked list struct list { struct node *head; }; // This function creates a node: stores the integer in the node // and sets the "next" node as NULL struct node *makeNode(int d) { struct node *n = malloc(sizeof(struct node)); n->data = d; n->next = NULL; return n; } // Deletes a list void delete(struct list *l) { struct node *c = l->head; struct node *n; while (c) { n = c->next; free(c); c = n; } } // Inserts a node in a particular position. If you pass NULL as the // position, the node is appended at the end of the list void insert(struct list *l, struct node *new, struct node *position) { struct node *p; if (position == l->head) { new->next = l->head; l->head = new; } else { p = l->head; while (p->next != position) p = p->next; new->next = p->next; p->next = new; } } // Prints the list void print(struct list *l) { struct node *c = l->head; for (; c != NULL; c = c->next) printf("-> %d\n", c->data); } int main() { int i; struct node *n; struct list list = { NULL }; struct node *node2, *node6, *node18; // Here I am creating the nodes 2 to 18 (incremented by 2). // The IF statements below are just for saving the nodes 2, // 6, and 18 - I will insert nodes before them later on for (i = 2; i <= 18; i += 2) { n = makeNode(i); if (i == 2) node2 = n; if (i == 6) node6 = n; if (i == 18) node18 = n; insert(&list, n, NULL); } // Inserting "1" before the node "2" n = makeNode(1); insert(&list, n, node2); // Inserting "5" before the node "6" n = makeNode(5); insert(&list, n, node6); // Inserting "17" before the node "18" n = makeNode(17); insert(&list, n, node18); // Prints and frees the list print(&list); delete(&list); return 0; } ``` This is a very common singly linked list: we have an object that points to the beginning of the list, and we can insert elements in it. What I want to focus on, however, is the `insert` function: ```c void insert(struct list *l, struct node *new, struct node *position) { struct node *p; // The list is empty - we can not reference any node from it if (position == l->head) { new->next = l->head; l->head = new; } else { // The list is not empty - we start iterating from the first node, and // when we find "position", we insert the new node before it p = l->head; while (p->next != position) p = p->next; new->next = p->next; p->next = new; } } ``` I don't know about you, but this bothers me a little bit: every time we insert something, we will have to go through this `if` statement, and it is something that will probably not execute very often (or more than once, if you don't ever empty your list). So, how can we solve this using triple ref pointers? First, let's understand the problem with the previous algorithm: for both situations we are updating a pointer somewhere so it points to our new object, and we update the "next" from the new node with the previous value of that pointer. The problem is that in the first scenario, we are dealing with a `struct list`, and in the second scenario, we are dealing with a `struct node`, and this is why we are branching the logic there; if we could eliminate this obstacle, we would not need the if statement. So, why triple ref pointers would help? They help this case by eliminating the need of accessing the `struct list` or the `struct node` to change its pointer: instead, we will reference their pointers directly, without having to go through the struct. Take a look: ```c void insert(struct list *l, struct node *new, struct node *position) { // This points to a pointer (which points to a node). The first one // is the head of the list, which is where we start struct node **p = &(l->head); // Is the triple ref pointer referencing a pointer to the position we // want to insert? If not, we reference the next pointer while (*p != position) p = &(*p)->next; // When we reach this point, the triple ref will be pointing to the // pointer that references the "position" node - we modify the // new node to have the same reference, and change the triple ref // pointer to point to the new node new->next = *p; *p = new; } ``` And there we go, the `if` statement is no more!