1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Can you edit the question to get rid of the source code and replace it with ideas and concise pseudo code? Not everyone here reads C code -- and that's a lot of code you're asking us to look at. See here and here for related meta discussions. $\endgroup$ – D.W. Mar 30 '17 at 5:20
  • 1
    $\begingroup$ You seem to be asking if your implementation of arrays in C is new. That's a question about how arrays are programmed in C, not a question about computer science in general. If your question is actually about the data structure and is independent of its implementation in C, then please rewrite your question so it doesn't require understanding C. $\endgroup$ – David Richerby Mar 30 '17 at 7:47
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.