libpurple/trie.c

   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 #include "trie.h"
  24
  25 #include <string.h>
  26
  27 #include "debug.h"
  28 #include "memorypool.h"
  29
  30 #define PURPLE_TRIE_GET_PRIVATE(obj) \
  31         (G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
  32
  33 /* A single internal (that don't have any children) consists
  34  * of 256 + 4 pointers. That's 1040 bytes on 32-bit machine or 2080 bytes
  35  * on 64-bit.
  36  *
  37  * Thus, in 10500-byte pool block we can hold about 5-10 internal states.
  38  * Threshold of 100 states means, we'd need 10-20 "small" blocks before
  39  * switching to ~1-2 large blocks.
  40  */
  41 #define PURPLE_TRIE_LARGE_THRESHOLD 100
  42 #define PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE 10880
  43 #define PURPLE_TRIE_STATES_LARGE_POOL_BLOCK_SIZE 102400
  44
  45 typedef struct _PurpleTrieRecord PurpleTrieRecord;
  46 typedef struct _PurpleTrieState PurpleTrieState;
  47 typedef struct _PurpleTrieRecordList PurpleTrieRecordList;
  48
  49 typedef struct
  50 {
  51         gboolean reset_on_match;
  52
  53         PurpleMemoryPool *records_str_mempool;
  54         PurpleMemoryPool *records_obj_mempool;
  55         PurpleTrieRecordList *records;
  56         GHashTable *records_map;
  57         gsize records_total_size;
  58
  59         PurpleMemoryPool *states_mempool;
  60         PurpleTrieState *root_state;
  61 } PurpleTriePrivate;
  62
  63 struct _PurpleTrieRecord
  64 {
  65         gchar *word;
  66         guint word_len;
  67         gpointer data;
  68 };
  69
  70 struct _PurpleTrieRecordList
  71 {
  72         PurpleTrieRecord *rec;
  73         PurpleTrieRecordList *next;
  74         PurpleTrieRecordList *prev;
  75
  76         gpointer extra_data;
  77 };
  78
  79 struct _PurpleTrieState
  80 {
  81         PurpleTrieState *parent;
  82         PurpleTrieState **children;
  83
  84         PurpleTrieState *longest_suffix;
  85
  86         PurpleTrieRecord *found_word;
  87 };
  88
  89 typedef struct
  90 {
  91         PurpleTrieState *state;
  92
  93         PurpleTrieState *root_state;
  94         gboolean reset_on_match;
  95
  96         PurpleTrieReplaceCb replace_cb;
  97         PurpleTrieFindCb find_cb;
  98         gpointer user_data;
  99 } PurpleTrieMachine;
 100
 101 /* TODO: an option to make it eager or lazy (now, it's eager) */
 102 enum
 103 {
 104         PROP_ZERO,
 105         PROP_RESET_ON_MATCH,
 106         PROP_LAST
 107 };
 108
 109 static GObjectClass *parent_class = NULL;
 110 static GParamSpec *properties[PROP_LAST];
 111
 112
 113 /*******************************************************************************
 114  * Records list
 115  ******************************************************************************/
 116
 117 static PurpleTrieRecordList *
 118 purple_record_list_new(PurpleMemoryPool *mpool, PurpleTrieRecord *rec)
 119 {
 120         PurpleTrieRecordList *node;
 121
 122         node = purple_memory_pool_alloc0(mpool,
 123                 sizeof(PurpleTrieRecordList), sizeof(gpointer));
 124         g_return_val_if_fail(node != NULL, NULL);
 125
 126         node->rec = rec;
 127
 128         return node;
 129 }
 130
 131 static PurpleTrieRecordList *
 132 purple_record_list_prepend(PurpleMemoryPool *mpool,
 133         PurpleTrieRecordList *old_head, PurpleTrieRecord *rec)
 134 {
 135         PurpleTrieRecordList *new_head;
 136
 137         new_head = purple_record_list_new(mpool, rec);
 138         g_return_val_if_fail(new_head != NULL, NULL);
 139
 140         new_head->next = old_head;
 141         if (old_head)
 142                 old_head->prev = new_head;
 143
 144         return new_head;
 145 }
 146
 147 static PurpleTrieRecordList *
 148 purple_record_list_copy(PurpleMemoryPool *mpool,
 149         const PurpleTrieRecordList *head)
 150 {
 151         PurpleTrieRecordList *new_head = NULL, *new_tail = NULL;
 152
 153         while (head) {
 154                 PurpleTrieRecordList *node;
 155
 156                 node = purple_record_list_new(mpool, head->rec);
 157                 g_return_val_if_fail(node != NULL, NULL); /* there is no leak */
 158
 159                 node->prev = new_tail;
 160                 if (new_tail)
 161                         new_tail->next = node;
 162                 new_tail = node;
 163                 if (!new_head)
 164                         new_head = node;
 165
 166                 head = head->next;
 167         }
 168
 169         return new_head;
 170 }
 171
 172 static PurpleTrieRecordList *
 173 purple_record_list_remove(PurpleTrieRecordList *head,
 174         PurpleTrieRecordList *node)
 175 {
 176         g_return_val_if_fail(head != NULL, NULL);
 177         g_return_val_if_fail(node != NULL, head);
 178         g_return_val_if_fail(head->prev == NULL, NULL);
 179
 180         if (head == node) {
 181                 if (head->next != NULL)
 182                         head->next->prev = NULL;
 183                 return head->next;
 184         } else {
 185                 g_return_val_if_fail(node->prev != NULL, NULL);
 186                 node->prev->next = node->next;
 187                 if (node->next != NULL)
 188                         node->next->prev = node->prev;
 189                 return head;
 190         }
 191 }
 192
 193
 194 /*******************************************************************************
 195  * States management
 196  ******************************************************************************/
 197
 198 static void
 199 purple_trie_states_cleanup(PurpleTrie *trie)
 200 {
 201         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 202
 203         g_return_if_fail(priv != NULL);
 204
 205         if (priv->root_state != NULL) {
 206                 purple_memory_pool_cleanup(priv->states_mempool);
 207                 priv->root_state = NULL;
 208         }
 209 }
 210
 211 /* Allocates a state and binds it to the parent. */
 212 static PurpleTrieState *
 213 purple_trie_state_new(PurpleTrie *trie, PurpleTrieState *parent, guchar character)
 214 {
 215         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 216         PurpleTrieState *state;
 217
 218         g_return_val_if_fail(priv != NULL, NULL);
 219
 220         state = purple_memory_pool_alloc0(priv->states_mempool,
 221                 sizeof(PurpleTrieState), sizeof(gpointer));
 222         g_return_val_if_fail(state != NULL, NULL);
 223
 224         if (parent == NULL)
 225                 return state;
 226
 227         state->parent = parent;
 228         if (parent->children == NULL) {
 229                 parent->children = purple_memory_pool_alloc0(
 230                         priv->states_mempool,
 231                         /* PurpleTrieState *children[G_MAXUCHAR + 1] */
 232                         256 * sizeof(gpointer),
 233                         sizeof(gpointer));
 234         }
 235
 236         if (parent->children == NULL) {
 237                 purple_memory_pool_free(priv->states_mempool, state);
 238                 g_warn_if_reached();
 239                 return NULL;
 240         }
 241
 242         parent->children[character] = state;
 243
 244         return state;
 245 }
 246
 247 #if 0
 248 static gchar *
 249 purple_trie_print(PurpleTrieState *state, int limit)
 250 {
 251         GString *str = g_string_new(NULL);
 252         int i;
 253
 254         if (limit < 0)
 255                 return g_strdup("{ LIMIT }");
 256
 257         if (state->found_word)
 258                 g_string_append(str, "*");
 259         g_string_append(str, "{ ");
 260         for (i = 0; i < 256; i++) {
 261                 gchar *chp;
 262                 if (!state->children)
 263                         continue;
 264                 if (!state->children[i])
 265                         continue;
 266                 if (i == 0)
 267                         g_string_append(str, "(null)->");
 268                 else
 269                         g_string_append_printf(str, "%c->", i);
 270                 if (state->children[i] == state)
 271                         g_string_append(str, "loop");
 272                 else {
 273                         chp = purple_trie_print(state->children[i], limit - 1);
 274                         g_string_append(str, chp);
 275                         g_string_append_c(str, ' ');
 276                         g_free(chp);
 277                 }
 278         }
 279         g_string_append(str, "}");
 280
 281         return g_string_free(str, FALSE);
 282 }
 283 #endif
 284
 285 static gboolean
 286 purple_trie_states_build(PurpleTrie *trie)
 287 {
 288         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 289         PurpleTrieState *root;
 290         PurpleMemoryPool *reclist_mpool;
 291         PurpleTrieRecordList *reclist, *it;
 292         gulong cur_len;
 293
 294         g_return_val_if_fail(priv != NULL, FALSE);
 295
 296         if (priv->root_state != NULL)
 297                 return TRUE;
 298
 299         if (priv->records_total_size < PURPLE_TRIE_LARGE_THRESHOLD) {
 300                 purple_memory_pool_set_block_size(priv->states_mempool,
 301                         PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE);
 302         } else {
 303                 purple_memory_pool_set_block_size(priv->states_mempool,
 304                         PURPLE_TRIE_STATES_LARGE_POOL_BLOCK_SIZE);
 305         }
 306
 307         priv->root_state = root = purple_trie_state_new(trie, NULL, '\0');
 308         g_return_val_if_fail(root != NULL, FALSE);
 309         g_assert(root->longest_suffix == NULL);
 310
 311         /* reclist is a list of words not yet added to the trie. Shorter words
 312          * are removed from the list, when they are fully added to the trie. */
 313         reclist_mpool = purple_memory_pool_new();
 314         reclist = purple_record_list_copy(reclist_mpool, priv->records);
 315
 316         /* extra_data on every element of reclist will be a pointer to a trie
 317          * node -- the prefix of the word with len of cur_len */
 318         for (it = reclist; it != NULL; it = it->next) {
 319                 it->extra_data = root;
 320         }
 321
 322         /* Iterate over indexes of words -- every loop iteration checks certain
 323          * index of all remaining words. Loop finishes when there are no words
 324          * longer than cur_len. */
 325         for (cur_len = 0; reclist != NULL; cur_len++) {
 326                 for (it = reclist; it; it = it->next) {
 327                         PurpleTrieRecord *rec = it->rec;
 328                         guchar character = rec->word[cur_len];
 329                         PurpleTrieState *prefix = it->extra_data;
 330                         PurpleTrieState *lon_suf_parent;
 331
 332                         g_assert(character != '\0');
 333
 334                         if (prefix->children && prefix->children[character]) {
 335                                 /* Word's prefix is already in the trie, added
 336                                  * by the other word. */
 337                                 prefix = prefix->children[character];
 338                         } else {
 339                                 /* We need to create a new branch of trie. */
 340                                 prefix = purple_trie_state_new(trie, prefix,
 341                                         character);
 342                                 if (!prefix) {
 343                                         g_warn_if_reached();
 344                                         g_object_unref(reclist_mpool);
 345                                         return FALSE;
 346                                 }
 347                         }
 348                         it->extra_data = prefix;
 349                         /* prefix is now of length increased by one character. */
 350
 351                         /* The whole word is now added to the trie. */
 352                         if (rec->word[cur_len + 1] == '\0') {
 353                                 if (prefix->found_word == NULL)
 354                                         prefix->found_word = rec;
 355                                 else {
 356                                         purple_debug_warning("trie", "found "
 357                                                 "a collision of \"%s\" words",
 358                                                 rec->word);
 359                                 }
 360
 361                                 /* "it" is not modified here, so it->next is
 362                                  * still valid */
 363                                 reclist = purple_record_list_remove(reclist, it);
 364                         }
 365
 366                         /* We need to fill the longest_suffix field -- a longest
 367                          * complete suffix of the prefix we created. We look for
 368                          * that suffix in any path starting in root and ending
 369                          * in the (cur_len - 1) level of trie. */
 370                         if (prefix->longest_suffix != NULL)
 371                                 continue;
 372                         lon_suf_parent = prefix->parent->longest_suffix;
 373                         while (lon_suf_parent) {
 374                                 if (lon_suf_parent->children &&
 375                                         lon_suf_parent->children[character])
 376                                 {
 377                                         prefix->longest_suffix = lon_suf_parent->
 378                                                 children[character];
 379                                         break;
 380                                 }
 381                                 lon_suf_parent = lon_suf_parent->longest_suffix;
 382                         }
 383                         if (prefix->longest_suffix == NULL)
 384                                 prefix->longest_suffix = root;
 385                         if (prefix->found_word == NULL) {
 386                                 prefix->found_word =
 387                                         prefix->longest_suffix->found_word;
 388                         }
 389                 }
 390         }
 391
 392         g_object_unref(reclist_mpool);
 393
 394         return TRUE;
 395 }
 396
 397 /*******************************************************************************
 398  * Searching
 399  ******************************************************************************/
 400
 401 static void
 402 purple_trie_advance(PurpleTrieMachine *m, const guchar character)
 403 {
 404         /* change state after processing a character */
 405         while (TRUE) {
 406                 /* Perfect fit - next character is the same, as the child of the
 407                  * prefix we reached so far. */
 408                 if (m->state->children && m->state->children[character]) {
 409                         m->state = m->state->children[character];
 410                         break;
 411                 }
 412
 413                 /* We reached root, that's a pity. */
 414                 if (m->state == m->root_state)
 415                         break;
 416
 417                 /* Let's try a bit shorter suffix. */
 418                 m->state = m->state->longest_suffix;
 419         }
 420 }
 421
 422 static gboolean
 423 purple_trie_replace_do_replacement(PurpleTrieMachine *m, GString *out)
 424 {
 425         gboolean was_replaced = FALSE;
 426         gsize str_old_len;
 427
 428         /* if we reached a "found" state, let's process it */
 429         if (!m->state->found_word)
 430                 return FALSE;
 431
 432         /* let's get back to the beginning of the word */
 433         g_assert(out->len >= m->state->found_word->word_len - 1);
 434         str_old_len = out->len;
 435         out->len -= m->state->found_word->word_len - 1;
 436
 437         was_replaced = m->replace_cb(out, m->state->found_word->word,
 438                 m->state->found_word->data, m->user_data);
 439
 440         /* output was untouched, revert to the previous position */
 441         if (!was_replaced)
 442                 out->len = str_old_len;
 443
 444         /* XXX */
 445         if (was_replaced || m->reset_on_match)
 446                 m->state = m->root_state;
 447
 448         return was_replaced;
 449 }
 450
 451 static gboolean
 452 purple_trie_find_do_discovery(PurpleTrieMachine *m)
 453 {
 454         gboolean was_accepted;
 455
 456         /* if we reached a "found" state, let's process it */
 457         if (!m->state->found_word)
 458                 return FALSE;
 459
 460         if (m->find_cb) {
 461                 was_accepted = m->find_cb(m->state->found_word->word,
 462                         m->state->found_word->data, m->user_data);
 463         } else {
 464                 was_accepted = TRUE;
 465         }
 466
 467         if (was_accepted && m->reset_on_match)
 468                 m->state = m->root_state;
 469
 470         return was_accepted;
 471 }
 472
 473 gchar *
 474 purple_trie_replace(PurpleTrie *trie, const gchar *src,
 475         PurpleTrieReplaceCb replace_cb, gpointer user_data)
 476 {
 477         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 478         PurpleTrieMachine machine;
 479         GString *out;
 480         gsize i;
 481
 482         if (src == NULL)
 483                 return NULL;
 484
 485         g_return_val_if_fail(replace_cb != NULL, g_strdup(src));
 486         g_return_val_if_fail(priv != NULL, NULL);
 487
 488         purple_trie_states_build(trie);
 489
 490         machine.state = priv->root_state;
 491         machine.root_state = priv->root_state;
 492         machine.reset_on_match = priv->reset_on_match;
 493         machine.replace_cb = replace_cb;
 494         machine.user_data = user_data;
 495
 496         out = g_string_new(NULL);
 497         i = 0;
 498         while (src[i] != '\0') {
 499                 guchar character = src[i++];
 500                 gboolean was_replaced;
 501
 502                 purple_trie_advance(&machine, character);
 503                 was_replaced = purple_trie_replace_do_replacement(&machine, out);
 504
 505                 /* We skipped a character without finding any records,
 506                  * let's just copy it to the output. */
 507                 if (!was_replaced)
 508                         g_string_append_c(out, character);
 509         }
 510
 511         return g_string_free(out, FALSE);
 512 }
 513
 514 gchar *
 515 purple_trie_multi_replace(const GSList *tries, const gchar *src,
 516         PurpleTrieReplaceCb replace_cb, gpointer user_data)
 517 {
 518         guint tries_count, m_idx;
 519         PurpleTrieMachine *machines;
 520         GString *out;
 521         gsize i;
 522
 523         if (src == NULL)
 524                 return NULL;
 525
 526         g_return_val_if_fail(replace_cb != NULL, g_strdup(src));
 527
 528         tries_count = g_slist_length((GSList*)tries);
 529         if (tries_count == 0)
 530                 return g_strdup(src);
 531
 532         /* Initialize all machines. */
 533         machines = g_new(PurpleTrieMachine, tries_count);
 534         for (i = 0; i < tries_count; i++, tries = tries->next) {
 535                 PurpleTrie *trie = tries->data;
 536                 PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 537
 538                 if (priv == NULL) {
 539                         g_warn_if_reached();
 540                         g_free(machines);
 541                         return NULL;
 542                 }
 543
 544                 purple_trie_states_build(trie);
 545
 546                 machines[i].state = priv->root_state;
 547                 machines[i].root_state = priv->root_state;
 548                 machines[i].reset_on_match = priv->reset_on_match;
 549                 machines[i].replace_cb = replace_cb;
 550                 machines[i].user_data = user_data;
 551         }
 552
 553         out = g_string_new(NULL);
 554         i = 0;
 555         while (src[i] != '\0') {
 556                 guchar character = src[i++];
 557                 gboolean was_replaced = FALSE;
 558
 559                 /* Advance every machine and possibly perform a replacement. */
 560                 for (m_idx = 0; m_idx < tries_count; m_idx++) {
 561                         purple_trie_advance(&machines[m_idx], character);
 562                         if (was_replaced)
 563                                 continue;
 564                         was_replaced = purple_trie_replace_do_replacement(
 565                                 &machines[m_idx], out);
 566                 }
 567
 568                 /* We skipped a character without finding any records,
 569                  * let's just copy it to the output. */
 570                 if (!was_replaced)
 571                         g_string_append_c(out, character);
 572
 573                 /* If we replaced a word, reset _all_ machines */
 574                 if (was_replaced) {
 575                         for (m_idx = 0; m_idx < tries_count; m_idx++) {
 576                                 machines[m_idx].state =
 577                                         machines[m_idx].root_state;
 578                         }
 579                 }
 580         }
 581
 582         g_free(machines);
 583         return g_string_free(out, FALSE);
 584 }
 585
 586 gulong
 587 purple_trie_find(PurpleTrie *trie, const gchar *src,
 588         PurpleTrieFindCb find_cb, gpointer user_data)
 589 {
 590         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 591         PurpleTrieMachine machine;
 592         gulong found_count = 0;
 593         gsize i;
 594
 595         if (src == NULL)
 596                 return 0;
 597
 598         g_return_val_if_fail(priv != NULL, 0);
 599
 600         purple_trie_states_build(trie);
 601
 602         machine.state = priv->root_state;
 603         machine.root_state = priv->root_state;
 604         machine.reset_on_match = priv->reset_on_match;
 605         machine.find_cb = find_cb;
 606         machine.user_data = user_data;
 607
 608         i = 0;
 609         while (src[i] != '\0') {
 610                 guchar character = src[i++];
 611                 gboolean was_found;
 612
 613                 purple_trie_advance(&machine, character);
 614
 615                 was_found = purple_trie_find_do_discovery(&machine);
 616
 617                 if (was_found)
 618                         found_count++;
 619         }
 620
 621         return found_count;
 622 }
 623
 624 gulong
 625 purple_trie_multi_find(const GSList *tries, const gchar *src,
 626         PurpleTrieFindCb find_cb, gpointer user_data)
 627 {
 628         guint tries_count, m_idx;
 629         PurpleTrieMachine *machines;
 630         gulong found_count = 0;
 631         gsize i;
 632
 633         if (src == NULL)
 634                 return 0;
 635
 636         tries_count = g_slist_length((GSList*)tries);
 637         if (tries_count == 0)
 638                 return 0;
 639
 640         /* Initialize all machines. */
 641         machines = g_new(PurpleTrieMachine, tries_count);
 642         for (i = 0; i < tries_count; i++, tries = tries->next) {
 643                 PurpleTrie *trie = tries->data;
 644                 PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 645
 646                 if (priv == NULL) {
 647                         g_warn_if_reached();
 648                         g_free(machines);
 649                         return 0;
 650                 }
 651
 652                 purple_trie_states_build(trie);
 653
 654                 machines[i].state = priv->root_state;
 655                 machines[i].root_state = priv->root_state;
 656                 machines[i].reset_on_match = priv->reset_on_match;
 657                 machines[i].find_cb = find_cb;
 658                 machines[i].user_data = user_data;
 659         }
 660
 661         i = 0;
 662         while (src[i] != '\0') {
 663                 guchar character = src[i++];
 664                 gboolean was_found = FALSE;
 665
 666                 /* Advance every machine and possibly perform a replacement. */
 667                 for (m_idx = 0; m_idx < tries_count; m_idx++) {
 668                         purple_trie_advance(&machines[m_idx], character);
 669                         if (was_found)
 670                                 continue;
 671                         was_found =
 672                                 purple_trie_find_do_discovery(&machines[m_idx]);
 673                         if (was_found)
 674                                 found_count++;
 675                 }
 676
 677                 /* If we replaced a word, reset _all_ machines */
 678                 if (was_found) {
 679                         for (m_idx = 0; m_idx < tries_count; m_idx++) {
 680                                 if (!machines[m_idx].reset_on_match)
 681                                         continue;
 682                                 machines[m_idx].state =
 683                                         machines[m_idx].root_state;
 684                         }
 685                 }
 686         }
 687
 688         g_free(machines);
 689         return found_count;
 690 }
 691
 692
 693 /*******************************************************************************
 694  * Records
 695  ******************************************************************************/
 696
 697 gboolean
 698 purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data)
 699 {
 700         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 701         PurpleTrieRecord *rec;
 702
 703         g_return_val_if_fail(priv != NULL, FALSE);
 704         g_return_val_if_fail(word != NULL, FALSE);
 705         g_return_val_if_fail(word[0] != '\0', FALSE);
 706
 707         if (g_hash_table_lookup(priv->records_map, word) != NULL) {
 708                 purple_debug_warning("trie", "record exists: %s", word);
 709                 return FALSE;
 710         }
 711
 712         /* Every change in a trie invalidates longest_suffix map.
 713          * These prefixes could be updated instead of cleaning the whole graph.
 714          */
 715         purple_trie_states_cleanup(trie);
 716
 717         rec = purple_memory_pool_alloc(priv->records_obj_mempool,
 718                 sizeof(PurpleTrieRecord), sizeof(gpointer));
 719         rec->word = purple_memory_pool_strdup(priv->records_str_mempool, word);
 720         rec->word_len = strlen(word);
 721         g_assert(rec->word_len > 0);
 722         rec->data = data;
 723
 724         priv->records_total_size += rec->word_len;
 725         priv->records = purple_record_list_prepend(priv->records_obj_mempool,
 726                 priv->records, rec);
 727         g_hash_table_insert(priv->records_map, rec->word, priv->records);
 728
 729         return TRUE;
 730 }
 731
 732 void
 733 purple_trie_remove(PurpleTrie *trie, const gchar *word)
 734 {
 735         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 736         PurpleTrieRecordList *it;
 737
 738         g_return_if_fail(priv != NULL);
 739         g_return_if_fail(word != NULL);
 740         g_return_if_fail(word[0] != '\0');
 741
 742         it = g_hash_table_lookup(priv->records_map, word);
 743         if (it == NULL)
 744                 return;
 745
 746         /* see purple_trie_add */
 747         purple_trie_states_cleanup(trie);
 748
 749         priv->records_total_size -= it->rec->word_len;
 750         priv->records = purple_record_list_remove(priv->records, it);
 751         g_hash_table_remove(priv->records_map, it->rec->word);
 752
 753         purple_memory_pool_free(priv->records_str_mempool, it->rec->word);
 754         purple_memory_pool_free(priv->records_obj_mempool, it->rec);
 755         purple_memory_pool_free(priv->records_obj_mempool, it);
 756 }
 757
 758 guint
 759 purple_trie_get_size(PurpleTrie *trie)
 760 {
 761         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 762
 763         g_return_val_if_fail(priv != NULL, 0);
 764
 765         return g_hash_table_size(priv->records_map);
 766 }
 767
 768
 769 /*******************************************************************************
 770  * API implementation
 771  ******************************************************************************/
 772
 773 gboolean
 774 purple_trie_get_reset_on_match(PurpleTrie *trie)
 775 {
 776         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 777
 778         g_return_val_if_fail(priv, FALSE);
 779
 780         return priv->reset_on_match;
 781 }
 782
 783 void
 784 purple_trie_set_reset_on_match(PurpleTrie *trie, gboolean reset)
 785 {
 786         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 787
 788         g_return_if_fail(priv);
 789
 790         priv->reset_on_match = reset;
 791         g_object_notify_by_pspec(G_OBJECT(trie), properties[PROP_RESET_ON_MATCH]);
 792 }
 793
 794 /*******************************************************************************
 795  * Object stuff
 796  ******************************************************************************/
 797
 798 PurpleTrie *
 799 purple_trie_new(void)
 800 {
 801         return g_object_new(PURPLE_TYPE_TRIE, NULL);
 802 }
 803
 804 static void
 805 purple_trie_init(GTypeInstance *instance, gpointer klass)
 806 {
 807         PurpleTrie *trie = PURPLE_TRIE(instance);
 808         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 809
 810         priv->records_obj_mempool = purple_memory_pool_new();
 811         priv->records_str_mempool = purple_memory_pool_new();
 812         priv->states_mempool = purple_memory_pool_new();
 813         purple_memory_pool_set_block_size(priv->states_mempool,
 814                 PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE);
 815
 816         priv->records_map = g_hash_table_new(g_str_hash, g_str_equal);
 817 }
 818
 819 static void
 820 purple_trie_finalize(GObject *obj)
 821 {
 822         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(obj);
 823
 824         g_hash_table_destroy(priv->records_map);
 825         g_object_unref(priv->records_obj_mempool);
 826         g_object_unref(priv->records_str_mempool);
 827         g_object_unref(priv->states_mempool);
 828
 829         G_OBJECT_CLASS(parent_class)->finalize(obj);
 830 }
 831
 832 static void
 833 purple_trie_get_property(GObject *obj, guint param_id, GValue *value,
 834         GParamSpec *pspec)
 835 {
 836         PurpleTrie *trie = PURPLE_TRIE(obj);
 837         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 838
 839         switch (param_id) {
 840                 case PROP_RESET_ON_MATCH:
 841                         g_value_set_boolean(value, priv->reset_on_match);
 842                         break;
 843                 default:
 844                         G_OBJECT_WARN_INVALID_PROPERTY_ID(obj, param_id, pspec);
 845         }
 846 }
 847
 848 static void
 849 purple_trie_set_property(GObject *obj, guint param_id,
 850         const GValue *value, GParamSpec *pspec)
 851 {
 852         PurpleTrie *trie = PURPLE_TRIE(obj);
 853         PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 854
 855         switch (param_id) {
 856                 case PROP_RESET_ON_MATCH:
 857                         priv->reset_on_match = g_value_get_boolean(value);
 858                         break;
 859                 default:
 860                         G_OBJECT_WARN_INVALID_PROPERTY_ID(obj, param_id, pspec);
 861         }
 862 }
 863
 864 static void
 865 purple_trie_class_init(PurpleTrieClass *klass)
 866 {
 867         GObjectClass *obj_class = G_OBJECT_CLASS(klass);
 868
 869         parent_class = g_type_class_peek_parent(klass);
 870
 871         g_type_class_add_private(klass, sizeof(PurpleTriePrivate));
 872
 873         obj_class->finalize = purple_trie_finalize;
 874         obj_class->get_property = purple_trie_get_property;
 875         obj_class->set_property = purple_trie_set_property;
 876
 877         properties[PROP_RESET_ON_MATCH] = g_param_spec_boolean("reset-on-match",
 878                 "Reset on match", "Determines, if the search state machine "
 879                 "should be reset to the initial state on every match. This "
 880                 "ensures, that every match is distinct from each other. "
 881                 "Please note, that it's not well-defined for a replace "
 882                 "operation, so it's better to leave this value default, unless "
 883                 "you perform only find operations.", TRUE,
 884                 G_PARAM_READWRITE | G_PARAM_CONSTRUCT | G_PARAM_STATIC_STRINGS);
 885
 886         g_object_class_install_properties(obj_class, PROP_LAST, properties);
 887 }
 888
 889 GType
 890 purple_trie_get_type(void)
 891 {
 892         static GType type = 0;
 893
 894         if (G_UNLIKELY(type == 0)) {
 895                 static const GTypeInfo info = {
 896                         .class_size = sizeof(PurpleTrieClass),
 897                         .class_init = (GClassInitFunc)purple_trie_class_init,
 898                         .instance_size = sizeof(PurpleTrie),
 899                         .instance_init = purple_trie_init,
 900                 };
 901
 902                 type = g_type_register_static(G_TYPE_OBJECT,
 903                         "PurpleTrie", &info, 0);
 904         }
 905
 906         return type;
 907 }