[MUD-Dev] Naming and Directories?

[Ola Fosheim Grøstad <olag@ifi.uio.no>]

Mark Gritter wrote:
> <GEEK mode='os/architecture'>
> There's actually a solution for handling "prefix" lookups that gets used
> (well, discussed, anyway) in handling TLB misses.  Say you have various page
> sizes, and aren't sure which size to use when looking in your inverted page
> table.  Just duplicate the entry for each of the possible prefixes.  So in
> terms of our discussion, add 'Mark', 'Mar', 'Ma', and 'M' to the hash table,
> stopping when there's a conflict with another name.
> </GEEK>

Interesting application. I think I already mentioned hashing substrings
when all those trie-freaks cried for abbrevs.

> Doh!  I was aiming for sizeof(struct node) == 32, but forgot the object
> pointer...  plus, you'd have to throw it out and start over for a new
> pointer size.  Your idea seems better, with those considerations.

Or more memory efficient:

struct node {
  object *obj; 
  node *l,*r;
  const char key[1];
};

node *new_node(char *s){
  node *n = 0;
  const char *k=n->key;

  // Ugly and not fully portable? An option would be to declare
  // key[4] and use sizeof(node)-3+strlen(s)

  size_t keyoffset=*(size_t*)(void*)&k;
  size_t keysize = strlen(s);

  void *n = calloc(1, keyoffset + keysize + 1);  
  assert(n);
  memcpy(((char*)n)+keyoffset,s,keysize + 1);
  return (node*)n;
}


Another option is to use a heap/array with the 32-bit integer version
discussed previously (reorganizing the tree will be expensive though, so
I doubt I will ever use it):

struct node { uint32 key; object *obj; };
node binarytree[LARGE_NUMBER];
--
Ola Fosheim Groestad,Norway      http://www.stud.ifi.uio.no/~olag/




_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev