missing files

[simgrid.git] / src / xbt / dict_elm.c

diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c
index 20458b4..b78d452 100644 (file)
--- a/src/xbt/dict_elm.c
+++ b/src/xbt/dict_elm.c
@@ -2,11 +2,10 @@
 
 /* dict - a generic dictionnary, variation over the B-tree concept          */
 
-/* Authors: Martin Quinson                                                  */
-/* Copyright (C) 2003 the OURAGAN project.                                  */
+/* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved.            */
 
 /* This program is free software; you can redistribute it and/or modify it
-   under the terms of the license (GNU LGPL) which comes with this package. */
+ * under the terms of the license (GNU LGPL) which comes with this package. */
 
 #include "dict_private.h"  /* prototypes of this module */
 
@@ -131,7 +130,6 @@ _xbt_dictelm_alloc(char                *key,
                    void                *data,
                    void_f_pvoid_t      *free_f,
                  /*OUT*/s_xbt_dictelm_t **pp_elm) {
-  xbt_error_t   errcode = no_error;
   s_xbt_dictelm_t *p_elm  = NULL;
 
   p_elm = xbt_new(s_xbt_dictelm_t,1);
@@ -342,16 +340,59 @@ _xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm,
 
   len = xbt_dynar_length(p_elm->sub);
 
-  for (p = 0; p < len; p++) {
-    int          cmp     = 0;
+  if(1) {
+    int p_min = 0;
+    int p_max = len-1;
+    int cmp = 0;
 
-    _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
-
-    if (m)
-      break;
-
-    o = *p_offset;
-    m = 0;
+    p = p_min;
+    if(len==0) {
+      p=0;
+    } else {
+      _dict_child_cmp(p_elm, p_min, key, key_len, &o, &m, &cmp);
+      if(!m) { /* OK, maybe it is somewhere else. */
+       o = *p_offset;
+       if (cmp<0) { /* Insert at the very beginning */
+         p=0;
+       } else if (p_max<=0) { /* No way. It is not there. Insert à the very end */
+         p=p_max+1;
+         m = 0;
+       } else { 
+         p=p_max;
+         _dict_child_cmp(p_elm, p_max, key, key_len, &o, &m, &cmp);
+         if(!m) {
+           o = *p_offset;
+           if(cmp>0) { /* Should be located at the end of the table */
+             p=p_max+1;
+           } else { /* Too bad, let's go for a dichotomic search. */
+             while(p_max-p_min>1) {
+               _dict_child_cmp(p_elm, (p_min+p_max)/2, key, key_len, &o, &m, &cmp);
+               if(m) break;
+               o = *p_offset;
+               if(cmp<0) p_max=(p_min+p_max)/2;
+               if(cmp>0) p_min=(p_min+p_max)/2;
+             } 
+             if(m) /* We have the element */
+               p=(p_min+p_max)/2 ;
+             else /* it should be inserted just after p_min */
+               p=p_min + 1;
+           }
+         } 
+       }
+      }
+    }
+  } else {
+    for (p = 0; p < len; p++) {
+      int          cmp     = 0;
+      
+      _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
+      
+      if (m)
+       break;
+      
+      o = *p_offset;
+      m = 0;
+    }
   }
 
   *p_offset = o;
@@ -395,7 +436,6 @@ _xbt_dictelm_change_value(s_xbt_dictelm_t    *p_elm,
  * @key: the key to set the new data
  * @offset: offset on key.
  * @data: the data to add in the dict
- * @Returns: a gras_error
  *
  * set the @data in the structure under the @key. The @key is destroyed
  * in the process. Think to strdup it before.
@@ -539,7 +579,6 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t     *p_head,
  * @head: the head of the dict
  * @key: the key to set the new data
  * @data: the data to add in the dict
- * @Returns: a gras_error
  *
  * set the @data in the structure under the @key, which can be any kind 
  * of data, as long as its length is provided in @key_len.
@@ -581,7 +620,6 @@ xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head,
  * @head: the head of the dict
  * @key: the key to set the new data
  * @data: the data to add in the dict
- * @Returns: a gras_error
  *
  * set the @data in the structure under the @key, which is a 
  * null terminated string.
@@ -602,7 +640,7 @@ xbt_dictelm_set(s_xbt_dictelm_t **pp_head,
  * @key: the key to find data
  * @offset: offset on the key
  * @data: the data that we are looking for
- * @Returns: gras_error
+ * @Returns: xbt_error
  *
  * Search the given @key. mismatch_error when not found.
  */
@@ -613,7 +651,6 @@ _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head,
                      int             key_len,
                      int             offset,
                      void **data) {
-  void *res;
 
   CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)p_head); 
 
@@ -677,7 +714,7 @@ _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head,
  * @head: the head of the dict
  * @key: the key to find data
  * @data: the data that we are looking for
- * @Returns: gras_error
+ * @Returns: xbt_error
  *
  * Search the given @key. mismatch_error when not found.
  */
@@ -700,7 +737,7 @@ xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head,
  * @head: the head of the dict
  * @key: the key to find data
  * @data: the data that we are looking for
- * @Returns: gras_error
+ * @Returns: xbt_error
  *
  * Search the given @key. mismatch_error when not found.
  */