Does my "hollow list" structure exist already?

Question

I came up with an implementation in c for arrays which can be extremely large yet only use an amount of memory proportional to how much data you have written to it. What I want to know is if there is a name for this kind of list or structure. Here is my code in C for the structure and example use:

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

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

int main(){
    int a = 221;
    int b = 222;
    int c = 9;
    int d = 89;

    hollow_list h;
    h = hollow_list_create(30);

    hollow_list_write(&h, 221999999, &a);
    hollow_list_write(&h, 9999, &b);
    hollow_list_write(&h, 22999999, &c);
    hollow_list_write(&h, 1, &d);

    printf("%d\n", *((int *) hollow_list_read(&h, 221999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 9999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 1)));
    printf("\n");
    printf("\n");
    printf("\n");
    printf("%d\n", a);
    printf("%d\n", b);
    printf("%d\n", c);
    printf("%d\n", d);

    c = 56;
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
}

These lists seem to be really useful alternatives to linked lists, and fast too: the worst case scenario for a read or write to a list is O(log n) for a list of n elements. I'd be surprised if this kind of structure didn't already exist, but I would simply like to know what it is called so I could refer to it by it's proper name haha.

Answer 1

This is a sparse array data structure, but I haven't seen this exact data structure before. It looks like your code builds a balanced binary tree, but with a particularly clever representation in memory.

One difference between other balanced binary trees is that the running time of your approach is $O(\lg m)$ where $m$ is the largest index written, whereas other balanced binary tree data structures (e.g., red-black trees) have a $O(\lg n)$ running time where $n$ is the number of indices written to. Since $m \ge n$, in principle your approach might be slower if $n$ is small (few elements have been written) but the indices are large. However in practice I don't expect this to make much difference, ordinarily.

Answer 2

I think that what you have created is a bitwise trie:

Bitwise tries are much the same as a normal character-based trie except that individual bits are used to traverse what effectively becomes a form of binary tree. Generally, implementations use a special CPU instruction to very quickly find the first set bit in a fixed length key (e.g., GCC's __builtin_clz() intrinsic)

Emphasis mine. Your code seems to be doing exactly that:

unsigned int bit_checker;
bit_checker = 1<<(l->size - 1);
int i;
for(i = 0; i < l->size; i++){
    if(bit_checker & index){
        if(l->written[i] == true){
            return hollow_list_read(l->children + i, bit_checker ^ index);
        } else {
            return (void *) 0;
        }
    }
    bit_checker >>= 1;
}