Skip to content

Instantly share code, notes, and snippets.

@lnsp
Created January 13, 2019 23:56
Show Gist options
  • Save lnsp/cc0354dc62a50a098efd06a484618395 to your computer and use it in GitHub Desktop.
Save lnsp/cc0354dc62a50a098efd06a484618395 to your computer and use it in GitHub Desktop.
Implementation of a XOR-Doubly linked list
/*
* Basic XORLIST-Implementation.
* (c) 2019 Lennart Espe. All rights reserved.
*/
#include <stdlib.h>
#include <stdio.h>
struct item {
uintptr_t both;
int value;
};
struct list {
struct item *head, *end;
size_t size;
};
struct list *list_new() {
return calloc(1, sizeof(struct list));
}
void list_add(struct list *list, int value) {
struct item *item = malloc(sizeof(struct item));
item->value = value;
item->both = (uintptr_t) list->end;
if (!list->head) list->head = item;
if (list->end) list->end->both ^= (uintptr_t) item;
list->end = item;
list->size++;
};
int list_get(struct list *list, size_t index) {
uintptr_t active = (uintptr_t) list->head,
prev = (uintptr_t) NULL,
tmp = (uintptr_t) NULL;
for (size_t i = 0; i < index; i++) {
tmp = active;
active = ((struct item *) active)->both ^ prev;
prev = tmp;
}
return ((struct item *) active)->value;
}
int main() {
struct list *list = list_new();
list_add(list, 12);
list_add(list, 15);
list_add(list, 30);
for (size_t i = 0; i < list->size; i++) {
printf("%d\n", list_get(list, i));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment