Skip to content

Instantly share code, notes, and snippets.

@chenyukang
Created April 11, 2013 15:46
Show Gist options
  • Save chenyukang/5364515 to your computer and use it in GitHub Desktop.
Save chenyukang/5364515 to your computer and use it in GitHub Desktop.
xor link list
//http://en.wikipedia.org/wiki/XOR_linked_list
//use one pointer to construct double-link list
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
struct item{
void* nextprev;
void* value;
};
struct xorLinkList{
struct item* head;
struct item* tail;
};
struct xorLinkList* xorLinkList_new() {
struct xorLinkList* list = (struct xorLinkList*)malloc(sizeof(struct xorLinkList));
memset(list, 0, sizeof(struct xorLinkList));
return list;
}
int xorLinkList_add(struct xorLinkList* list, void* value) {
assert(list);
struct item* _new = (struct item*)malloc(sizeof(struct item));
if(_new == 0) return -1;
memset(_new, 0, sizeof(struct item));
_new->value = value;
if(list->head == 0) { //no elem
list->head = _new;
} else if(list->tail == 0) { //have one elem
list->tail = _new;
_new->nextprev = list->head;
list->head->nextprev = list->tail;
} else { //append to end
_new->nextprev = list->tail;
list->tail->nextprev = (void*)( (size_t)list->tail->nextprev ^ (size_t)_new);
list->tail = _new;
}
return 0;
}
/* remove a element from head of list */
void* xorLinkList_remove(struct xorLinkList* list) {
assert(list);
void* v = 0;
void* head = list->head;
if(list->head != 0) {
v = list->head->value;
}
if(list->tail == 0) {
list->head = 0;
}
else if(list->tail->nextprev == list->head &&
list->head->nextprev == list->tail) { //just two elem
list->head = list->tail;
list->tail = 0;
list->head->nextprev = 0;
} else {
list->head = list->head->nextprev;
list->head->nextprev = (void*)( (size_t)list->head->nextprev ^ (size_t)head);
}
free(head);
return v;
}
void xorLinkList_del(struct xorLinkList* list) {
struct item* p = list->head;
while(xorLinkList_remove(list))
;
free(list);
}
typedef void(*traverse_func) (const void*);
void* xorLinkList_traverse(struct xorLinkList* list, traverse_func func) {
assert(list);
struct item* p = list->head;
struct item* q = 0;
while(p != 0) {
func(p->value);
if(p == list->head) {
q = p;
p = p->nextprev;
} else if( p != list->tail) {
p = (struct item*)((size_t)q ^ (size_t)p->nextprev);
q = p;
} else {
break;
}
}
}
struct elem{
int v;
};
void elem_func(const void* p) {
struct elem* e = (struct elem*)p;
printf("elem value: %d\n", e->v);
}
int main() {
int k;
struct elem* p;
struct xorLinkList* list = xorLinkList_new();
for(k=1; k<100; k++) {
p = (struct elem*)malloc(sizeof(struct elem));
p->v = k;
xorLinkList_add(list, p);
}
xorLinkList_traverse(list, elem_func);
while((p = xorLinkList_remove(list)) != 0) {
printf("remove: %d\n", p->v);
free(p);
}
xorLinkList_del(list);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment