libpurple/trie.h

   1 /*
   2  * Purple
   3  *
   4  * Purple is the legal property of its developers, whose names are too
   5  * numerous to list here. Please refer to the COPYRIGHT file distributed
   6  * with this source distribution
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or (at
  11  * your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16  * General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA
  21  */
  22
  23 #ifndef PURPLE_TRIE_H
  24 #define PURPLE_TRIE_H
  25 /**
  26  * SECTION:trie
  27  * @include:trie.h
  28  * @section_id: libpurple-trie
  29  * @short_description: a structure for linear-time text searching
  30  * @title: Tries
  31  *
  32  * A #PurpleTrie is a structure for quick searching of multiple phrases within
  33  * a text. It's intended for repeated searches of the same set of patterns
  34  * within multiple source texts (or a single, big one).
  35  *
  36  * It's preparation time is <literal>O(p)</literal>, where <literal>p</literal>
  37  * is the total length of searched phrases. In current implementation, the
  38  * internal structure is invalidated after every modification of the
  39  * #PurpleTrie's contents, so it's not efficient to do alternating modifications
  40  * and searches. Search time does not depend on patterns being stored within
  41  * a trie and is always <literal>O(n)</literal>, where <literal>n</literal> is
  42  * the size of a text.
  43  *
  44  * Its main drawback is a significant memory usage - every internal trie node
  45  * needs about 1kB of memory on 32-bit machine and 2kB on 64-bit. Fortunately,
  46  * the trie grows slower when more words (with common prefixes) are added.
  47  * We could avoid invalidating the whole tree when altering it, but it would
  48  * require figuring out, how to update <literal>longest_suffix</literal> fields
  49  * in satisfying time.
  50  */
  51
  52 #include <glib-object.h>
  53
  54 #define PURPLE_TYPE_TRIE  purple_trie_get_type()
  55
  56 /**
  57  * PurpleTrieReplaceCb:
  58  * @out: currently built output string, append replacement to it.
  59  * @word: found word.
  60  * @word_data: the user data bound with this word, when added with
  61  *             #purple_trie_add.
  62  * @user_data: the user supplied data passed when calling #purple_trie_replace.
  63  *
  64  * A funtion called on every matching substring to be replaced.
  65  *
  66  * If you decide to replace the word, append your text to @out and return %TRUE.
  67  * Otherwise, you must not touch @out. In both cases, you must not do any
  68  * operations on @out other than appending text to it.
  69  *
  70  * Returns: %TRUE if the word was replaced, %FALSE otherwise.
  71  */
  72 typedef gboolean (*PurpleTrieReplaceCb)(GString *out, const gchar *word,
  73         gpointer word_data, gpointer user_data);
  74
  75 /**
  76  * PurpleTrieFindCb:
  77  * @word: found word.
  78  * @word_data: the user data bound with this word, when added with
  79  *             #purple_trie_add.
  80  * @user_data: the user data passed when calling #purple_trie_find.
  81  *
  82  * A function called on every matching substring.
  83  *
  84  * You can decide to count the match or not (for the total number of found
  85  * words, that is returned by #purple_trie_find). In both cases you can
  86  * obviously do some processing outside the #PurpleTrie object.
  87  *
  88  * If you decide to count the word and #PurpleTrie:reset-on-match property
  89  * is set, no overlapping words will be found - the processing will skip after
  90  * the end of this word.
  91  *
  92  * Returns: %TRUE if the word should be counter, %FALSE otherwise.
  93  */
  94 typedef gboolean (*PurpleTrieFindCb)(const gchar *word, gpointer word_data,
  95         gpointer user_data);
  96
  97 G_BEGIN_DECLS
  98
  99 /**
 100  * purple_trie_get_type:
 101  *
 102  * Returns: the #GType for a #PurpleTrie.
 103  */
 104 G_DECLARE_FINAL_TYPE(PurpleTrie, purple_trie, PURPLE, TRIE, GObject)
 105
 106 /**
 107  * purple_trie_new:
 108  *
 109  * Creates a new trie.
 110  *
 111  * Returns: the new #PurpleTrie.
 112  */
 113 PurpleTrie *
 114 purple_trie_new(void);
 115
 116 /**
 117  * purple_trie_get_reset_on_match:
 118  * @trie: the trie.
 119  *
 120  * Checks, if the trie will reset its internal state after every match.
 121  *
 122  * Returns: %TRUE, if trie will reset, %FALSE otherwise.
 123  */
 124 gboolean
 125 purple_trie_get_reset_on_match(PurpleTrie *trie);
 126
 127 /**
 128  * purple_trie_set_reset_on_match:
 129  * @trie: the trie.
 130  * @reset: %TRUE, if trie should reset, %FALSE otherwise.
 131  *
 132  * Enables or disables a feature of resetting trie's state after every match.
 133  * When enabled, it will not search for overlapping matches.
 134  *
 135  * It's well defined for #purple_trie_find, but not for replace operations.
 136  * Thus, for the latter, it's better to stay with this option enabled, because
 137  * its behavior may be changed in future.
 138  */
 139 void
 140 purple_trie_set_reset_on_match(PurpleTrie *trie, gboolean reset);
 141
 142 /**
 143  * purple_trie_add:
 144  * @trie: the trie.
 145  * @word: the word.
 146  * @data: the word-related data (may be %NULL).
 147  *
 148  * Adds a word to the trie. Current implementation doesn't allow for duplicates,
 149  * so please avoid adding those.
 150  *
 151  * Please note, that altering a trie invalidates its internal structure, so by
 152  * the occasion of next search, it will be rebuilt. It's done in
 153  * <literal>O(n)</literal>, where n is the total length of strings
 154  * in #PurpleTrie.
 155  *
 156  * Returns: %TRUE if succeeded, %FALSE otherwise.
 157  */
 158 gboolean
 159 purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data);
 160
 161 /**
 162  * purple_trie_remove:
 163  * @trie: the trie.
 164  * @word: the word.
 165  *
 166  * Removes a word from the trie. Depending on used memory pool, this may not
 167  * free allocated memory (that will be freed when destroying the whole
 168  * collection), so use it wisely. See #purple_memory_pool_free.
 169  *
 170  * Please note, that altering a trie invalidates its internal structure.
 171  * See #purple_trie_add.
 172  */
 173 void
 174 purple_trie_remove(PurpleTrie *trie, const gchar *word);
 175
 176 /**
 177  * purple_trie_get_size:
 178  * @trie: the trie.
 179  *
 180  * Returns the number of elements contained in the #PurpleTrie.
 181  *
 182  * Returns: the number of stored words in @trie.
 183  */
 184 guint
 185 purple_trie_get_size(PurpleTrie *trie);
 186
 187 /**
 188  * purple_trie_replace:
 189  * @trie: the trie.
 190  * @src: the source string.
 191  * @replace_cb: (scope call): the replacement function.
 192  * @user_data: custom data to be passed to @replace_cb.
 193  *
 194  * Processes @src string and replaces all occuriences of words added to @trie.
 195  * It's <literal>O(strlen(src))</literal>, if @replace_cb runs in
 196  * <literal>O(strlen(word))</literal> and #PurpleTrie:reset-on-match is set.
 197  *
 198  * Returns: resulting string. Must be #g_free'd when you are done using it.
 199  */
 200 gchar *
 201 purple_trie_replace(PurpleTrie *trie, const gchar *src,
 202         PurpleTrieReplaceCb replace_cb, gpointer user_data);
 203
 204 /**
 205  * purple_trie_multi_replace:
 206  * @tries: (element-type PurpleTrie): the list of tries.
 207  * @src: the source string.
 208  * @replace_cb: (scope call): the replacement function.
 209  * @user_data: custom data to be passed to @replace_cb.
 210  *
 211  * Processes @src and replaces all occuriences of words added to tries in list
 212  * @tries. Entries added to tries on the beginning of the list have higher
 213  * priority, than ones added further.
 214  *
 215  * Different #GSList's can be combined to possess common parts, so you can create
 216  * a "tree of tries".
 217  *
 218  * Returns: resulting string. Must be #g_free'd when you are done using it.
 219  */
 220 gchar *
 221 purple_trie_multi_replace(const GSList *tries, const gchar *src,
 222         PurpleTrieReplaceCb replace_cb, gpointer user_data);
 223
 224 /**
 225  * purple_trie_find:
 226  * @trie: the trie.
 227  * @src: the source string.
 228  * @find_cb: (nullable) (scope call): the callback for the found entries (may be %NULL).
 229  * @user_data: custom data to be passed to @find_cb.
 230  *
 231  * Processes @src string and finds all occuriences of words added to @trie.
 232  * It's <literal>O(strlen(src))</literal>, if find_cb runs
 233  * in <literal>O(1)</literal>.
 234  *
 235  * The word is counted as found if it's found and the callback returns %TRUE.
 236  *
 237  * Returns: the number of found words.
 238  */
 239 gulong
 240 purple_trie_find(PurpleTrie *trie, const gchar *src,
 241         PurpleTrieFindCb find_cb, gpointer user_data);
 242
 243 /**
 244  * purple_trie_multi_find:
 245  * @tries: (element-type PurpleTrie): the list of tries.
 246  * @src: the source string.
 247  * @find_cb: (nullable) (scope call): the callback for the found entries (may be %NULL).
 248  * @user_data: custom data to be passed to @find_cb.
 249  *
 250  * Processes @src and replaces all occuriences of words added to tries in
 251  * list @tries. Entries added to tries on the beginning of the list have higher
 252  * priority, than ones added further.
 253  *
 254  * Different #GSList's can be combined to possess common parts, so you can create
 255  * a "tree of tries".
 256  *
 257  * Returns: the number of found words.
 258  */
 259 gulong
 260 purple_trie_multi_find(const GSList *tries, const gchar *src,
 261         PurpleTrieFindCb find_cb, gpointer user_data);
 262
 263 G_END_DECLS
 264
 265 #endif /* PURPLE_MEMORY_POOL_H */