xor link list

gistfile1.c

//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;
}