[ioke-dev] Data structure melee

[Ola Bini <ola.bini@gmail.com>]

Hi all,

So, as you know, I've been trying to find a good data structure to use 
for representations of cells in Ioke. This mail will first detail the 
problem/requirements, and then talk about my current ideas.

To recap, the current structure looks like this:

class IokeObject {
 HashMap<String, Object> cells;
 LinkedList<IokeObject> mimics;
}

finding a cell looks a bit like this:

Object getCell(String name) {
 if(cells.containsKey(name)) return cells.get(name);
 for(IokeObject mimic : mimics) {
   Object result = mimic.getCell(name);
   if(null != result) return result;
 }
 return null;
}

Searching cells is the most important operation. Inserting cells is the 
next most important. Removing cells, changing mimics, iterating over 
cells or mimics are all of less importance and it's ok to have them be 
expensive - although not TOO expensive.

All of the above operations can happen at any time. Which means that the 
global state will never settle down.

I have investigated using tries, trees and associative arrays. In their 
basic forms, all of these are unsuitable for the combination of operations.

My current thinking is that we need a separate data structure that works 
a bit like a hashmap, except that the number of buckets are globally 
fixed. That means each linked list of entries in the buckets can have as 
its last element a link to the bucket of the next mimics map. So a 
search will entail first calculating the hash of an entry, finding that 
bucket in the self-map, and then start traversing until it comes to the 
end - or it finds something. To make this process easier, we can intern 
all cell names. In pseudo code the lookup would be this:

Object getCell(String name) {
 assert name == name.intern();
 int hash = name.hashCode();
 EntryNode node = buckets[hash % NUMBER_OF_BUCKETS];
 while(node != null) {
   if(node.name == name) return node.value;
   node = node.next;
 }
 return null;
}

Insertion and removal can be handled in several different ways. The 
really expensive operation will be to add new mimics - but that should 
be quite uncommon in a running system, so the cost of that can be amortized.

Ideas, thoughts?

--
Ola Bini (http://olabini.com) 
Ioke creator (http://ioke.org)
JRuby Core Developer (http://jruby.org)
Developer, ThoughtWorks Studios (http://studios.thoughtworks.com)
Practical JRuby on Rails (http://apress.com/book/view/9781590598818)

"Yields falsehood when quined" yields falsehood when quined.