/* 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 */
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);
xbt_dynar_free(&(p_elm->sub));
if (p_elm->key) {
- xbt_free(p_elm->key);
+ free(p_elm->key);
}
if (p_elm->free_f && p_elm->content) {
p_elm->free_f(p_elm->content);
}
- xbt_free(p_elm);
+ free(p_elm);
*pp_elm = NULL;
}
}
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;
* @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.
CDEBUG0(dict_add, "--> Change the value of head");
_xbt_dictelm_change_value(p_head, data, free_f);
- xbt_free(key); /* Keep the key used in the tree */
+ free(key); /* Keep the key used in the tree */
return;
}
CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child);
_xbt_dictelm_change_value(p_child, data, free_f);
- xbt_free(key);
+ free(key);
return;
}
* @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.
* @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.
* @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.
*/
int key_len,
int offset,
void **data) {
- void *res;
CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)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.
*/
* @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.
*/
head->content = child->content;
head->free_f = child->free_f;
- xbt_free(head->key);
+ free(head->key);
head->key = child->key;
head->key_len = child->key_len;
xbt_dynar_free_container(&(head->sub)) ;
head->sub = child->sub;
- xbt_free(child);
+ free(child);
}
/**
printf("%.*s|(%d)", key_len-offset, key_string + offset, offset);
- xbt_free(key_string);
+ free(key_string);
}
}
