XOR連結リストによるメモリ圧縮

XOR連結リストの概要

XOR連結リストはポインタ一つで双方向の走査を実現する連結リストの為のアルゴリズムです。通常、双方向リストを実装する場合は前方向と後ろ方向へのポインタを２つ使用しますが、XOR連結リストでは隣接するノードのアドレスの XOR(排他的論理和) した値を格納することで１つのマジックポインタに保存します。これよって単方向リストと同じメモリ消費にすることが出来ます。このアルゴリズムはメモリアドレスを整数として直接計算して代入できる安全ではないプログラミング言語でのみ実装できます。次の図のような構造でリストを構築します。

head -> a
tail -> d

      a                 b                 c                 d
 +---------+       +---------+       +---------+        +---------+
 | 0 xor b | <---> | a xor c | <---> | b xor d |  <---> | c xor 0 | 
 +---------+       +---------+       +---------+        +---------+

隣接するノードアドレスは対象要素のアドレスと、隣接する一方のアドレスを次の関数に入力することで、もう一方のアドレスを取得することによって前方向にも後ろ方向にも走査出来ます。

node *xor(node *a, node *b){
    return (node*) ((uintptr_t) a ^ (uintptr_t) b);
}

アルゴリズムの評価

64bitのアプリケーションで 100万個の要素をもつ場合でも 7 MB 程度の削減にしかならないのでギガバイト単位の大容量のメモリーが安価に入手できる現在においては廃れたアルゴリズムとも言えます。ポインタの為のメモリ消費量を削減するアルゴリズムとしては Unrolled linked list の方がメモリ参照の局所化によって性能向上が見込めるのでそちらを使うべきでしょう。

サンプルコード

以下は実際に動作するXOR連結リストのサンプルコードです。

$ clang test.c -c test
$ ./test

test.c のソース

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct node {
    int item;
    struct node * magic_ptr;
} node;

node *head, *tail;

node *xor(node *a, node *b){
    return (node*) ((uintptr_t) a ^ (uintptr_t) b);
}

void insert(int item, bool at_tail){
    node *ptr = (node*) malloc(sizeof(node));
    ptr->item = item;

    if (NULL == head) {
        ptr-> magic_ptr = NULL;
        head = tail = ptr;
    } else if (at_tail) {
        ptr->magic_ptr = xor(tail, NULL);
        tail->magic_ptr = xor(ptr, xor(tail->magic_ptr, NULL));
        tail = ptr;
    } else {
        ptr->magic_ptr = xor(NULL, head);
        head->magic_ptr = xor(ptr, xor(NULL, head->magic_ptr));
        head = ptr;
    }
}

int delete(bool from_tail){
    if (NULL == head) {
        exit(1);
    } else if (from_tail) {
        node *ptr = tail;
        int item = ptr->item;
        node *prev = xor(ptr->magic_ptr, NULL);
        if (NULL == prev) head = NULL;
        else prev->magic_ptr = xor(ptr, xor(prev->magic_ptr, NULL));
        tail = prev;
        free(ptr);
        ptr = NULL;
        return item;
    } else {
        node *ptr = head;
        int item = ptr->item;
        node *next = xor(NULL, ptr->magic_ptr);
        if (NULL == next) tail = NULL;
        else next->magic_ptr = xor(ptr, xor(NULL, next->magic_ptr));
        head = next;
        free(ptr);
        ptr = NULL;
        return item;
    }
}

void list(bool fromHead ){
    node *curr = fromHead?head:tail;
    node *prev = NULL, *next;

    while (NULL != curr) {
        printf("%d ", curr->item);
        next = xor(prev, curr->magic_ptr);
        prev = curr;
        curr = next;
    }
    printf("\n");
}

int main(int argc, char *argv[]){
    int i;
    for (i = 0; i < 10; i++) {
        insert(i, i < 5);
    }
    list(true); // 9 8 7 6 5 0 1 2 3 4
    list(false);// 4 3 2 1 0 5 6 7 8 9
}