X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/8f9ddec9995bd05c627517bbb7fe62451788d1e4..c415c91f074a3047abd92a7d63b59baf1c61f51a:/src/xbt/dict_elm.c

diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c
index 99423b575a..b78d452eb1 100644
--- 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;
@@ -610,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);