From: alegrand <alegrand@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Date: Thu, 4 Nov 2004 03:27:23 +0000 (+0000)
Subject: Added a dichotomy to the dictionnaries. make check works as well before so I
X-Git-Tag: v3.3~4868
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/2ec77ead8131d77ef5201888c49ae61681fa3922

Added a dichotomy to the dictionnaries. make check works as well before so I
assume that the patch is correct. I do not know however if things run
effectively faster than before now. :)


git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@482 48e7efb5-ca39-0410-a469-dd3cf9ba447f
---

diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c
index 99423b575a..5616959e00 100644
--- a/src/xbt/dict_elm.c
+++ b/src/xbt/dict_elm.c
@@ -342,16 +342,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;
-
-    _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
-
-    if (m)
-      break;
-
-    o = *p_offset;
-    m = 0;
+  if(1) {
+    int p_min = 0;
+    int p_max = len-1;
+    int cmp = 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;