/* -*- linux-c -*- */
/** @file map.c
* @brief Implements maps (associative arrays) and lists
*/
static int map_sizes[] = {
sizeof(struct map_node_int64),
sizeof(struct map_node_stat),
sizeof(struct map_node_str),
0
};
static unsigned string_hash(const char *key1, const char *key2)
{
int hash = 0, count = 0;
char *v1 = (char *)key1;
char *v2 = (char *)key2;
while (*v1 && count++ < 5) {
hash += *v1++;
}
while (v2 && *v2 && count++ < 5) {
hash += *v2++;
}
return hash_long((unsigned long)hash, HASH_TABLE_BITS);
}
static unsigned mixed_hash(const char *key1, long key2)
{
int hash = 0, count = 0;
char *v = (char *)key1;
while (v && *v && count++ < 5)
hash += *v++;
return hash_long((unsigned long)(hash ^ key2), HASH_TABLE_BITS);
}
/** Create a new map.
* Maps must be created at module initialization time.
* @param max_entries The maximum number of entries allowed. Currently that number will
* be preallocated. If more entries are required, the oldest ones will be deleted. This makes
* it effectively a circular buffer. If max_entries is 0, there will be no maximum and entries
* will be allocated dynamically.
* @param type Type of values stored in this map.
* @return A MAP on success or NULL on failure.
*/
MAP _stp_map_new(unsigned max_entries, enum valtype type)
{
size_t size;
MAP m = (MAP) _stp_valloc(sizeof(struct map_root));
if (m == NULL)
return NULL;
INIT_LIST_HEAD(&m->head);
m->maxnum = max_entries;
m->type = type;
if (type >= END) {
dbug ("map_new: unknown type %d\n", type);
return NULL;
}
if (max_entries) {
void *tmp;
int i;
struct list_head *e;
INIT_LIST_HEAD(&m->pool);
size = map_sizes[type];
tmp = _stp_valloc(max_entries * size);
for (i = max_entries - 1; i >= 0; i--) {
e = i * size + tmp;
dbug ("e=%lx\n", (long)e);
list_add(e, &m->pool);
}
m->membuf = tmp;
}
return m;
}
static void map_free_strings(MAP map, struct map_node *n)
{
struct map_node_str *m = (struct map_node_str *)n;
dbug ("n = %lx\n", (long)n);
if (map->type == STRING) {
dbug ("val STRING %lx\n", (long)m->str);
if (m->str)
_stp_free(m->str);
}
if (m->n.key1type == STR) {
dbug ("key1 STR %lx\n", (long)key1str(m));
if (key1str(m))
_stp_free(key1str(m));
}
if (m->n.key2type == STR) {
dbug ("key2 STR %lx\n", (long)key2str(m));
if (key2str(m))
_stp_free(key2str(m));
}
}
/** Deletes the current element.
* If no current element (key) for this map is set, this function does nothing.
* @param map
*/
void _stp_map_key_del(MAP map)
{
struct map_node *m;
dbug ("create=%d key=%lx\n", map->create, (long)map->key);
if (map == NULL)
return;
if (map->create) {
map->create = 0;
map->key = NULL;
return;
}
if (map->key == NULL)
return;
m = (struct map_node *)map->key;
/* remove node from old hash list */
hlist_del_init(&m->hnode);
/* remove from entry list */
list_del(&m->lnode);
/* remove any allocated string storage */
map_free_strings(map, (struct map_node *)map->key);
if (map->maxnum)
list_add(&m->lnode, &map->pool);
else
_stp_free(m);
map->key = NULL;
map->num--;
}
/** Get the first element in a map.
* @param map
* @returns a pointer to the first element.
* This is typically used with _stp_map_iter(). See the foreach() macro
* for typical usage. It probably does what you want anyway.
* @sa foreach
*/
struct map_node *_stp_map_start(MAP map)
{
if (map == NULL)
return NULL;
dbug ("%lx\n", (long)map->head.next);
if (list_empty(&map->head))
return NULL;
return (struct map_node *)map->head.next;
}
/** Get the next element in a map.
* @param map
* @param m a pointer to the current element, returned from _stp_map_start()
* or _stp_map_iter().
* @returns a pointer to the next element.
* This is typically used with _stp_map_start(). See the foreach() macro
* for typical usage. It probably does what you want anyway.
* @sa foreach
*/
struct map_node *_stp_map_iter(MAP map, struct map_node *m)
{
if (map == NULL)
return NULL;
dbug ("%lx next=%lx prev=%lx map->head.next=%lx\n", (long)m,
(long)m->lnode.next, (long)m->lnode.prev, (long)map->head.next);
if (m->lnode.next == &map->head)
return NULL;
return (struct map_node *)m->lnode.next;
}
/** Deletes a map.
* Deletes a map, freeing all memory in all elements. Normally done only when the module exits.
* @param map
*/
void _stp_map_del(MAP map)
{
if (map == NULL)
return;
if (!list_empty(&map->head)) {
struct map_node *ptr = (struct map_node *)map->head.next;
while (ptr && ptr != (struct map_node *)&map->head) {
map_free_strings(map, ptr);
ptr = (struct map_node *)ptr->lnode.next;
}
}
_stp_vfree(map->membuf);
_stp_vfree(map);
}
/********************** KEY FUNCTIONS *********************/
/** Set the map's key to two longs.
* This sets the current element based on a key of two strings. If the keys are
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key1 first key
* @param key2 second key
*/
void _stp_map_key_long_long(MAP map, long key1, long key2)
{
unsigned hv;
struct hlist_head *head;
struct hlist_node *e;
if (map == NULL)
return;
hv = hash_long(key1 ^ key2, HASH_TABLE_BITS);
head = &map->hashes[hv];
dbug ("hash for %ld,%ld is %d\n", key1, key2, hv);
hlist_for_each(e, head) {
struct map_node *n =
(struct map_node *)((long)e - sizeof(struct hlist_node));
dbug ("n =%lx key=%ld,%ld\n", (long)n, n->key1.val, n->key2.val);
if (key1 == n->key1.val && key2 == n->key2.val) {
map->key = n;
dbug ("saving key %lx\n", (long)map->key);
map->create = 0;
return;
}
}
map->c_key1.val = key1;
map->c_key2.val = key2;
map->c_key1type = LONG;
map->c_key2type = LONG;
map->c_keyhead = head;
map->create = 1;
}
/** Set the map's key to two strings.
* This sets the current element based on a key of two strings. If the keys are
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key1 first key
* @param key2 second key
*/
void _stp_map_key_str_str(MAP map, char *key1, char *key2)
{
unsigned hv;
struct hlist_head *head;
struct hlist_node *e;
if (map == NULL)
return;
if (key1 == NULL) {
map->key = NULL;
return;
}
hv = string_hash(key1, key2);
head = &map->hashes[hv];
dbug ("hash for %s,%s is %d\n", key1, key2, hv);
hlist_for_each(e, head) {
struct map_node *n =
(struct map_node *)((long)e - sizeof(struct hlist_node));
dbug ("e =%lx key=%s,%s\n", (long)e, n->key1.str,n->key2.str);
if (strcmp(key1, n->key1.str) == 0
&& (key2 == NULL || strcmp(key2, n->key2.str) == 0)) {
map->key = n;
dbug ("saving key %lx\n", (long)map->key);
map->create = 0;
return;
}
}
map->c_key1.str = key1;
map->c_key2.str = key2;
map->c_key1type = STR;
map->c_key2type = STR;
map->c_keyhead = head;
map->create = 1;
}
/** Set the map's key to a string and a long.
* This sets the current element based on a key of a string and a long. If the keys are
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key1 first key
* @param key2 second key
*/
void _stp_map_key_str_long(MAP map, char *key1, long key2)
{
unsigned hv;
struct hlist_head *head;
struct hlist_node *e;
if (map == NULL)
return;
if (key1 == NULL) {
map->key = NULL;
return;
}
hv = mixed_hash(key1, key2);
head = &map->hashes[hv];
dbug ("hash for %s,%ld is %d\n", key1, key2, hv);
hlist_for_each(e, head) {
struct map_node *n =
(struct map_node *)((long)e - sizeof(struct hlist_node));
dbug ("e =%lx key=%s,%ld\n", (long)e, n->key1.str,(long)n->key2.val);
if (strcmp(key1, n->key1.str) == 0 && key2 == n->key2.val) {
map->key = n;
dbug ("saving key %lx\n", (long)map->key);
map->create = 0;
return;
}
}
map->c_key1.str = key1;
map->c_key2.val = key2;
map->c_key1type = STR;
map->c_key2type = LONG;
map->c_keyhead = head;
map->create = 1;
}
/** Set the map's key to a long and a string.
* This sets the current element based on a key of a long and a string. If the keys are
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key1 first key
* @param key2 second key
*/
void _stp_map_key_long_str(MAP map, long key1, char *key2)
{
unsigned hv;
struct hlist_head *head;
struct hlist_node *e;
if (map == NULL)
return;
hv = mixed_hash(key2, key1);
head = &map->hashes[hv];
dbug ("hash for %ld,%s is %d\n", key1, key2, hv);
hlist_for_each(e, head) {
struct map_node *n =
(struct map_node *)((long)e - sizeof(struct hlist_node));
dbug ("e =%lx key=%ld,%s\n", (long)e, n->key1.val,n->key2.str);
if (key1 == n->key1.val && strcmp(key2, n->key2.str) == 0) {
map->key = n;
dbug ("saving key %lx\n", (long)map->key);
map->create = 0;
return;
}
}
map->c_key1.val = key1;
map->c_key2.str = key2;
map->c_key1type = LONG;
map->c_key2type = STR;
map->c_keyhead = head;
map->create = 1;
}
/** Set the map's key to a string.
* This sets the current element based on a string key. If the key is
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key
*/
void _stp_map_key_str(MAP map, char *key)
{
if (map == NULL)
return;
_stp_map_key_str_str(map, key, NULL);
map->c_key2type = NONE;
}
/** Set the map's key to a long.
* This sets the current element based on a long key. If the key is
* not found, a new element will not be created until a _stp_map_set_xxx
* call.
* @param map
* @param key
*/
void _stp_map_key_long(MAP map, long key)
{
if (map == NULL)
return;
_stp_map_key_long_long(map, key, 0);
map->c_key2type = NONE;
}
/********************** SET/GET VALUES *********************/
static void map_copy_keys(MAP map, struct map_node *m)
{
m->key1type = map->c_key1type;
m->key2type = map->c_key2type;
switch (map->c_key1type) {
case STR:
m->key1.str = _stp_alloc(strlen(map->c_key1.str) + 1);
strcpy(m->key1.str, map->c_key1.str);
break;
case LONG:
m->key1.val = map->c_key1.val;
break;
case NONE:
/* ERROR */
break;
}
switch (map->c_key2type) {
case STR:
m->key2.str = _stp_alloc(strlen(map->c_key2.str) + 1);
strcpy(m->key2.str, map->c_key2.str);
break;
case LONG:
m->key2.val = map->c_key2.val;
break;
case NONE:
break;
}
/* add node to new hash list */
hlist_add_head(&m->hnode, map->c_keyhead);
map->key = m;
map->create = 0;
map->num++;
}
static void __stp_map_set_int64(MAP map, int64_t val, int add)
{
struct map_node_int64 *m;
if (map == NULL)
return;
if (map->create) {
if (val == 0)
return;
if (map->maxnum) {
if (list_empty(&map->pool)) {
if (map->no_wrap) {
/* ERROR. FIXME */
return;
}
m = (struct map_node_int64 *)map->head.next;
hlist_del_init(&m->n.hnode);
map_free_strings(map, (struct map_node *)m);
dbug ("got %lx off head\n", (long)m);
} else {
m = (struct map_node_int64 *)map->pool.next;
dbug ("got %lx off pool\n", (long)m);
}
list_move_tail(&m->n.lnode, &map->head);
} else {
m = (struct map_node_int64 *)
_stp_calloc(sizeof(struct map_node_int64));
/* add node to list */
list_add_tail(&m->n.lnode, &map->head);
}
/* copy the key(s) */
map_copy_keys(map, &m->n);
/* set the value */
m->val = val;
} else {
if (map->key == NULL)
return;
if (val) {
m = (struct map_node_int64 *)map->key;
if (add)
m->val += val;
else
m->val = val;
} else if (!add) {
/* setting value to 0 is the same as deleting */
_stp_map_key_del(map);
}
}
}
/** Set the current element's value to an int64.
* This sets the current element's value to an int64. The map must have been created
* to hold int64s using _stp_map_new()
*
* If the element doesn't exist, it is created. If no current element (key)
* is set for the map, this function does nothing.
* @param map
* @param val new value
* @sa _stp_map_add_int64
*/
void _stp_map_set_int64(MAP map, int64_t val)
{
__stp_map_set_int64 (map, val, 0);
}
/** Adds an int64 to the current element's value.
* This adds an int64 to the current element's value. The map must have been created
* to hold int64s using _stp_map_new()
*
* If the element doesn't exist, it is created. If no current element (key)
* is set for the map, this function does nothing.
* @param map
* @param val value
* @sa _stp_map_set_int64
*/
void _stp_map_add_int64(MAP map, int64_t val)
{
__stp_map_set_int64 (map, val, 1);
}
/** Gets the current element's value.
* @param map
* @returns The value. If the current element is not set or doesn't exist, returns 0.
*/
int64_t _stp_map_get_int64(MAP map)
{
struct map_node_int64 *m;
if (map == NULL || map->create || map->key == NULL)
return 0;
dbug ("%lx\n", (long)map->key);
m = (struct map_node_int64 *)map->key;
return m->val;
}
/** Set the current element's value to a string.
* This sets the current element's value to an string. The map must have been created
* to hold int64s using _stp_map_new(xxx, STRING)
*
* If the element doesn't exist, it is created. If no current element (key)
* is set for the map, this function does nothing.
* @param map
* @param val new string
*/
void _stp_map_set_str(MAP map, char *val)
{
struct map_node_str *m;
if (map == NULL)
return;
if (map->create) {
if (val == NULL)
return;
if (map->maxnum) {
if (list_empty(&map->pool)) {
if (map->no_wrap) {
/* ERROR. FIXME */
return;
}
m = (struct map_node_str *)map->head.next;
hlist_del_init(&m->n.hnode);
map_free_strings(map, (struct map_node *)m);
dbug ("got %lx off head\n", (long)m);
} else {
m = (struct map_node_str *)map->pool.next;
dbug ("got %lx off pool\n", (long)m);
}
list_move_tail(&m->n.lnode, &map->head);
} else {
m = (struct map_node_str *)
_stp_calloc(sizeof(struct map_node_str));
/* add node to list */
list_add_tail(&m->n.lnode, &map->head);
}
/* copy the key(s) */
map_copy_keys(map, &m->n);
/* set the value */
m->str = _stp_alloc(strlen(val) + 1);
strcpy(m->str, val);
} else {
if (map->key == NULL)
return;
if (val) {
m = (struct map_node_str *)map->key;
if (m->str)
_stp_free(m->str);
m->str = _stp_alloc(strlen(val) + 1);
strcpy(m->str, val);
} else {
/* setting value to 0 is the same as deleting */
_stp_map_key_del(map);
}
}
}
/** Gets the current element's value.
* @param map
* @returns A string pointer. If the current element is not set or doesn't exist, returns NULL.
*/
char *_stp_map_get_str(MAP map)
{
struct map_node_str *m;
if (map == NULL || map->create || map->key == NULL)
return NULL;
dbug ("%lx\n", (long)map->key);
m = (struct map_node_str *)map->key;
return m->str;
}
/** Set the current element's value to a stat.
* This sets the current element's value to an stat struct. The map must have been created
* to hold stats using _stp_map_new(xxx, STAT). This function would only be used
* if we wanted to set stats to something other than the normal initial values (count = 0,
* sum = 0, etc). It may be deleted if it doesn't turn out to be useful.
* @sa _stp_map_stat_add
*
* If the element doesn't exist, it is created. If no current element (key)
* is set for the map, this function does nothing.
* @param map
* @param stats pointer to stats struct.
* @todo Histograms don't work yet.
*/
void _stp_map_set_stat(MAP map, stat * stats)
{
struct map_node_stat *m;
if (map == NULL)
return;
dbug ("set_stat %lx\n", (long)map->key);
if (map->create) {
if (stats == NULL)
return;
if (map->maxnum) {
if (list_empty(&map->pool)) {
if (map->no_wrap) {
/* ERROR. FIXME */
return;
}
m = (struct map_node_stat *)map->head.next;
hlist_del_init(&m->n.hnode);
map_free_strings(map, (struct map_node *)m);
dbug ("got %lx off head\n", (long)m);
} else {
m = (struct map_node_stat *)map->pool.next;
dbug ("got %lx off pool\n", (long)m);
}
list_move_tail(&m->n.lnode, &map->head);
} else {
m = (struct map_node_stat *)
_stp_calloc(sizeof(struct map_node_stat));
/* add node to list */
list_add_tail(&m->n.lnode, &map->head);
}
/* copy the key(s) */
map_copy_keys(map, &m->n);
/* set the value */
memcpy(&m->stats, stats, sizeof(stat));
} else {
if (map->key == NULL)
return;
if (stats) {
m = (struct map_node_stat *)map->key;
memcpy(&m->stats, stats, sizeof(stat));
} else {
/* setting value to NULL is the same as deleting */
_stp_map_key_del(map);
}
}
}
/** Gets the current element's value.
* @param map
* @returns A pointer to the stats struct. If the current element is not set
* or doesn't exist, returns NULL.
*/
stat *_stp_map_get_stat(MAP map)
{
struct map_node_stat *m;
if (map == NULL || map->create || map->key == NULL)
return NULL;
dbug ("%lx\n", (long)map->key);
m = (struct map_node_stat *)map->key;
return &m->stats;
}
/** Add to the current element's statistics.
* Increments the statistics counter by one and the sum by val.
* Adjusts minimum, maximum, and histogram.
*
* If the element doesn't exist, it is created. If no current element (key)
* is set for the map, this function does nothing.
* @param map
* @param val value to add to the statistics
* @todo Histograms don't work yet.
*/
void _stp_map_stat_add(MAP map, int64_t val)
{
struct map_node_stat *m;
if (map == NULL)
return;
if (map->create) {
stat st = { 1, val, val, val };
/* histogram */
_stp_map_set_stat(map, &st);
return;
}
if (map->key == NULL)
return;
dbug ("add_stat %lx\n", (long)map->key);
m = (struct map_node_stat *)map->key;
m->stats.count++;
m->stats.sum += val;
if (val > m->stats.max)
m->stats.max = val;
if (val < m->stats.min)
m->stats.min = val;
/* histogram */
}
/********************** List Functions *********************/
/** Create a new list.
* A list is a map that internally has an incrementing long key for each member.
* Lists do not wrap if elements are added to exceed their maximum size.
* @param max_entries The maximum number of entries allowed. Currently that number will
* be preallocated. If max_entries is 0, there will be no maximum and entries
* will be allocated dynamically.
* @param type Type of values stored in this list.
* @return A MAP on success or NULL on failure.
* @sa foreach
*/
MAP _stp_list_new(unsigned max_entries, enum valtype type)
{
MAP map = _stp_map_new (max_entries, type);
map->no_wrap = 1;
return map;
}
/** Clears a list.
* All elements in the list are deleted.
* @param map
*/
void _stp_list_clear(MAP map)
{
if (map == NULL)
return;
if (!list_empty(&map->head)) {
struct map_node *ptr = (struct map_node *)map->head.next;
while (ptr && ptr != (struct map_node *)&map->head) {
struct map_node *next = (struct map_node *)ptr->lnode.next;
/* remove node from old hash list */
hlist_del_init(&ptr->hnode);
/* remove from entry list */
list_del(&ptr->lnode);
/* remove any allocated string storage */
map_free_strings(map, ptr);
if (map->maxnum)
list_add(&ptr->lnode, &map->pool);
else
_stp_free(ptr);
map->num--;
ptr = next;
}
}
if (map->num != 0) {
dlog ("ERROR: list is supposed to be empty (has %d)\n", map->num);
}
}
/** Adds a string to a list.
* @param map
* @param str
*/
inline void _stp_list_add_str(MAP map, char *str)
{
_stp_map_key_long(map, map->num);
_stp_map_set_str(map, str);
}
/** Adds an int64 to a list.
* @param map
* @param val
*/
inline void _stp_list_add_int64(MAP map, int64_t val)
{
_stp_map_key_long(map, map->num);
_stp_map_set_int64(map, val);
}
/** Get the number of elements in a list.
* @param map
* @returns The number of elements in a list.
*/
inline int _stp_list_size(MAP map)
{
return map->num;
}