Ed's Big Plans

Computing for Science and Awesome

fridgelib — Andre’s C Library

with 3 comments

Brief: Fridge Library (fridgelib) is a light weight C library that’s basically what each C programmer eventually comes away with. Fridgelib contains a queue, stack and trie data type implementation– these implementations are cleaner than mine, hence I have devoured them into my code where necessary.

There is however one item that Andre’s told me I can add to fridgelib if I can ever tidy it up, and that’s my evil linked-array. It’s basically a doubly linked list whose elements are arrays of fixed size; the traversal is cut down by a multiple of that array size while indexing thereafter is still constant time given the modulus of the index. My evil implementation is a double-headed stack/queue/array which supported python-like negative-value indexing, slicing and iteration… actually, that’s when I decided it had grown too grotesque and left it to sit in my repository…

I’ll probably return to it later, to remove slicing and to more cleanly define the semantics of iteration.

Hmm– the only things that are really missing from fridgelib are the hashtable and either a nice red-black tree or a treap…

Eddie Ma

November 23rd, 2009 at 1:14 pm

Brandon says...

Yo! Holy crap you have a blog. Interesting concept of a linked array. Do the allocations increase exponentially? You would have an interesting problem trying to keep constant time because even if your allocations increase exponentially, if you have a large number, you would have to traverse the small nodes first.

Eddie Ma says...

No, the allocations increase at a constant size 🙂

The modulus short cut can only work that way– this pseudocode should clear it up… I haven’t checked for off-by-one logical errors– this’ll give you the sense of what I’m doing though.

Pseudocode:

function get linkedArray this, int index:
    int which_page = index / length of one internal array
    int which_index_in_page = index % length of one internal array
    internalArray this_page = this -> start
    for int i = 0; i < which_page; i++
        this_page = this_page ->> next
    return this_page -> array[ which_index_in_page ]
struct linkedArray:
    int length of one internal array
    internalArray start
struct internalArray:
    generic array
    internalArray next

Note that I haven’t added anything in the above to convert out of Python-style negative-indices– I also had an optimization that would traverse the list of arrays from the last internal array instead of the first internal array if the selected index is actually on a ‘page’ that’s past the midpoint of the list.

Edit: Getting pseudocode in html to work well in WordPress comments is a pain…

Brandon says...

Hmm, if you double the number and start the array size at 1, the capacity:

sum of 1->numPages 2**maxIndex

You could either do a O(lg(maxIndex)) (using bit shifting) access if you don’t store where all the pages start, or a O(1) access if you do. It’s an extra 4 bytes per page plus the occasional expansion of the index which should happen seldomly. That way inserts are no longer a max O(numberInserted/number per array) but O(lg(numberInserted)).

Heavier on the memory but saves big time on write time. I like this idea though, never heard of a linked array. Arbitrary inserts aren’t so bad because you can just expand one array rather than all of them, that’s so smart!

I suppose though, if you knew that the inserts were constant, then your data structure would be better. It really does depend on application.