map.c

Go to the documentation of this file.

/* -*- linux-c -*- */

static int map_sizes[] = {
        sizeof(struct map_node_int64),
        sizeof(struct map_node_stat),
        sizeof(struct map_node_str),
        0
};

static inline 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 inline 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);
}

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

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--;
}

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;
}

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;
}

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 *********************/


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;
}

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;
}

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;
}

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;
}

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;
}

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

void _stp_map_set_int64(MAP map, int64_t val)
{
        __stp_map_set_int64 (map, val, 0);
}


void _stp_map_add_int64(MAP map, int64_t val)
{
        __stp_map_set_int64 (map, val, 1);
}

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;
}

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

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;
}

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

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;
}

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 *********************/

MAP _stp_list_new(unsigned max_entries, enum valtype type)
{
  MAP map = _stp_map_new (max_entries, type);
  map->no_wrap = 1;
  return map;
}

inline 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);
        }
}

inline void _stp_list_add_str(MAP map, char *str)
{
        _stp_map_key_long(map, map->num);
        _stp_map_set_str(map, str);
}

inline void _stp_list_add_int64(MAP map, int64_t val)
{
        _stp_map_key_long(map, map->num);
        _stp_map_set_int64(map, val);
}

inline int _stp_list_size(MAP map)
{
        return map->num;
}

---