pidgin/pidgin

Initial trie class implementation

2014-03-25, Tomasz Wasilczyk
95f34a3f4172
Parents eff51bb998b0
Children 1dc7369ff9f9
Initial trie class implementation
5 files changed, 365 insertions(+), 2 deletions(-)
  • +2 -0
    libpurple/Makefile.am
  • +21 -0
    libpurple/memorypool.c
  • +16 -2
    libpurple/memorypool.h
  • +216 -0
    libpurple/trie.c
  • +110 -0
    libpurple/trie.h
    • --- a/libpurple/Makefile.am Sat Mar 22 17:59:35 2014 +0100
    +++ b/libpurple/Makefile.am Tue Mar 25 14:19:13 2014 +0100
    @@ -114,6 +114,7 @@
    theme.c \
    theme-loader.c \
    theme-manager.c \
    + trie.c \
    upnp.c \
    util.c \
    version.c \
    @@ -188,6 +189,7 @@
    theme.h \
    theme-loader.h \
    theme-manager.h \
    + trie.h \
    upnp.h \
    util.h \
    whiteboard.h \
    --- a/libpurple/memorypool.c Sat Mar 22 17:59:35 2014 +0100
    +++ b/libpurple/memorypool.c Tue Mar 25 14:19:13 2014 +0100
    @@ -293,3 +293,24 @@
    return type;
    }
    +
    +gchar *
    +purple_memory_pool_strdup(PurpleMemoryPool *pool, const gchar *str)
    +{
    + gsize str_len;
    + gchar *str_dup;
    +
    + if (str == NULL)
    + return NULL;
    +
    + g_return_val_if_fail(PURPLE_IS_MEMORY_POOL(pool), NULL);
    +
    + str_len = strlen(str);
    + str_dup = purple_memory_pool_alloc(pool, str_len + 1, sizeof(gchar));
    + g_return_val_if_fail(str_dup != NULL, NULL);
    +
    + memcpy(str_dup, str, str_len);
    + str_dup[str_len] = '\0';
    +
    + return str_dup;
    +}
    --- a/libpurple/memorypool.h Sat Mar 22 17:59:35 2014 +0100
    +++ b/libpurple/memorypool.h Tue Mar 25 14:19:13 2014 +0100
    @@ -72,7 +72,7 @@
    *
    * Creates a new memory pool.
    *
    - * Returns: The new PurpleMemoryPool.
    + * Returns: The new #PurpleMemoryPool.
    */
    PurpleMemoryPool *
    purple_memory_pool_new(gulong block_size);
    @@ -112,11 +112,25 @@
    * @mem: The pointer to a memory block.
    *
    * Frees a memory allocated within a memory pool. This can be a no-op in certain
    - * implementations.
    + * implementations. Thus, it don't need to be called in every case.
    */
    void
    purple_memory_pool_free(PurpleMemoryPool *pool, gpointer mem);
    +/**
    + * purple_memory_pool_strdup:
    + * @pool: The memory pool.
    + * @str: The string to duplicate.
    + *
    + * Duplicates a string using a memory allocated within a memory pool. If @str is
    + * %NULL it returns %NULL. The returned string should be freed with g_free()
    + * when no longer needed.
    + *
    + * Returns: a newly-allocated copy of @str
    + */
    +gchar *
    +purple_memory_pool_strdup(PurpleMemoryPool *pool, const gchar *str);
    +
    G_END_DECLS
    #endif /* PURPLE_MEMORY_POOL_H */
    --- /dev/null Thu Jan 01 00:00:00 1970 +0000
    +++ b/libpurple/trie.c Tue Mar 25 14:19:13 2014 +0100
    @@ -0,0 +1,216 @@
    +/*
    + * Purple
    + *
    + * Purple is the legal property of its developers, whose names are too
    + * numerous to list here. Please refer to the COPYRIGHT file distributed
    + * with this source distribution
    + *
    + * This program is free software; you can redistribute it and/or modify
    + * it under the terms of the GNU General Public License as published by
    + * the Free Software Foundation; either version 2 of the License, or (at
    + * your option) any later version.
    + *
    + * This program is distributed in the hope that it will be useful, but
    + * WITHOUT ANY WARRANTY; without even the implied warranty of
    + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    + * General Public License for more details.
    + *
    + * You should have received a copy of the GNU General Public License
    + * along with this program; if not, write to the Free Software
    + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA
    + */
    +
    +#include "trie.h"
    +
    +#include "memorypool.h"
    +
    +#define PURPLE_TRIE_GET_PRIVATE(obj) \
    + (G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
    +
    +typedef struct _PurpleTrieRecord PurpleTrieRecord;
    +
    +typedef struct
    +{
    + gboolean reset_on_match;
    + gulong block_size;
    +
    + PurpleMemoryPool *records_mempool;
    + GSList *records;
    +} PurpleTriePrivate;
    +
    +struct _PurpleTrieRecord
    +{
    + const gchar *word;
    + gpointer data;
    +};
    +
    +/*******************************************************************************
    + * Records
    + ******************************************************************************/
    +
    +void
    +purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data)
    +{
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    + PurpleTrieRecord *rec;
    +
    + 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);
    + rec->data = data;
    +
    + priv->records = g_slist_prepend(priv->records, rec);
    +}
    +
    +/*******************************************************************************
    + * API implementation
    + ******************************************************************************/
    +
    +gboolean
    +purple_trie_get_reset_on_match(PurpleTrie *trie)
    +{
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    +
    + g_return_val_if_fail(priv, FALSE);
    +
    + return priv->reset_on_match;
    +}
    +
    +void
    +purple_trie_set_reset_on_match(PurpleTrie *trie, gboolean reset)
    +{
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    +
    + g_return_if_fail(priv);
    +
    + priv->reset_on_match = reset;
    +}
    +
    +/*******************************************************************************
    + * Object stuff
    + ******************************************************************************/
    +
    +enum
    +{
    + PROP_ZERO,
    + PROP_RESET_ON_MATCH,
    + PROP_BLOCK_SIZE,
    + PROP_LAST
    +};
    +
    +static GObjectClass *parent_class = NULL;
    +static GParamSpec *properties[PROP_LAST];
    +
    +PurpleTrie *
    +purple_trie_new(void)
    +{
    + return g_object_new(PURPLE_TYPE_TRIE, NULL);
    +}
    +
    +static void
    +purple_trie_init(GTypeInstance *instance, gpointer klass)
    +{
    + PurpleTrie *trie = PURPLE_TRIE(instance);
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    +
    + priv->records_mempool = purple_memory_pool_new(priv->block_size);
    +}
    +
    +static void
    +purple_trie_finalize(GObject *obj)
    +{
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(obj);
    +
    + g_slist_free_full(priv->records, g_free);
    + g_object_unref(priv->records_mempool);
    +
    + G_OBJECT_CLASS(parent_class)->finalize(obj);
    +}
    +
    +static void
    +purple_trie_get_property(GObject *obj, guint param_id, GValue *value,
    + GParamSpec *pspec)
    +{
    + PurpleTrie *trie = PURPLE_TRIE(obj);
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    +
    + switch (param_id) {
    + case PROP_RESET_ON_MATCH:
    + g_value_set_boolean(value, priv->reset_on_match);
    + break;
    + case PROP_BLOCK_SIZE:
    + g_value_set_ulong(value, priv->block_size);
    + break;
    + default:
    + G_OBJECT_WARN_INVALID_PROPERTY_ID(obj, param_id, pspec);
    + }
    +}
    +
    +static void
    +purple_trie_set_property(GObject *obj, guint param_id,
    + const GValue *value, GParamSpec *pspec)
    +{
    + PurpleTrie *trie = PURPLE_TRIE(obj);
    + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
    +
    + switch (param_id) {
    + case PROP_RESET_ON_MATCH:
    + priv->reset_on_match = g_value_get_boolean(value);
    + break;
    + case PROP_BLOCK_SIZE:
    + priv->block_size = g_value_get_ulong(value);
    + break;
    + default:
    + G_OBJECT_WARN_INVALID_PROPERTY_ID(obj, param_id, pspec);
    + }
    +}
    +
    +static void
    +purple_trie_class_init(PurpleTrieClass *klass)
    +{
    + GObjectClass *obj_class = G_OBJECT_CLASS(klass);
    +
    + parent_class = g_type_class_peek_parent(klass);
    +
    + g_type_class_add_private(klass, sizeof(PurpleTriePrivate));
    +
    + obj_class->finalize = purple_trie_finalize;
    + obj_class->get_property = purple_trie_get_property;
    + obj_class->set_property = purple_trie_set_property;
    +
    + properties[PROP_RESET_ON_MATCH] = g_param_spec_boolean("reset-on-match",
    + "Reset on match", "Determines, if the search state machine "
    + "should be reset to the initial state on every match. This "
    + "ensures, that every match is distinct from each other.", TRUE,
    + G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS);
    +
    + properties[PROP_BLOCK_SIZE] = g_param_spec_ulong("block-size",
    + "Block size", "The size of each block of pool memory. Every "
    + "string in trie have to be smaller than this value",
    + 1, G_MAXULONG, 1024,
    + G_PARAM_READWRITE | G_PARAM_CONSTRUCT | G_PARAM_STATIC_STRINGS);
    +
    + g_object_class_install_properties(obj_class, PROP_LAST, properties);
    +}
    +
    +GType
    +purple_trie_get_type(void)
    +{
    + static GType type = 0;
    +
    + if (G_UNLIKELY(type == 0)) {
    + static const GTypeInfo info = {
    + .class_size = sizeof(PurpleTrieClass),
    + .class_init = (GClassInitFunc)purple_trie_class_init,
    + .instance_size = sizeof(PurpleTrie),
    + .instance_init = purple_trie_init,
    + };
    +
    + type = g_type_register_static(G_TYPE_OBJECT,
    + "PurpleTrie", &info, 0);
    + }
    +
    + return type;
    +}
    --- /dev/null Thu Jan 01 00:00:00 1970 +0000
    +++ b/libpurple/trie.h Tue Mar 25 14:19:13 2014 +0100
    @@ -0,0 +1,110 @@
    +/*
    + * Purple
    + *
    + * Purple is the legal property of its developers, whose names are too
    + * numerous to list here. Please refer to the COPYRIGHT file distributed
    + * with this source distribution
    + *
    + * This program is free software; you can redistribute it and/or modify
    + * it under the terms of the GNU General Public License as published by
    + * the Free Software Foundation; either version 2 of the License, or (at
    + * your option) any later version.
    + *
    + * This program is distributed in the hope that it will be useful, but
    + * WITHOUT ANY WARRANTY; without even the implied warranty of
    + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    + * General Public License for more details.
    + *
    + * You should have received a copy of the GNU General Public License
    + * along with this program; if not, write to the Free Software
    + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA
    + */
    +
    +#ifndef PURPLE_TRIE_H
    +#define PURPLE_TRIE_H
    +
    +#include <glib-object.h>
    +
    +#define PURPLE_TYPE_TRIE (purple_trie_get_type())
    +#define PURPLE_TRIE(obj) \
    + (G_TYPE_CHECK_INSTANCE_CAST((obj), PURPLE_TYPE_TRIE, PurpleTrie))
    +#define PURPLE_TRIE_CLASS(klass) \
    + (G_TYPE_CHECK_CLASS_CAST((klass), PURPLE_TYPE_TRIE, PurpleTrieClass))
    +#define PURPLE_IS_TRIE(obj) \
    + (G_TYPE_CHECK_INSTANCE_TYPE((obj), PURPLE_TYPE_TRIE))
    +#define PURPLE_IS_TRIE_CLASS(klass) \
    + (G_TYPE_CHECK_CLASS_TYPE((klass), PURPLE_TYPE_TRIE))
    +#define PURPLE_TRIE_GET_CLASS(obj) \
    + (G_TYPE_INSTANCE_GET_CLASS((obj), PURPLE_TYPE_TRIE, PurpleTrieClass))
    +
    +typedef struct _PurpleTrie PurpleTrie;
    +typedef struct _PurpleTrieClass PurpleTrieClass;
    +
    +struct _PurpleTrie
    +{
    + /*< private >*/
    + GObject parent_instance;
    +};
    +
    +struct _PurpleTrieClass
    +{
    + /*< private >*/
    + GObjectClass parent_class;
    +
    + void (*purple_reserved1)(void);
    + void (*purple_reserved2)(void);
    + void (*purple_reserved3)(void);
    + void (*purple_reserved4)(void);
    +};
    +
    +G_BEGIN_DECLS
    +
    +GType
    +purple_trie_get_type(void);
    +
    +/**
    + * purple_trie_new:
    + *
    + * Creates a new trie.
    + *
    + * Returns: The new #PurpleTrie.
    + */
    +PurpleTrie *
    +purple_trie_new(void);
    +
    +/**
    + * purple_trie_get_reset_on_match:
    + * @trie: The trie.
    + *
    + * Checks, if the trie will reset its internal state after every match.
    + *
    + * Returns: %TRUE, if trie will reset, %FALSE otherwise.
    + */
    +gboolean
    +purple_trie_get_reset_on_match(PurpleTrie *trie);
    +
    +/**
    + * purple_trie_set_reset_on_match:
    + * @trie: The trie.
    + * @reset: %TRUE, if trie should reset, %FALSE otherwise.
    + *
    + * Enables or disables a feature of resetting trie's state after every match.
    + * When enabled, it will not search for overlapping matches.
    + */
    +void
    +purple_trie_set_reset_on_match(PurpleTrie *trie, gboolean reset);
    +
    +/**
    + * purple_trie_add:
    + * @trie: The trie.
    + * @word: The word.
    + * @data: The word-related data (may be %NULL).
    + *
    + * Adds a word to the trie.
    + */
    +void
    +purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data);
    +
    +G_END_DECLS
    +
    +#endif /* PURPLE_MEMORY_POOL_H */