/pidgin/main: b4a35c405e95: Trie: states allocation

Tomasz Wasilczyk twasilczyk at pidgin.im
Tue Mar 25 10:42:06 EDT 2014


Changeset: b4a35c405e9526f9a2ea3c5c961b5f2dc83490db
Author:	 Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date:	 2014-03-25 15:41 +0100
Branch:	 default
URL: https://hg.pidgin.im/pidgin/main/rev/b4a35c405e95

Description:

Trie: states allocation

diffstat:

 libpurple/memorypool.c |   49 +++++++++++++---
 libpurple/memorypool.h |   21 +++++++
 libpurple/trie.c       |  147 ++++++++++++++++++++++++++++++++++++++++++++++--
 3 files changed, 200 insertions(+), 17 deletions(-)

diffs (truncated from 321 to 300 lines):

diff --git a/libpurple/memorypool.c b/libpurple/memorypool.c
--- a/libpurple/memorypool.c
+++ b/libpurple/memorypool.c
@@ -137,6 +137,23 @@ purple_memory_pool_alloc_impl(PurpleMemo
 	return mem;
 }
 
+static void
+purple_memory_pool_cleanup_impl(PurpleMemoryPool *pool)
+{
+	PurpleMemoryPoolPrivate *priv = PURPLE_MEMORY_POOL_GET_PRIVATE(pool);
+	PurpleMemoryPoolBlock *blk;
+
+	g_return_if_fail(priv != NULL);
+
+	blk = priv->first_block;
+	while (blk) {
+		PurpleMemoryPoolBlock *next = blk->next;
+		g_free(blk);
+		blk = next;
+	}
+}
+
+
 /*******************************************************************************
  * API implementation
  ******************************************************************************/
@@ -191,6 +208,19 @@ purple_memory_pool_free(PurpleMemoryPool
 		klass->pfree(pool, mem);
 }
 
