X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/b010eea06ca2993294d4bc3410dacd74fb7225d5..4a69abcc786d029bd2962537f767d12a0f808d11:/src/xbt/lib.c

diff --git a/src/xbt/lib.c b/src/xbt/lib.c
index 902d5ffc5e..068652e41a 100644
--- a/src/xbt/lib.c
+++ b/src/xbt/lib.c
@@ -1,460 +1,125 @@
-/*
- * lib.c
- *
- *  Created on: 16 mars 2011
- *      Author: navarrop
- */
+/* lib - a generic library, variation over dictionary                    */
 
-#include <string.h>
-#include <stdio.h>
-#include "xbt/misc.h"           /* SG_BEGIN_DECL */
-#include "xbt/mallocator.h"
-#include "xbt/ex.h"
-#include "xbt/log.h"
-#include "xbt_modinter.h"
-#include "xbt/lib.h"
+/* Copyright (c) 2011, 2013-2015. The SimGrid Team.
+ * All rights reserved.                                                     */
 
-#define DJB2_HASH_FUNCTION
-//#define FNV_HASH_FUNCTION
+/* 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. */
 
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_lib, xbt,
-                                "Libraries provide the same functionalities than hash tables");
+#include <xbt/asserts.h>
+#include <xbt/sysdep.h>
+#include <xbt/log.h>
+#include <xbt/lib.h>
 
-xbt_mallocator_t lib_mallocator = NULL;
-
-/*####[ Private prototypes ]#################################################*/
-static void *lib_mallocator_new_f(void);
-static void lib_mallocator_free_f(void *dict);
-static void lib_mallocator_reset_f(void *dict);
-
-static void xbt_lib_set_ext(xbt_lib_t lib,const char *key,
-                            int key_len, int level, void *data);
-
-static unsigned int xbt_lib_hash_ext(const char *str,
-                                                 int str_len);
-static unsigned int xbt_lib_hash(const char *str);
-static void xbt_lib_rehash(xbt_lib_t lib);
-
-
-static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib);
-static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor);
-static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor);
-
-/*####[ Code ]###############################################################*/
-
-void xbt_lib_preinit(void)
-{
-  if (lib_mallocator != NULL) {
-    xbt_mallocator_free(lib_mallocator);
-  }
-
-  lib_mallocator = xbt_mallocator_new(256,
-                                       lib_mallocator_new_f,
-                                       lib_mallocator_free_f,
-                                       lib_mallocator_reset_f);
-}
-
-void xbt_lib_postexit(void)
-{
-  if (lib_mallocator != NULL) {
-    xbt_mallocator_free(lib_mallocator);
-    lib_mallocator = NULL;
-  }
-}
-
-static xbt_libelm_t xbt_libelm_new(const char *key,
-                              int key_len,
-                              unsigned int hash_code,
-                              void *content,int level, int level_numbers)
-{
-  xbt_libelm_t element = xbt_malloc0(sizeof (s_xbt_libelm_t) + sizeof(void *)*(level_numbers-1));
-
-  element->key = xbt_new(char, key_len + 1);
-  memcpy((void *) element->key, (void *) key, key_len);
-  element->key[key_len] = '\0';
-
-  element->key_len = key_len;
-  element->hash_code = hash_code;
-
-  (&(element->content))[level] = content;
-  element->next = NULL;
-
-  return element;
-}
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_lib, xbt, "A dict with keys of type (name, level)");
 
 xbt_lib_t xbt_lib_new(void)
 {
-  xbt_lib_t lib;
-  lib = xbt_mallocator_get(lib_mallocator);
-  lib->table_size = 127;
-  lib->table = xbt_new0(xbt_libelm_t, lib->table_size + 1);
-  lib->count = 0;
-  lib->fill = 0;
+  xbt_lib_t lib  = xbt_new(s_xbt_lib_t, 1);
+  lib->dict = xbt_dict_new_homogeneous(xbt_free_f);
   lib->levels = 0;
   lib->free_f = NULL;
-
   return lib;
 }
 
