-/*
- * 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);
}
