gistfile1.txt

commit a115ab32c2d4d9d320fe758067915e719c44ab36
Merge: 7e15c7f 777012a
Author: M.Schneider <not.m.schneider@gmail.com>
Date:   Mon Feb 21 22:45:06 2011 +0100

    deleted branch iterator

diff --cc scdb.cc
index 1dc88e7,dd1f916..0b02cea
--- a/scdb.cc
+++ b/scdb.cc
@@@ -1281,51 -1025,12 +1281,47 @@@ scdb_iterator* scdb_iterate(scdb_index
          const char* key, size_t key_length)
  {
      if(key_length > SCDB_MAX_KEY_LENGTH) return NULL;
--    scdb_iterator* iterator = new scdb_iterator(index);
-     
-     if(key == NULL || key_length == 0) {
-         // search for the first key
 -    // search for the first key
 -    iterator->initial_seek_next();
 -    // if the specified key is not the empty key, and the index contains a
 -    // non-empty key we try to find it TODO not implemented yet
 -    if (key_length > 0 && !iterator->is_at_end()) assert(false);
++    scdb_iterator* iterator = new scdb_iterator(index);    
++    if(key == NULL || key_length == 0)
++    { // search for the first key
 +        iterator->initial_seek_next();
-     } else {
-         // starting in the middle of the trie
-         
++    } else { // starting in the middle of the trie
 +        memcpy(iterator->current_key, key, key_length);
 +        
 +        // Search for the key. If it was found, everything is perfect. If not, we will have
 +        // the list of parent nodes up to which the key was found and the length of the
 +        // key that was "consumed". This way we can just start at that node and go to the
 +        // next node
 +        
 +        size_t remaining_key_length;
 +        iterator->current_node = scdb_node_find(index->root,
 +                                                key,
 +                                                key_length,
 +                                                &(iterator->parent_nodes), &remaining_key_length);
 +        
 +        bool node_found = (iterator->current_node != NULL);
 +        
 +        if(node_found) {
 +            iterator->last_seek_status = SCDB_OK;
 +            iterator->current_key_length = key_length;
 +        } else {
 +            iterator->current_key_length = key_length - remaining_key_length;
 +            memcpy(iterator->current_key, key, iterator->current_key_length); // size was checked above
 +            
 +            // set iterator to last node that was matched
 +            iterator->current_node = iterator->parent_nodes.top();
 +            // we are at level n, so we have to remove the key that belongs to that node
 +            iterator->current_key_length -= (iterator->current_node->key_length + 1);
 +            // we need to go down to the first leave
 +            iterator->seek_first_leave();
 +            // from here, we go forward until we find the first key greater than the search key
 +            iterator->last_seek_status = iterator->seek_next();
 +            if(iterator->last_seek_status == SCDB_NOT_FOUND) {
 +                DEBUG("Iterator key not found, no next node found");
 +                return NULL;
 +            }
 +        }
 +    }
-     
      return iterator;
  }
  
@@@ -1416,22 -1119,14 +1412,18 @@@ scdb_status scdb_next(scdb_iterator* it
          char* key_buffer, size_t* key_buffer_length,
          char* value_buffer, size_t* value_buffer_length)
  {
-     if (iterator->is_at_end()) {
 -    if (iterator->is_at_end()) return SCDB_NOT_FOUND;
++    if (iterator->is_at_end())
 +        return SCDB_NOT_FOUND;
-     }
-     if (*key_buffer_length < iterator->current_key_length) {
++        
+     if (*key_buffer_length < iterator->current_key_length)
          return SCDB_KEY_BUFFER_TOO_SMALL;
-     }
-     
++        
      iterator->write_key(key_buffer, key_buffer_length);
-     
-     if(*value_buffer_length < iterator->current_value_length()) {
+     if(*value_buffer_length < iterator->current_value_length())
          return SCDB_VALUE_BUFFER_TOO_SMALL;
-     }
- 
++        
      iterator->write_value(value_buffer, value_buffer_length);
      iterator->last_seek_status = iterator->seek_next();
-     
      return SCDB_OK;
  }
  
diff --cc scdb2.h
index a6aa2d5,4ae2de0..39ea5de
--- a/scdb2.h
+++ b/scdb2.h
@@@ -279,7 -220,7 +279,7 @@@ struct nod
      
      char * node_chars() const
      {
--        return (((char*) (this + 1)) + key_length);
++        return ((node**) (((char*)(this + 1)) + key_length + size));
      }
      
      char nth_node_char(node_length_t node_index) const
@@@ -288,7 -229,7 +288,7 @@@
          return node_chars()[node_index];
      }
  
--    node ** node_ptr()
++    bool is_routing_node() const
      {
          return ((node**) (((char*)(this + 1)) + key_length + size));
      }