[ioke-dev] Re: Data structure melee

["Kosta Welke" <kosta@fillibach.de>]

Note: I seem to constantly forget to hit "Reply All". This orginially only  
went to Ola.

On Thu, 29 Jan 2009 13:43:00 +0100, Ola Bini <ola.bini@gmail.com> wrote:

Hi!

I decided instead of arguing about Steve's Blog post I better reply to
your orignal message.

Approach 1)
> 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;
> }

Approach 2)
> 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;
> }

Well if I'm not mistaken, this basically a hashtable of a linked list of
the actual cells. In total, it contains all the objects cell and all
mimic'ed cells.

The big problem I see is that if we update a parent, all children need to
be informed. This could be eased by also remembering where the node comes
from:

Object getCell(String name) {
    Node node = hashtable.find(name);
    if (null == node)
      return null;
    if (node.local)
      //cell from this object
      return node.value;
    else
      //cell mimic'd
      return node.pointer.value;
}

Now we only need to update children if cells are inserted or deleted. When
inserting into node n, we only need to update children whose first parent
is not n.

Do I make any sense?

Cheers,
Kosta