XOR linked list

Navegando por aí, acabei caindo na página da Wikipédia sobre XOR linked list (http://en.wikipedia.org/wiki/XOR_linked_list), eu já havia visto essa página, mas não tinha parado para analisar, nem mesmo implementar...

Alguém pode estar curioso pra ver a implementação em C, como não há um código exemplificando, mas seguindo os passos do que é dito no texto, uma implementação seria a seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
struct _xorll {
	void* value;
	struct _xorll* np;
};
typedef struct _xorll xorll;
 
typedef void (*xorll_callback)(const xorll*, const xorll*);
 
xorll* new_node(xorll* prev, xorll* cur, void* value) {
	xorll* next = (xorll*) malloc(sizeof(xorll));
 
	next->value = value;
	next->np = cur;
 
	if (cur) {
		cur->np = prev == cur ? cur : (xorll*)((uintptr_t)prev ^ (uintptr_t)next);
	}
	return next;
}
 
void traverse(xorll* start, xorll_callback callback) {
	xorll* save, *cur = start, *prev = start;
 
	while (cur) {
		callback(prev, cur);
 
		if (cur->np == cur) {
			break;
		}
		save = cur;
		cur = cur == prev ? cur->np : (xorll*)((uintptr_t)prev ^ (uintptr_t)cur->np);
		prev = save;
	}
}
 
void xorll_string_printer(const xorll* prev, const xorll* cur) {
	printf("- %s\n", (char*)cur->value);
	printf("(prev=%p cur=%p next=%p)\n", prev, cur, (xorll*)((uintptr_t)prev ^ (uintptr_t)cur->np));
}
 
void freellist(xorll* start) {
	xorll* save, *cur = start, *prev = start;
 
	while (cur) {
		if (cur->np == cur) {
			free(cur);
			break;
		}
		save = cur;
		cur = cur == prev ? cur->np : (xorll*)((uintptr_t)prev ^ (uintptr_t)cur->np);
		prev = save;
		free(save);
	}
}
 
int main(int argc, char** argv) {
	xorll* end, *head;
 
	end = head = new_node(NULL, NULL, "a");
	end = new_node(end->np, end, "b");
	end = new_node(end->np, end, "c");
	end = new_node(end->np, end, "d");
 
	traverse(head, xorll_string_printer);
	freellist(head);
 
	return 0;
}

Testando o código:

$ gcc -o xorll xorll.c 
$ ./xorll 
- a
(prev=0x88b3008 cur=0x88b3008 next=0x10)
- b
(prev=0x88b3008 cur=0x88b3018 next=0x88b3028)
- c
(prev=0x88b3018 cur=0x88b3028 next=0x88b3038)
- d
(prev=0x88b3028 cur=0x88b3038 next=(nil))

I was curious if you ever

I was curious if you ever thought of changing the structure of your website?
Its very well written; I love what youve got to say.

But maybe you could a little more in the way
of content so people could connect with it better.
Youve got an awful lot of text for only having 1 or two pictures.
Maybe you could space it out better?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options