+void
+purple_memory_pool_cleanup(PurpleMemoryPool *pool)
+{
+	PurpleMemoryPoolClass *klass;
+
+	g_return_if_fail(PURPLE_IS_MEMORY_POOL(pool));
+
+	klass = PURPLE_MEMORY_POOL_GET_CLASS(pool);
+	g_return_if_fail(klass != NULL);
+
+	klass->cleanup(pool);
+}
+
 
 /*******************************************************************************
  * Object stuff
@@ -212,18 +242,18 @@ purple_memory_pool_new(void)
 	return g_object_new(PURPLE_TYPE_MEMORY_POOL, NULL);
 }
 
+PurpleMemoryPool *
+purple_memory_pool_new_sized(gulong block_size)
+{
+	return g_object_new(PURPLE_TYPE_MEMORY_POOL,
+		"block-size", block_size,
+		NULL);
+}
+
 static void
 purple_memory_pool_finalize(GObject *obj)
 {
-	PurpleMemoryPoolPrivate *priv = PURPLE_MEMORY_POOL_GET_PRIVATE(obj);
-	PurpleMemoryPoolBlock *blk;
-
-	blk = priv->first_block;
-	while (blk) {
-		PurpleMemoryPoolBlock *next = blk->next;
-		g_free(blk);
-		blk = next;
-	}
+	purple_memory_pool_cleanup(PURPLE_MEMORY_POOL(obj));
 
 	G_OBJECT_CLASS(parent_class)->finalize(obj);
 }
@@ -274,6 +304,7 @@ purple_memory_pool_class_init(PurpleMemo
 	obj_class->set_property = purple_memory_pool_set_property;
 
 	klass->palloc = purple_memory_pool_alloc_impl;
+	klass->cleanup = purple_memory_pool_cleanup_impl;
 
 	properties[PROP_BLOCK_SIZE] = g_param_spec_ulong("block-size",
 		"Block size", "The default size of each block of pool memory.",
diff --git a/libpurple/memorypool.h b/libpurple/memorypool.h
--- a/libpurple/memorypool.h
+++ b/libpurple/memorypool.h
@@ -53,6 +53,7 @@ struct _PurpleMemoryPoolClass
 
 	gpointer (*palloc)(PurpleMemoryPool *pool, gsize size, guint alignment);
 	gpointer (*pfree)(PurpleMemoryPool *pool, gpointer mem);
+	void (*cleanup)(PurpleMemoryPool *pool);
 
 	void (*purple_reserved1)(void);
 	void (*purple_reserved2)(void);
@@ -76,6 +77,16 @@ PurpleMemoryPool *
 purple_memory_pool_new(void);
 
 /**
+ * purple_memory_pool_new_sized:
+ *
+ * Creates a new memory pool with non-default block size.
+ *
+ * Returns: The new #PurpleMemoryPool.
+ */
+PurpleMemoryPool *
+purple_memory_pool_new_sized(gulong block_size);
+
+/**
  * purple_memory_pool_alloc:
  * @pool: The memory pool.
  * @size: The size of memory to be allocated.
@@ -116,6 +127,16 @@ void
 purple_memory_pool_free(PurpleMemoryPool *pool, gpointer mem);
 
 /**
+ * purple_memory_pool_cleanup:
+ * @pool: The memory pool.
+ *
+ * Marks all memory allocated within a memory pool as not used. It may free
+ * resources, but don't have to.
+ */
+void
+purple_memory_pool_cleanup(PurpleMemoryPool *pool);
+
+/**
  * purple_memory_pool_strdup:
  * @pool: The memory pool.
  * @str: The string to duplicate.
diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -27,14 +27,22 @@
 #define PURPLE_TRIE_GET_PRIVATE(obj) \
 	(G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
 
+#define PURPLE_TRIE_STATES_POOL_BLOCK_SIZE 102400
+
 typedef struct _PurpleTrieRecord PurpleTrieRecord;
+typedef struct _PurpleTrieState PurpleTrieState;
+typedef struct _PurpleTrieRecordList PurpleTrieRecordList;
 
 typedef struct
 {
 	gboolean reset_on_match;
 
-	PurpleMemoryPool *records_mempool;
-	GSList *records;
+	PurpleMemoryPool *records_str_mempool;
+	PurpleMemoryPool *records_obj_mempool;
+	PurpleTrieRecordList *records;
+
+	PurpleMemoryPool *states_mempool;
+	PurpleTrieState *root_state;
 } PurpleTriePrivate;
 
 struct _PurpleTrieRecord
@@ -43,6 +51,115 @@ struct _PurpleTrieRecord
 	gpointer data;
 };
 
+struct _PurpleTrieRecordList
+{
+	PurpleTrieRecord *rec;
+	PurpleTrieRecordList *next;
+	PurpleTrieRecordList *prev;
+};
+
+struct _PurpleTrieState
+{
+	PurpleTrieState *parent;
+	PurpleTrieState **children;
+
+	PurpleTrieState *longest_suffix;
+
+	PurpleTrieRecord *found_word;
+};
+
+/*******************************************************************************
+ * Records list
+ ******************************************************************************/
+
+static PurpleTrieRecordList *
+purple_record_list_prepend(PurpleMemoryPool *mpool,
+	PurpleTrieRecordList *old_head, PurpleTrieRecord *rec)
+{
+	PurpleTrieRecordList *new_head;
+
+	new_head = purple_memory_pool_alloc(mpool,
+		sizeof(PurpleTrieRecordList), sizeof(gpointer));
+	new_head->rec = rec;
+	new_head->next = old_head;
+	old_head->prev = new_head;
+	new_head->prev = NULL;
+
+	return new_head;
+}
+
+/*******************************************************************************
+ * States management
+ ******************************************************************************/
+
+static void
+purple_trie_states_cleanup(PurpleTrie *trie)
+{
+	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+
+	g_return_if_fail(priv != NULL);
+
+	if (priv->root_state != NULL) {
+		purple_memory_pool_cleanup(priv->states_mempool);
+		priv->root_state = NULL;
+	}
+}
+
+/* Allocates a state and binds it to the parent. */
+static PurpleTrieState *
+purple_trie_state_new(PurpleTrie *trie, PurpleTrieState *parent, guchar letter)
+{
+	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+	PurpleTrieState *state;
+
+	g_return_val_if_fail(priv != NULL, NULL);
+
+	state = purple_memory_pool_alloc0(priv->states_mempool,
+		sizeof(PurpleTrieState), sizeof(gpointer));
+	g_return_val_if_fail(state != NULL, NULL);
+
+	if (parent == NULL)
+		return state;
+
+	state->parent = parent;
+	if (parent->children == NULL) {
+		parent->children = purple_memory_pool_alloc0(
+			priv->states_mempool,
+			/* PurpleTrieState *children[sizeof(guchar)] */
+			sizeof(guchar) * sizeof(gpointer),
+			sizeof(gpointer));
+	}
+
+	if (parent->children == NULL) {
+		purple_memory_pool_free(priv->states_mempool, state);
+		g_warn_if_reached();
+		return NULL;
+	}
+
+	parent->children[letter] = state;
+
+	return state;
+}
+
+static gboolean
+purple_trie_states_build(PurpleTrie *trie)
+{
+	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+	PurpleTrieState *root;
+
+	g_return_val_if_fail(priv != NULL, FALSE);
+
+	if (priv->root_state != NULL)
+		return TRUE;
+
+	priv->root_state = root = purple_trie_state_new(trie, NULL, '\0');
+	g_return_val_if_fail(root != NULL, FALSE);
+
+	/* XXX: TODO */
+
+	return TRUE;
+}
+
 /*******************************************************************************
  * Records
  ******************************************************************************/
@@ -56,11 +173,21 @@ purple_trie_add(PurpleTrie *trie, const 
 	g_return_if_fail(priv != NULL);
 	g_return_if_fail(word != NULL);
 
-	rec = g_new(PurpleTrieRecord, 1);
-	rec->word = purple_memory_pool_strdup(priv->records_mempool, word);
+	/* Every change in a trie invalidates longest_suffix map.
+	 * These prefixes could be updated instead of cleaning the whole graph.
+	 */
+	purple_trie_states_cleanup(trie);
+
+	rec = purple_memory_pool_alloc(priv->records_obj_mempool,
+		sizeof(PurpleTrieRecord), sizeof(gpointer));
+	rec->word = purple_memory_pool_strdup(priv->records_str_mempool, word);
 	rec->data = data;
 
-	priv->records = g_slist_prepend(priv->records, rec);
+	priv->records = purple_record_list_prepend(priv->records_obj_mempool,
+		priv->records, rec);
+
+	/* XXX: it won't be called here (it's inefficient), but in search function */
+	purple_trie_states_build(trie);
 }
 
 /*******************************************************************************
@@ -113,7 +240,10 @@ purple_trie_init(GTypeInstance *instance
 	PurpleTrie *trie = PURPLE_TRIE(instance);
 	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);



More information about the Commits mailing list