map.c

Go to the documentation of this file.

/* -*- 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_set_xxx</i>
 * 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 <i>_stp_map_new(xxx, STRING)</i>
 *
 * 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 <i>_stp_map_new(xxx, STAT)</i>.  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 <i>val</i>.
 * 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;
}

---