libpurple/tests/test_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 <glib.h>
  24
  25 #include "../trie.h"
  26
  27 static gint find_sum;
  28
  29 static gboolean
  30 test_trie_replace_cb(GString *out, const gchar *word, gpointer word_data,
  31         gpointer user_data)
  32 {
  33         /* the "test" word for the test_trie_replace test */
  34         if ((gintptr)word_data == 0x1001)
  35                 return FALSE;
  36
  37         g_string_append_printf(out, "[%d:%x]",
  38                 (int)(gintptr)user_data, (int)(gintptr)word_data);
  39
  40         return TRUE;
  41 }
  42
  43 static gboolean
  44 test_trie_find_cb(const gchar *word, gpointer word_data,
  45         gpointer user_data)
  46 {
  47         if ((gintptr)word_data == 0x7004)
  48                 return FALSE;
  49
  50         find_sum += (gintptr)word_data;
  51         find_sum -= (gintptr)user_data * 0x1000;
  52
  53         return TRUE;
  54 }
  55
  56 static void
  57 test_trie_replace_normal(void) {
  58         PurpleTrie *trie;
  59         const gchar *in;
  60         gchar *out;
  61
  62         trie = purple_trie_new();
  63         purple_trie_set_reset_on_match(trie, FALSE);
  64
  65         purple_trie_add(trie, "test", (gpointer)0x1001);
  66         purple_trie_add(trie, "testing", (gpointer)0x1002);
  67         purple_trie_add(trie, "overtested", (gpointer)0x1003);
  68         purple_trie_add(trie, "trie", (gpointer)0x1004);
  69         purple_trie_add(trie, "tree", (gpointer)0x1005);
  70         purple_trie_add(trie, "implement", (gpointer)0x1006);
  71         purple_trie_add(trie, "implementation", (gpointer)0x1007);
  72
  73         in = "Alice is testing her trie implementation, "
  74                 "but she's far away from making test tree overtested";
  75
  76         out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)1);
  77
  78         g_assert_cmpstr(
  79                 "Alice is [1:1002] her [1:1004] [1:1006]ation,"
  80                 " but she's far away from making test [1:1005] [1:1003]",
  81                 ==,
  82                 out
  83         );
  84
  85         g_object_unref(trie);
  86         g_free(out);
  87 }
  88
  89 static void
  90 test_trie_replace_whole(void) {
  91         PurpleTrie *trie;
  92         const gchar *in;
  93         gchar *out;
  94
  95         trie = purple_trie_new();
  96
  97         purple_trie_add(trie, "test", (gpointer)0x2002);
  98
  99         in = "test";
 100
 101         out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)2);
 102
 103         g_assert_cmpstr("[2:2002]", ==, out);
 104
 105         g_object_unref(trie);
 106         g_free(out);
 107 }
 108
 109 static void
 110 test_trie_replace_inner(void) {
 111         PurpleTrie *trie;
 112         const gchar *in;
 113         gchar *out;
 114
 115         trie = purple_trie_new();
 116
 117         purple_trie_add(trie, "est", (gpointer)0x3001);
 118         purple_trie_add(trie, "tester", (gpointer)0x3002);
 119
 120         in = "the test!";
 121
 122         out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)3);
 123
 124         g_assert_cmpstr("the t[3:3001]!", ==, out);
 125
 126         g_object_unref(trie);
 127         g_free(out);
 128 }
 129
 130
 131 static void
 132 test_trie_replace_empty(void) {
 133         PurpleTrie *trie;
 134         const gchar *in;
 135         gchar *out;
 136
 137         trie = purple_trie_new();
 138
 139         purple_trie_add(trie, "test", (gpointer)0x4001);
 140
 141         in = "";
 142
 143         out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)4);
 144
 145         g_assert_cmpstr("", ==, out);
 146
 147         g_object_unref(trie);
 148         g_free(out);
 149 }
 150
 151 static void
 152 test_trie_multi_replace(void) {
 153         PurpleTrie *trie1, *trie2, *trie3;
 154         GSList *tries = NULL;
 155         const gchar *in;
 156         gchar *out;
 157
 158         trie1 = purple_trie_new();
 159         trie2 = purple_trie_new();
 160         trie3 = purple_trie_new();
 161
 162         /* appending is not efficient, but we have only 3 elements */
 163         tries = g_slist_append(tries, trie1);
 164         tries = g_slist_append(tries, trie2);
 165         tries = g_slist_append(tries, trie3);
 166
 167         purple_trie_add(trie1, "test", (gpointer)0x5011);
 168         purple_trie_add(trie1, "trie1", (gpointer)0x5012);
 169         purple_trie_add(trie1, "Alice", (gpointer)0x5013);
 170
 171         purple_trie_add(trie2, "test", (gpointer)0x5021);
 172         purple_trie_add(trie2, "trie2", (gpointer)0x5022);
 173         purple_trie_add(trie2, "example", (gpointer)0x5023);
 174         purple_trie_add(trie2, "Ali", (gpointer)0x5024);
 175
 176         /* "tester" without last (accepting) letter of "test" */
 177         purple_trie_add(trie3, "teser", (gpointer)0x5031);
 178         purple_trie_add(trie3, "trie3", (gpointer)0x5032);
 179         purple_trie_add(trie3, "tester", (gpointer)0x5033);
 180         purple_trie_add(trie3, "example", (gpointer)0x5034);
 181         purple_trie_add(trie3, "Al", (gpointer)0x5035);
 182
 183         in = "test tester trie trie1 trie2 trie3 example Alice";
 184
 185         out = purple_trie_multi_replace(tries, in,
 186                 test_trie_replace_cb, (gpointer)5);
 187
 188         g_assert_cmpstr(
 189                 "[5:5011] [5:5011]er trie [5:5012] [5:5022] "
 190                 "[5:5032] [5:5023] [5:5035]ice",
 191                 ==,
 192                 out
 193         );
 194
 195         g_slist_free_full(tries, g_object_unref);
 196         g_free(out);
 197 }
 198
 199 static void
 200 test_trie_remove(void) {
 201         PurpleTrie *trie;
 202         const gchar *in;
 203         gchar *out;
 204
 205         trie = purple_trie_new();
 206
 207         purple_trie_add(trie, "alice", (gpointer)0x6001);
 208         purple_trie_add(trie, "bob", (gpointer)0x6002);
 209         purple_trie_add(trie, "cherry", (gpointer)0x6003);
 210
 211         purple_trie_remove(trie, "bob");
 212
 213         in = "alice bob cherry";
 214
 215         out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)6);
 216
 217         g_assert_cmpstr("[6:6001] bob [6:6003]", ==, out);
 218
 219         g_object_unref(trie);
 220         g_free(out);
 221 }
 222
 223 static void
 224 test_trie_find_normal(void) {
 225         PurpleTrie *trie;
 226         const gchar *in;
 227         gint out;
 228
 229         trie = purple_trie_new();
 230
 231         purple_trie_add(trie, "alice", (gpointer)0x7001);
 232         purple_trie_add(trie, "bob", (gpointer)0x7002);
 233         purple_trie_add(trie, "cherry", (gpointer)0x7003);
 234         purple_trie_add(trie, "al", (gpointer)0x7004); /* not accepted */
 235
 236         in = "test alice bob test cherry alice";
 237
 238         find_sum = 0;
 239         out = purple_trie_find(trie, in, test_trie_find_cb, (gpointer)7);
 240
 241         g_assert_cmpint(4, ==, out);
 242         g_assert_cmpint(2 * 1 + 2 + 3, ==, find_sum);
 243
 244         g_object_unref(trie);
 245 }
 246
 247 static void
 248 test_trie_find_reset(void) {
 249         PurpleTrie *trie;
 250         const gchar *in;
 251         gint out;
 252
 253         trie = purple_trie_new();
 254         purple_trie_set_reset_on_match(trie, TRUE);
 255
 256         purple_trie_add(trie, "alice", (gpointer)0x8001);
 257         purple_trie_add(trie, "ali", (gpointer)0x8002);
 258         purple_trie_add(trie, "al", (gpointer)0x8003);
 259
 260         in = "al ali alice";
 261
 262         find_sum = 0;
 263         out = purple_trie_find(trie, in, test_trie_find_cb, (gpointer)8);
 264
 265         g_assert_cmpint(3, ==, out);
 266         g_assert_cmpint(3 * 3, ==, find_sum);
 267
 268         g_object_unref(trie);
 269 }
 270
 271 static void
 272 test_trie_find_noreset(void) {
 273         PurpleTrie *trie;
 274         const gchar *in;
 275         gint out;
 276
 277         trie = purple_trie_new();
 278         purple_trie_set_reset_on_match(trie, FALSE);
 279
 280         purple_trie_add(trie, "alice", (gpointer)0x9001);
 281         purple_trie_add(trie, "ali", (gpointer)0x9002);
 282         purple_trie_add(trie, "al", (gpointer)0x9003);
 283
 284         in = "al ali alice";
 285
 286         find_sum = 0;
 287         out = purple_trie_find(trie, in, test_trie_find_cb, (gpointer)9);
 288
 289         g_assert_cmpint(6, ==, out);
 290         g_assert_cmpint(3 * 3 + 2 * 2 + 1, ==, find_sum);
 291
 292         g_object_unref(trie);
 293 }
 294
 295 static void
 296 test_trie_multi_find(void) {
 297         PurpleTrie *trie1, *trie2, *trie3;
 298         GSList *tries = NULL;
 299         const gchar *in;
 300         int out;
 301
 302         trie1 = purple_trie_new();
 303         trie2 = purple_trie_new();
 304         trie3 = purple_trie_new();
 305         purple_trie_set_reset_on_match(trie1, FALSE);
 306         purple_trie_set_reset_on_match(trie2, TRUE);
 307         purple_trie_set_reset_on_match(trie3, FALSE);
 308
 309         /* appending is not efficient, but we have only 3 elements */
 310         tries = g_slist_append(tries, trie1);
 311         tries = g_slist_append(tries, trie2);
 312         tries = g_slist_append(tries, trie3);
 313
 314         purple_trie_add(trie1, "test", (gpointer)0x10011);
 315         purple_trie_add(trie1, "trie1", (gpointer)0x10012);
 316         purple_trie_add(trie1, "Alice", (gpointer)0x10013);
 317
 318         purple_trie_add(trie2, "test", (gpointer)0x10021);
 319         purple_trie_add(trie2, "trie2", (gpointer)0x10022);
 320         purple_trie_add(trie2, "example", (gpointer)0x10023);
 321         purple_trie_add(trie2, "Ali", (gpointer)0x10024);
 322
 323         /* "tester" without last (accepting) letter of "test" */
 324         purple_trie_add(trie3, "teser", (gpointer)0x10031);
 325         purple_trie_add(trie3, "trie3", (gpointer)0x10032);
 326         purple_trie_add(trie3, "tester", (gpointer)0x10033);
 327         purple_trie_add(trie3, "example", (gpointer)0x10034);
 328         purple_trie_add(trie3, "Al", (gpointer)0x10035);
 329
 330         in = "test tester trie trie1 trie2 trie3 example Alice";
 331
 332         out = purple_trie_multi_find(tries, in,
 333                 test_trie_find_cb, (gpointer)0x10);
 334
 335         g_assert_cmpint(9, ==, out);
 336         g_assert_cmpint(2 * 0x11 + 0x33 + 0x12 + 0x22 +
 337                 0x32 + 0x23 + 0x35 + 0x13, ==, find_sum);
 338
 339         g_slist_free_full(tries, g_object_unref);
 340 }
 341
 342 gint
 343 main(gint argc, gchar **argv) {
 344         g_test_init(&argc, &argv, NULL);
 345
 346         g_test_add_func("/trie/replace/normal",
 347                         test_trie_replace_normal);
 348         g_test_add_func("/trie/replace/whole",
 349                         test_trie_replace_whole);
 350         g_test_add_func("/trie/replace/inner",
 351                         test_trie_replace_inner);
 352         g_test_add_func("/trie/replace/empty",
 353                         test_trie_replace_empty);
 354
 355         g_test_add_func("/trie/multi_replace",
 356                         test_trie_multi_replace);
 357
 358         g_test_add_func("/trie/remove",
 359                         test_trie_remove);
 360
 361         g_test_add_func("/trie/find/normal",
 362                         test_trie_find_normal);
 363         g_test_add_func("/trie/find/reset",
 364                         test_trie_find_reset);
 365         g_test_add_func("/trie/find/noreset",
 366                         test_trie_find_noreset);
 367
 368         g_test_add_func("/trie/multi_find",
 369                         test_trie_multi_find);
 370
 371         return g_test_run();
 372 }