Initial runtime checkin.

1 files changed, 830 insertions, 0 deletions

diff --git a/runtime/map.c b/runtime/map.c
new file mode 100644
index 00000000..9b264c3a
--- /dev/null
+++ b/runtime/map.c
@@ -0,0 +1,830 @@
+/* -*- 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);
+}
+
+/** 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++;
+}
+
+/** 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
+ */
+
+void _stp_map_set_int64(MAP map, int64_t val)
+{
+	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;
+			m->val = 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 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 
+ */
+
+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);
+	}
+}
+
+/** 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;
+}