-void xbt_lib_free(xbt_lib_t * lib)
+void xbt_lib_free(xbt_lib_t *plib)
 {
-  int i,j;
-  xbt_libelm_t current, previous;
-  int table_size;
-  xbt_libelm_t *table;
-
-  //  if ( *dict )  xbt_dict_dump_sizes(*dict);
-
-  if (lib != NULL && *lib != NULL) {
-    table_size = (*lib)->table_size;
-    table = (*lib)->table;
-
-    for (i = 0; (*lib)->count && i <= table_size; i++) {
-      current = table[i];
-      while (current != NULL) {
-			previous = current;
-			current = current->next;
-			xbt_free(previous->key);
-			for(j=0; j< (*lib)->levels; j++)
-			  if((&(previous->content))[j])
-				  (*lib)->free_f[j]( (&(previous->content))[j]);
-	    	xbt_free(previous);
-			(*lib)->count--;
-      }
+  xbt_lib_t lib = *plib;
+  if (lib) {
+    xbt_dict_cursor_t cursor;
+    char *key;
+    void **elts;
+    xbt_dict_foreach (lib->dict, cursor, key, elts) {
+      int i;
+      for (i = 0 ; i < lib->levels ; i++)
+        if (elts[i] && lib->free_f[i])
+          lib->free_f[i](elts[i]);
     }
-    xbt_free(table);
-    xbt_free((*lib)->free_f);
-    xbt_mallocator_release(lib_mallocator, *lib);
-    *lib = NULL;
+    xbt_dict_free(&lib->dict);
+    xbt_free(lib->free_f);
+    xbt_free(lib);
+    *plib = NULL;
   }
 }
 
 int xbt_lib_add_level(xbt_lib_t lib, void_f_pvoid_t free_f)
 {
-	XBT_DEBUG("xbt_lib_add_level");
-
-	lib->free_f = realloc(lib->free_f,sizeof(void_f_pvoid_t)*(lib->levels+1));
-	lib->free_f[lib->levels]=free_f;
-	return lib->levels++;
-}
-
-void xbt_lib_set(xbt_lib_t lib, const char *name, int level, void *obj)
-{
-	XBT_INFO("xbt_lib_set key '%s' with object '%p'",name,obj);
-	xbt_lib_set_ext(lib, name, strlen(name),level, obj);
-}
-
-void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
-{
-	unsigned int hash_code = xbt_lib_hash(key);
-	xbt_libelm_t current;
-
-	if(!lib) xbt_die("Lib is NULL!");
-
-	current = lib->table[hash_code & lib->table_size];
-	while (current != NULL &&
-		 (hash_code != current->hash_code || strcmp(key, current->key)))
-	current = current->next;
-
-	if (current == NULL)
-	return NULL;
-
-	return (&(current->content))[level];
-}
-
-static void *lib_mallocator_new_f(void)
-{
-  return xbt_new(s_xbt_lib_t, 1);
-}
-
-static void lib_mallocator_free_f(void *lib)
-{
-  xbt_free(lib);
+  XBT_DEBUG("xbt_lib_add_level");
+  xbt_assert(xbt_dict_is_empty(lib->dict), "Lib is not empty (size: %u), cannot add a level", xbt_dict_size(lib->dict));
+  lib->free_f = xbt_realloc(lib->free_f, sizeof(void_f_pvoid_t) * (lib->levels + 1));
+  lib->free_f[lib->levels] = free_f;
+  return lib->levels++;
 }
 
-static void lib_mallocator_reset_f(void *lib)
+void xbt_lib_set(xbt_lib_t lib, const char *key, int level, void *obj)
 {
-  /* nothing to do because all fields are
-   * initialized in xbt_dict_new
-   */
-}
-
-void xbt_lib_reset(xbt_lib_t *lib)
-{
-	XBT_INFO("xbt_lib_reset");
-  int i,j;
-  xbt_libelm_t current, next;
-  xbt_lib_t l = *lib;
-  int levels = l->levels;
-  if(!(*lib)) xbt_die("Lib is NULL!");
-
-  if (l->count == 0)
-    return;
-
-  for (i = 0; i <= l->table_size; i++) {
-    current = l->table[i];
-    while (current) {
-    	next = current->next;
-    	xbt_free(current->key);
-    	for(j=0; j< levels; j++)
-    		if((&(current->content))[j] && (l->free_f[j]))
-    			l->free_f[j]((&(current->content))[j]);
-    	xbt_free(current);
-    	current = next;
-    }
-    l->table[i] = NULL;
+  XBT_DEBUG("xbt_lib_set key '%s:%d' with object %p", key, level, obj);
+  xbt_assert(level >= 0);
+  void **elts = xbt_dict_get_or_null(lib->dict, key);
+  if (!elts) {
+    elts = xbt_new0(void *, lib->levels);
+    xbt_dict_set(lib->dict, key, elts, NULL);
   }
-  xbt_free(l->free_f);
-  l->count = 0;
-  l->fill = 0;
-  l->levels = 0;
-  l->free_f = NULL;
-}
-
-int xbt_lib_length(xbt_lib_t lib)
-{
-  if(!lib) xbt_die("Lib is NULL!");
-  return lib->count;
-}
-
-static void xbt_lib_set_ext(xbt_lib_t lib,
-                            const char *key,
-                            int key_len,
-                            int level,
-                            void *data)
-{
-
-  unsigned int hash_code = xbt_lib_hash_ext(key, key_len);
-
-  xbt_libelm_t current, previous = NULL;
-  if(!lib) xbt_die("Lib is NULL!");
-
-  XBT_DEBUG("ADD '%.*s' hash = '%d', size = '%d', & = '%d' to level : %d",
-		  key_len,
-		  key,
-		  hash_code,
-          lib->table_size,
-          hash_code & lib->table_size,
-          level);
-
-  current = lib->table[hash_code & lib->table_size];
-  while (current != NULL &&
-         (hash_code != current->hash_code || key_len != current->key_len
-          || memcmp(key, current->key, key_len))) {
-    previous = current;
-    current = current->next;
+  if (elts[level]) {
+    XBT_DEBUG("Replace %p by %p element under key '%s:%d'", elts[level], obj, key, level);
+    if (lib->free_f[level])
+      lib->free_f[level](elts[level]);
   }
-
-  if (current == NULL) {/* this key doesn't exist yet */
-		current = xbt_libelm_new(key, key_len, hash_code, data,level,lib->levels);
-		lib->count++;
-		if (previous == NULL) {
-		lib->table[hash_code & lib->table_size] = current;
-		lib->fill++;
-		if ((lib->fill * 100) / (lib->table_size + 1) > MAX_FILL_PERCENT)
-		  xbt_lib_rehash(lib);
-		} else {
-		previous->next = current;
-		}
-  }
-  else
-	  if( (&(current->content))[level] == NULL )/* this key exist but level is empty */
-	  {
-		  (&(current->content))[level] = data;
-	  }
-	  else
-	  {/* there is already an element with the same key: overwrite it */
-			XBT_INFO("Replace %.*s by %.*s under key %.*s",
-				   key_len, (char *) (&(current->content))[level],
-				   key_len, (char *) data, key_len, (char *) key);
-			if (current->content != NULL) {
-			  free((&(current->content))[level]);
-			}
-			(&(current->content))[level] = data;
-	  }
+  elts[level] = obj;
 }
 
-/**
- * Returns the hash code of a string.
- */
-static unsigned int xbt_lib_hash_ext(const char *str,
-                                                 int str_len)
+void xbt_lib_unset(xbt_lib_t lib, const char *key, int level, int invoke_callback)
 {
-
-
-#ifdef DJB2_HASH_FUNCTION
-  /* fast implementation of djb2 algorithm */
-  int c;
-  register unsigned int hash = 5381;
-
-  while (str_len--) {
-    c = *str++;
-    hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
-  }
-# elif defined(FNV_HASH_FUNCTION)
-  register unsigned int hash = 0x811c9dc5;
-  unsigned char *bp = (unsigned char *) str;    /* start of buffer */
-  unsigned char *be = bp + str_len;     /* beyond end of buffer */
-
-  while (bp < be) {
-    /* multiply by the 32 bit FNV magic prime mod 2^32 */
-    hash +=
-        (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
-        (hash << 24);
-
-    /* xor the bottom with the current octet */
-    hash ^= (unsigned int) *bp++;
-  }
-
-# else
-  register unsigned int hash = 0;
-
-  while (str_len--) {
-    hash += (*str) * (*str);
-    str++;
+  xbt_assert(level >= 0);
+  void **elts = xbt_dict_get_or_null(lib->dict, key);
+  if (!elts) {
+     XBT_WARN("no key %s", key);
+     return;
   }
-#endif
-
-  return hash;
-}
 
-static unsigned int xbt_lib_hash(const char *str)
-{
-#ifdef DJB2_HASH_FUNCTION
-  /* fast implementation of djb2 algorithm */
-  int c;
-  register unsigned int hash = 5381;
-
-  while ((c = *str++)) {
-    hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
+  void *obj = elts[level];
+  if (!obj) {
+     XBT_WARN("no key %s at level %d", key, level);
+     return;
   }
 
-# elif defined(FNV_HASH_FUNCTION)
-  register unsigned int hash = 0x811c9dc5;
-
-  while (*str) {
-    /* multiply by the 32 bit FNV magic prime mod 2^32 */
-    hash +=
-        (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
-        (hash << 24);
+  XBT_DEBUG("Remove %p of key %s at level %d", obj, key, level);
+  elts[level] = NULL;
 
-    /* xor the bottom with the current byte */
-    hash ^= (unsigned int) *str++;
+  /* check if there still remains any elements of this key */
+  int empty = 1;
+  for (int i = 0; i < lib->levels && empty; i++) {
+     if (elts[i] != NULL)
+       empty = 0;
   }
-
-# else
-  register unsigned int hash = 0;
-
-  while (*str) {
-    hash += (*str) * (*str);
-    str++;
+  if (empty) {
+    /* there is no element at any level, so delete the key */
+    xbt_dict_remove(lib->dict, key);
   }
-#endif
-  return hash;
-}
 
-static void xbt_lib_rehash(xbt_lib_t lib)
-{
-	xbt_die("xbt_lib_rehash not yet implemented!");
+  if (invoke_callback && lib->free_f[level])
+    lib->free_f[level](obj);
 }
 
-void xbt_lib_cursor_first(const xbt_lib_t lib,
-                                      xbt_lib_cursor_t * cursor)
-{
-  XBT_DEBUG("xbt_lib_cursor_first");
-  if (!*cursor) {
-    XBT_DEBUG("Create the cursor on first use");
-    *cursor = xbt_lib_cursor_new(lib);
-  } else {
-    xbt_lib_cursor_rewind(*cursor);
-  }
-  if (lib != NULL && (*cursor)->current == NULL) {
-    xbt_lib_cursor_step(*cursor);      /* find the first element */
-  }
-}
-
-static xbt_lib_cursor_t xbt_lib_cursor_new(const xbt_lib_t lib)
+void *xbt_lib_get_or_null(xbt_lib_t lib, const char *key, int level)
 {
-  xbt_lib_cursor_t res = NULL;
-
-  res = xbt_new(s_xbt_lib_cursor_t, 1);
-  res->lib = lib;
-
-  xbt_lib_cursor_rewind(res);
-
-  return res;
+  xbt_assert(level >= 0);
+  void **elts = xbt_dict_get_or_null(lib->dict, key);
+  return elts ? elts[level] : NULL;
 }
 
-static void xbt_lib_cursor_rewind(xbt_lib_cursor_t cursor)
+xbt_dictelm_t xbt_lib_get_elm_or_null(xbt_lib_t lib, const char *key)
 {
-  XBT_DEBUG("xbt_lib_cursor_rewind");
-  xbt_assert(cursor);
-
-  cursor->line = 0;
-  if (cursor->lib != NULL) {
-    cursor->current = cursor->lib->table[0];
-  } else {
-    cursor->current = NULL;
-  }
+  return xbt_dict_get_elm_or_null(lib->dict, key);
 }
 
-int xbt_lib_cursor_get_or_free(xbt_lib_cursor_t * cursor,
-                                           char **key, void **data)
+void *xbt_lib_get_level(xbt_dictelm_t elm, int level)
 {
-
-  xbt_libelm_t current;
-
-  XBT_DEBUG("xbt_lib_get_or_free");
-
-  if (!cursor || !(*cursor))
-    return FALSE;
-
-  current = (*cursor)->current;
-  if (current == NULL) {        /* no data left */
-    xbt_lib_cursor_free(cursor);
-    return FALSE;
-  }
-
-  *key = current->key;
-  *data = &(current->content);
-  return TRUE;
+  xbt_assert(level >= 0);
+  void **elts = elm->content;
+  return elts ? elts[level] : NULL;
 }
 
-static void xbt_lib_cursor_free(xbt_lib_cursor_t * cursor)
-{
-  if (*cursor) {
-    xbt_free(*cursor);
-    *cursor = NULL;
-  }
-}
-
-void xbt_lib_cursor_step(xbt_lib_cursor_t cursor)
-{
-  xbt_libelm_t current;
-  int line;
-
-  XBT_DEBUG("xbt_lib_cursor_step");
-  xbt_assert(cursor);
-
-  current = cursor->current;
-  line = cursor->line;
-
-  if (cursor->lib != NULL) {
-
-    if (current != NULL) {
-      XBT_DEBUG("current is not null, take the next element");
-      current = current->next;
-      XBT_DEBUG("next element: %p", current);
-    }
-
-    while (current == NULL && ++line <= cursor->lib->table_size) {
-      XBT_DEBUG("current is NULL, take the next line");
-      current = cursor->lib->table[line];
-      XBT_DEBUG("element in the next line: %p", current);
-    }
-    XBT_DEBUG("search finished, current = %p, line = %d", current, line);
-
-    cursor->current = current;
-    cursor->line = line;
-  }
+void xbt_lib_remove(xbt_lib_t lib, const char *key){
+  xbt_dict_remove(lib->dict, key);
 }