chunklist.c

#include "chunklist.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

ChunkListNode *chunklist__new_chunk();
ChunkListNode *chunklist__init_chunk(ChunkList *, ChunkListNode *);
ChunkListNode *chunklist__get_chunk_for_index(ChunkList *, index_t);

ChunkList *chunklist_new(size_t values_per_node) {
  return chunklist_init(malloc(sizeof(ChunkList)), values_per_node);
}

ChunkList *chunklist_init(ChunkList *l, size_t values_per_node) {
  chunklist_del(l);
  l->head = chunklist__new_chunk();
  l->_values_per_node = values_per_node;
  return l;
}

void chunklist_del(ChunkList *l) {
  ChunkListNode *head, *next;
  head = l->head;
  while (head != NULL) {
    next = head->next;
    free(head->values);
    free(head);
    head = next;
  }
  free(l->head);
}

value_t chunklist_get(ChunkList *l, index_t index) {
  ChunkListNode *chunk = chunklist__get_chunk_for_index(l, index);
  return chunk->values[index % l->_values_per_node];
}

value_t chunklist_set(ChunkList *l, index_t index, value_t value) {
  ChunkListNode *chunk = chunklist__get_chunk_for_index(l, index);
  chunk->values[index % l->_values_per_node] = value;
  return value;
}

void chunklist_print(ChunkList *l) {
  ChunkListNode *n;
  index_t chunk_index = 0;
  n = l->head;

  printf("ChunkList[%lu] at %p", l->_values_per_node, l);
  if (n == NULL) {
    printf(" is empty.\n");
  } else {
    printf(":\n");

    while (n != NULL) {
      printf("  Node at %p (%lu-%lu) ", n, chunk_index * l->_values_per_node, (chunk_index + 1) * l->_values_per_node - 1);
      if (n->values == NULL) {
        printf("is empty\n");
      } else {
        printf("contains:\n");
        for(int i = 0; i < l->_values_per_node; i += 1) {
          printf("    %lu: %d\n", chunk_index * l->_values_per_node + i, n->values[i]);
        }
      }
      n = n->next;
      chunk_index += 1;
    }
  }
}

ChunkListNode *chunklist__init_chunk(ChunkList *l, ChunkListNode *c) {
  size_t chunk_size = sizeof(value_t) * l->_values_per_node;
  c->values = malloc(chunk_size);
  memset(c->values, 0, chunk_size);
  return c;
}

ChunkListNode *chunklist__new_chunk() {
  ChunkListNode *n;
  n = malloc(sizeof(ChunkListNode));
  n->next = NULL;
  n->values = NULL;
  return n;
}

ChunkListNode *chunklist__grow_to_index(ChunkList *l, index_t to_index) {
  ChunkListNode *head, *backref;
  index_t chunk_index = 1;
  head = l->head;

  while (chunk_index * l->_values_per_node <= to_index) {
    backref = head;
    head = head->next;
    chunk_index += 1;
    if (head == NULL) {
      head = chunklist__new_chunk();
      backref->next = head;
    }
  }
  return head;
}

ChunkListNode *chunklist__get_chunk_for_index(ChunkList *l, index_t to_index) {
  ChunkListNode *head;
  head = chunklist__grow_to_index(l, to_index);

  if (head->values == NULL) {
    chunklist__init_chunk(l, head);
  }

  return head;
}

chunklist.h

#ifndef CHUNKLIST_H
#define CHUNKLIST_H

#include <stddef.h>

typedef unsigned int value_t;
typedef unsigned int index_t;

typedef struct ChunkList ChunkList;
typedef struct ChunkListNode ChunkListNode;

/**
 * ChunkList
 *
 * A Chunk list is a NULL-terminated, single-linked list of simple
 * arrays.  The 'head' node points to the very beginning of this list.
 *
 * The size of each node is kept in '_values_per_node'.  It should
 * never be modified after the list has been initialized.
 */
struct ChunkList {
  ChunkListNode *head;
  size_t _values_per_node;
};

/**
 * ChunkList Node
 *
 * When the array-pointer is null, the node is 'uninitialized'.
 *
 * The 'next' pointer is either NULL or points to another node.
 */
struct ChunkListNode {
  value_t *values;
  ChunkListNode *next;
};

ChunkList *chunklist_new(size_t);
ChunkList *chunklist_init(ChunkList *, size_t);
void       chunklist_del(ChunkList *);

value_t chunklist_get(ChunkList *, index_t);
value_t chunklist_set(ChunkList *, index_t, value_t);

void chunklist_print(ChunkList *);

#endif

Makefile

test.o: test.c chunklist.c chunklist.h
	gcc -o test.o test.c chunklist.c

prototype.py

class ChunkList:
    """The unholy lovechild of arrays and linked lists

The chunk-list is a data-structure idea I had as I laid down to sleep.
It's surely not original, but *stitch voice* this one is mine.

Basically, we have a linked list of arrays.  Each element of the
linked list is an array of SIZE elements where SIZE is set in the
constructor.  When we access an index of the chunk-list, we first make
sure we have enough slots for arrays by adding placeholders until we
reach an array that can store our index.  (See _grow_to.)  When that
slot is dereferenced (i.e., we need to retrieve or set a value), we
initialize the array with values.  We only create containers for the
chunks we have information in.

This is a good data structure when your data will be clustered.

This is a prototype for a C implementation.

    """
    class Array:
        """A basic array."""
        def __init__(self, size):
            self.values = [None] * size
        def __getitem__(self, index):
            return self.values[index]
        def __setitem__(self, index, value):
            self.values[index] = value

    def __init__(self, size=100):
        self._size = size
        self._arrays = list()
    def __getitem__(self, index):
        self._grow_to(index)
        return self._arrays[index // self._size][index % self._size]
    def __setitem__(self, index, value):
        self._grow_to(index)
        self._arrays[index // self._size][index % self._size] = value
    def _grow_to(self, index):
        while len(self._arrays) < index // self._size:
            self._arrays.append(None)
        if len(self._arrays) == index // self._size:
            self._arrays.append(ChunkList.Array(self._size))

# tests
a = ChunkList(500)

a[29] = 5
print(a[29])

a[230203] = 40
print(a[230203])

test.c

#include "chunklist.h"
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv)
{
  ChunkList *l = chunklist_new(10);
  chunklist_set(l, 13, 13);
  chunklist_set(l, 48, 48);
  chunklist_set(l, 20, 20);
  chunklist_set(l, 132, 132);
  chunklist_print(l);
}