examples

Toy examples in single C files.
git clone git://henryandlizzy.uk/examples
Log | Files | Refs

xor-linked-list.c (1793B)

      1 #include <assert.h>
      2 #include <stdint.h>
      3 #include <stdio.h>
      4 
      5 struct node
      6 {
      7 	uintptr_t delta;
      8 	int data;
      9 };
     10 
     11 struct node* next_node(struct node* prev, struct node* current)
     12 {
     13 	assert(current);
     14 	return (struct node*)((uintptr_t)prev ^ current->delta);
     15 }
     16 
     17 
     18 void insert(struct node* p, struct node* c, struct node* n)
     19 {
     20 	if (c)
     21 	{
     22 		assert(!c->delta);
     23 		c->delta ^= (uintptr_t)p ^ (uintptr_t)n;
     24 
     25 	}
     26 	if (p)
     27 	{
     28 		p->delta ^= (uintptr_t)c ^ (uintptr_t)n;
     29 		assert(p->delta);
     30 	}
     31 	if (n)
     32 	{
     33 		n->delta ^= (uintptr_t)c ^ (uintptr_t)p;
     34 		assert(n->delta);
     35 	}
     36 }
     37 
     38 void append(struct node* p, struct node* c, struct node* n)
     39 {
     40 	assert(n);
     41 	assert(!n->delta);
     42 	assert(!next_node(p, c));
     43 	c->delta ^= (uintptr_t)n;
     44 	n->delta = (uintptr_t)c;
     45 }
     46 
     47 void extract(struct node* prev, struct node* get)
     48 {
     49 	assert(prev);
     50 	assert(get);
     51 
     52 	struct node* next = next_node(prev, get);
     53 	if (prev)
     54 		prev->delta ^= (uintptr_t)get ^ (uintptr_t)next;
     55 	if (next)
     56 		next->delta ^= (uintptr_t)get ^ (uintptr_t)prev;
     57 	get->delta = 0;
     58 }
     59 
     60 void advance(struct node** prev, struct node** current)
     61 {
     62 	struct node* p = *current;
     63 	*current = next_node(*prev, *current);
     64 	*prev = p;
     65 }
     66 
     67 static struct node nodes[5];
     68 static struct node stray = {0, 11};
     69 
     70 int main()
     71 {
     72 	for (unsigned i = 0; i < 5; ++i)
     73 		nodes[i].data = i;
     74 
     75 	append(NULL,    nodes+0, nodes+1);
     76 	append(nodes+0, nodes+1, nodes+3);
     77 	append(nodes+1, nodes+3, nodes+2);
     78 	append(nodes+3, nodes+2, nodes+4);
     79 	insert(nodes+2, &stray, nodes+4);
     80 	extract(nodes+1, nodes+3);
     81 
     82 	puts("Forward:");
     83 	for (struct node* current = nodes, *last = NULL; current; advance(&last, &current))
     84 		printf("  %p = %d\n", current, current->data);
     85 	puts("\nReverse:");
     86 	for (struct node* current = nodes+4, *last = NULL; current; advance(&last, &current))
     87 		printf("  %p = %d\n", current, current->data);
     88 }