Groonga 3.0.9 Source Code Document
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
test-trie.cpp
Go to the documentation of this file.
1 /* -*- c-basic-offset: 2; coding: utf-8 -*- */
2 /*
3  Copyright (C) 2011-2012 Brazil
4 
5  This library is free software; you can redistribute it and/or
6  modify it under the terms of the GNU Lesser General Public
7  License version 2.1 as published by the Free Software Foundation.
8 
9  This library is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  Lesser General Public License for more details.
13 
14  You should have received a copy of the GNU Lesser General Public
15  License along with this library; if not, write to the Free Software
16  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 
19 #include <gcutter.h>
20 #include <glib/gstdio.h>
21 #include <cppcutter.h>
22 
23 #include <grn-assertions.h>
24 #include <dat/trie.hpp>
25 
26 #include <algorithm>
27 #include <cstdlib>
28 #include <cstring>
29 #include <ctime>
30 #include <map>
31 #include <set>
32 #include <stack>
33 #include <string>
34 #include <vector>
35 
36 #include "test-string.hpp"
37 
38 namespace
39 {
40  class Thread {
41  public:
42  Thread() : thread_(NULL) {}
43  ~Thread() {
44  join();
45  }
46 
47  void create(GThreadFunc func, gpointer data) {
48  join();
49 
50  thread_ = g_thread_new("test-trie", func, data);
51  }
52 
53  void join() {
54  if (thread_) {
55  g_thread_join(thread_);
56  thread_ = NULL;
57  }
58  }
59 
60  private:
61  GThread *thread_;
62 
63  // Disallows copy and assignment.
64  Thread(const Thread &);
65  Thread &operator=(const Thread &);
66  };
67 
68  struct Context {
69  CutTestContext *cut_test_context;
70  grn::dat::Trie *trie;
71  bool continue_flag;
72  };
73 
74  void create_key(std::string *key, std::size_t min_length,
75  std::size_t max_length)
76  {
77  key->resize(min_length + (std::rand() % (max_length - min_length + 1)));
78  for (std::size_t i = 0; i < key->size(); ++i) {
79  (*key)[i] = '0' + (std::rand() % 10);
80  }
81  }
82 
83  void create_keys(std::vector<std::string> *keys, std::size_t num_keys,
84  std::size_t min_length, std::size_t max_length)
85  {
86  std::string key;
87  std::set<std::string> keyset;
88  while (keyset.size() < num_keys) {
89  create_key(&key, min_length, max_length);
90  keyset.insert(key);
91  }
92  std::vector<std::string>(keyset.begin(), keyset.end()).swap(*keys);
93  std::random_shuffle(keys->begin(), keys->end());
94  }
95 }
96 
97 namespace test_dat_trie
98 {
99  const gchar *base_dir = NULL;
100 
101  void cut_setup(void)
102  {
103  std::srand(static_cast<unsigned int>(std::time(NULL)));
104 
105  base_dir = grn_test_get_tmp_dir();
106  cut_remove_path(base_dir, NULL);
107  g_mkdir_with_parents(base_dir, 0755);
108  }
109 
110  void cut_teardown(void)
111  {
112  if (base_dir) {
113  cut_remove_path(base_dir, NULL);
114  }
115  }
116 
117  void test_empty_trie(void)
118  {
119  grn::dat::Trie trie;
120  trie.create();
121 
122  cppcut_assert_equal(grn::dat::DEFAULT_FILE_SIZE, trie.file_size());
123  cppcut_assert_equal(grn::dat::UInt64(4236), trie.virtual_size());
124  cppcut_assert_equal(grn::dat::UInt32(0), trie.total_key_length());
125  cppcut_assert_equal(grn::dat::UInt32(0), trie.num_keys());
126  cppcut_assert_equal(grn::dat::UInt32(1), trie.min_key_id());
127  cppcut_assert_equal(grn::dat::UInt32(1), trie.next_key_id());
128  cppcut_assert_equal(grn::dat::UInt32(0), trie.max_key_id());
129  cppcut_assert_equal(grn::dat::UInt32(0), trie.num_keys());
130  cppcut_assert_equal(grn::dat::UInt32(17893), trie.max_num_keys());
131  cppcut_assert_equal(grn::dat::UInt32(512), trie.num_nodes());
132  cppcut_assert_equal(grn::dat::UInt32(511), trie.num_phantoms());
133  cppcut_assert_equal(grn::dat::UInt32(0), trie.num_zombies());
134  cppcut_assert_equal(grn::dat::UInt32(71680), trie.max_num_nodes());
135  cppcut_assert_equal(grn::dat::UInt32(1), trie.num_blocks());
136  cppcut_assert_equal(grn::dat::UInt32(140), trie.max_num_blocks());
137  cppcut_assert_equal(grn::dat::UInt32(0), trie.next_key_pos());
138  cppcut_assert_equal(grn::dat::UInt32(100439), trie.key_buf_size());
139  }
140 
141  void test_trie_on_memory(void)
142  {
143  std::vector<std::string> keys;
144  create_keys(&keys, 1000, 1, 16);
145 
146  grn::dat::Trie trie;
147  trie.create();
148 
149  for (std::size_t i = 0; i < keys.size(); ++i) {
150  cppcut_assert_equal(true,
151  trie.insert(keys[i].c_str(), keys[i].length()));
152  cppcut_assert_equal(true,
153  trie.search(keys[i].c_str(), keys[i].length()));
154  }
155  }
156 
157  void test_trie_on_file(void)
158  {
159  char trie_path[PATH_MAX];
160  std::strcpy(trie_path, base_dir);
161  std::strcat(trie_path, "/test_trie_on_file.dat");
162 
163  std::vector<std::string> keys;
164  create_keys(&keys, 1000, 1, 16);
165 
166  grn::dat::Trie trie;
167  trie.create(trie_path);
168 
169  for (std::size_t i = 0; i < keys.size(); ++i) {
170  cppcut_assert_equal(true,
171  trie.insert(keys[i].c_str(), keys[i].length()));
172  cppcut_assert_equal(true,
173  trie.search(keys[i].c_str(), keys[i].length()));
174  }
175 
176  grn::dat::Trie new_trie;
177  new_trie.open(trie_path);
178 
179  for (std::size_t i = 0; i < keys.size(); ++i) {
180  cppcut_assert_equal(false,
181  new_trie.insert(keys[i].c_str(), keys[i].length()));
182  cppcut_assert_equal(true,
183  new_trie.search(keys[i].c_str(), keys[i].length()));
184  }
185  }
186 
187  void test_insert(void)
188  {
189  std::vector<std::string> keys;
190  create_keys(&keys, 1000, 1, 16);
191 
192  grn::dat::Trie trie;
193  trie.create();
194 
195  std::size_t total_key_length = 0;
196  for (std::size_t i = 0; i < keys.size(); ++i) {
197  grn::dat::UInt32 key_pos;
198  cppcut_assert_equal(true,
199  trie.insert(keys[i].c_str(), keys[i].length(), &key_pos));
200 
201  const grn::dat::Key &key = trie.get_key(key_pos);
202  cppcut_assert_equal(true, key.is_valid());
203  cppcut_assert_equal(static_cast<grn::dat::UInt32>(i + 1), key.id());
204  cppcut_assert_equal(static_cast<grn::dat::UInt32>(keys[i].length()),
205  key.length());
206  cppcut_assert_equal(0,
207  std::memcmp(key.ptr(), keys[i].c_str(), key.length()));
208 
209  grn::dat::UInt32 key_pos_again;
210  cppcut_assert_equal(false,
211  trie.insert(keys[i].c_str(), keys[i].length(), &key_pos_again));
212  cppcut_assert_equal(key_pos, key_pos_again);
213 
214  total_key_length += keys[i].length();
215  cppcut_assert_equal(total_key_length,
216  static_cast<std::size_t>(trie.total_key_length()));
217  }
218  }
219 
220  void test_ith_key(void)
221  {
222  std::vector<std::string> keys;
223  create_keys(&keys, 1000, 1, 16);
224 
225  grn::dat::Trie trie;
226  trie.create();
227 
228  for (std::size_t i = 0; i < keys.size(); ++i) {
229  cppcut_assert_equal(false, trie.ith_key(i + 1).is_valid());
230 
231  grn::dat::UInt32 key_pos;
232  cppcut_assert_equal(true,
233  trie.insert(keys[i].c_str(), keys[i].length(), &key_pos));
234 
235  const grn::dat::Key &key_by_pos = trie.get_key(key_pos);
236  const grn::dat::Key &key_by_id = trie.ith_key(i + 1);
237  cppcut_assert_equal(&key_by_pos, &key_by_id);
238  }
239  }
240 
241  void test_search(void)
242  {
243  std::vector<std::string> keys;
244  create_keys(&keys, 1000, 1, 16);
245 
246  grn::dat::Trie trie;
247  trie.create();
248 
249  for (std::size_t i = 0; i < keys.size(); ++i) {
250  cppcut_assert_equal(false,
251  trie.search(keys[i].c_str(), keys[i].length()));
252 
253  grn::dat::UInt32 key_pos_inserted;
254  cppcut_assert_equal(true,
255  trie.insert(keys[i].c_str(), keys[i].length(), &key_pos_inserted));
256 
257  grn::dat::UInt32 key_pos_found;
258  cppcut_assert_equal(true,
259  trie.search(keys[i].c_str(), keys[i].length(), &key_pos_found));
260  cppcut_assert_equal(key_pos_inserted, key_pos_found);
261  }
262  }
263 
264  void test_lcp_search(void)
265  {
266  grn::dat::Trie trie;
267  trie.create();
268 
269  cppcut_assert_equal(true, trie.insert("012", 3));
270  cppcut_assert_equal(true, trie.insert("01234", 5));
271  cppcut_assert_equal(true, trie.insert("0123456", 7));
272 
273  cppcut_assert_equal(false, trie.lcp_search("01", 2));
274  cppcut_assert_equal(true, trie.lcp_search("012", 3));
275  cppcut_assert_equal(true, trie.lcp_search("0123", 4));
276  cppcut_assert_equal(false, trie.lcp_search("12345", 5));
277 
278  grn::dat::UInt32 key_pos = grn::dat::MAX_UINT32;
279 
280  cppcut_assert_equal(false, trie.lcp_search("01", 2, &key_pos));
281  cppcut_assert_equal(grn::dat::MAX_UINT32, key_pos);
282 
283  cppcut_assert_equal(true, trie.lcp_search("012", 3, &key_pos));
284  cppcut_assert_equal(true, trie.get_key(key_pos).is_valid());
285  cppcut_assert_equal(static_cast<grn::dat::UInt32>(1),
286  trie.get_key(key_pos).id());
287 
288  cppcut_assert_equal(true, trie.lcp_search("012345", 6, &key_pos));
289  cppcut_assert_equal(true, trie.get_key(key_pos).is_valid());
290  cppcut_assert_equal(static_cast<grn::dat::UInt32>(2),
291  trie.get_key(key_pos).id());
292 
293  cppcut_assert_equal(true, trie.lcp_search("0123456789", 10, &key_pos));
294  cppcut_assert_equal(true, trie.get_key(key_pos).is_valid());
295  cppcut_assert_equal(static_cast<grn::dat::UInt32>(3),
296  trie.get_key(key_pos).id());
297 
298  std::vector<std::string> keys;
299  create_keys(&keys, 1000, 1, 16);
300 
301  for (std::size_t i = 0; i < keys.size(); ++i) {
302  const char * const ptr = keys[i].c_str();
303  const uint32_t length = static_cast<uint32_t>(keys[i].length());
304  grn::dat::UInt32 key_pos_inserted;
305  trie.insert(ptr, length, &key_pos_inserted);
306 
307  grn::dat::UInt32 key_pos_found;
308  cppcut_assert_equal(true,
309  trie.lcp_search(ptr, length, &key_pos_found));
310  cppcut_assert_equal(key_pos_inserted, key_pos_found);
311  }
312  }
313 
314  void test_remove(void)
315  {
316  std::vector<std::string> keys;
317  create_keys(&keys, 1000, 1, 16);
318 
319  grn::dat::Trie trie;
320  trie.create();
321 
322  std::size_t total_key_length = 0;
323  for (std::size_t i = 0; i < keys.size(); ++i) {
324  cppcut_assert_equal(true,
325  trie.insert(keys[i].c_str(), keys[i].length()));
326  total_key_length += keys[i].length();
327  }
328  for (std::size_t i = 0; i < keys.size(); ++i) {
329  cppcut_assert_equal(static_cast<grn::dat::UInt32>(keys.size() - i),
330  trie.num_keys());
331  cppcut_assert_equal(true, trie.remove(i + 1));
332  cppcut_assert_equal(false, trie.ith_key(i + 1).is_valid());
333  cppcut_assert_equal(false,
334  trie.search(keys[i].c_str(), keys[i].length()));
335  cppcut_assert_equal(false, trie.remove(i + 1));
336 
337  total_key_length -= keys[i].length();
338  cppcut_assert_equal(total_key_length, static_cast<std::size_t>(trie.total_key_length()));
339  }
340 
341  for (std::size_t i = 0; i < keys.size(); ++i) {
342  cppcut_assert_equal(true,
343  trie.insert(keys[i].c_str(), keys[i].length()));
344  }
345  for (std::size_t i = 0; i < keys.size(); ++i) {
346  cppcut_assert_equal(true,
347  trie.remove(keys[i].c_str(), keys[i].length()));
348  cppcut_assert_equal(false, trie.ith_key(keys.size() - i).is_valid());
349  cppcut_assert_equal(false,
350  trie.search(keys[i].c_str(), keys[i].length()));
351  cppcut_assert_equal(false,
352  trie.remove(keys[i].c_str(), keys[i].length()));
353  }
354  }
355 
356  void test_update(void)
357  {
358  std::vector<std::string> keys;
359  create_keys(&keys, 1000, 1, 16);
360 
361  grn::dat::Trie trie;
362  trie.create();
363 
364  std::size_t total_key_length = 0;
365  for (std::size_t i = 0; i < (keys.size() / 2); ++i) {
366  cppcut_assert_equal(true,
367  trie.insert(keys[i].c_str(), keys[i].length()));
368  total_key_length += keys[i].length();
369  }
370  for (std::size_t i = (keys.size() / 2); i < keys.size(); ++i) {
371  const grn::dat::UInt32 key_id = i + 1 - (keys.size() / 2);
372  const std::string &src_key = keys[i - (keys.size() / 2)];
373  cppcut_assert_equal(true,
374  trie.update(key_id, keys[i].c_str(), keys[i].length()));
375  cppcut_assert_equal(true, trie.ith_key(key_id).is_valid());
376  cppcut_assert_equal(true,
377  trie.search(keys[i].c_str(), keys[i].length()));
378  cppcut_assert_equal(false,
379  trie.search(src_key.c_str(), src_key.length()));
380 
381  total_key_length += keys[i].length() - src_key.length();
382  cppcut_assert_equal(total_key_length, static_cast<std::size_t>(trie.total_key_length()));
383  }
384  for (std::size_t i = 0; i < (keys.size() / 2); ++i) {
385  const std::string &src_key = keys[i + (keys.size() / 2)];
386  cppcut_assert_equal(true,
387  trie.update(src_key.c_str(), src_key.length(),
388  keys[i].c_str(), keys[i].length()));
389  cppcut_assert_equal(true, trie.ith_key(i + 1).is_valid());
390  cppcut_assert_equal(true,
391  trie.search(keys[i].c_str(), keys[i].length()));
392  cppcut_assert_equal(false,
393  trie.search(src_key.c_str(), src_key.length()));
394 
395  total_key_length += keys[i].length() - src_key.length();
396  cppcut_assert_equal(total_key_length,
397  static_cast<std::size_t>(trie.total_key_length()));
398  }
399  }
400 
401  void test_create(void)
402  {
403  std::vector<std::string> keys;
404  create_keys(&keys, 1000, 1, 16);
405 
406  grn::dat::Trie src_trie;
407  src_trie.create();
408 
409  for (std::size_t i = 0; i < keys.size(); ++i) {
410  cppcut_assert_equal(true,
411  src_trie.insert(keys[i].c_str(), keys[i].length()));
412  }
413 
414  grn::dat::Trie dest_trie;
415  dest_trie.create(src_trie);
416 
417  for (std::size_t i = 0; i < keys.size(); ++i) {
418  cppcut_assert_equal(true,
419  dest_trie.search(keys[i].c_str(), keys[i].length()));
420  }
421 
422  cppcut_assert_equal(src_trie.file_size(), dest_trie.file_size());
423  cppcut_assert_equal(src_trie.total_key_length(),
424  dest_trie.total_key_length());
425  cppcut_assert_equal(src_trie.min_key_id(), dest_trie.min_key_id());
426  cppcut_assert_equal(src_trie.next_key_id(), dest_trie.next_key_id());
427  cppcut_assert_equal(src_trie.max_key_id(), dest_trie.max_key_id());
428  cppcut_assert_equal(src_trie.num_keys(), dest_trie.num_keys());
429  cppcut_assert_equal(src_trie.next_key_pos(), dest_trie.next_key_pos());
430 
431  cppcut_assert_operator(dest_trie.num_nodes(), <, src_trie.num_nodes());
432  cppcut_assert_equal(grn::dat::UInt32(0), dest_trie.num_zombies());
433  cppcut_assert_operator(dest_trie.num_blocks(), <, src_trie.num_nodes());
434  }
435 
436  void test_random_queries(void)
437  {
438  typedef std::stack<grn::dat::UInt32> Stack;
439  typedef std::map<std::string, grn::dat::UInt32> Keyset;
440 
441  grn::dat::Trie trie;
442  trie.create(NULL, 1 << 16);
443 
444  Keyset keyset;
445  Stack stack;
446  std::string str;
447  for (std::size_t i = 0; i < 1000; ++i) {
448  create_key(&str, 2, 3);
449  switch (static_cast<int>(4.0 * std::rand() / RAND_MAX)) {
450  case 0: {
451  const Keyset::const_iterator it = keyset.find(str);
452  const bool to_be_found = (it != keyset.end());
453  grn::dat::UInt32 key_pos;
454  const bool is_found =
455  trie.search(str.c_str(), str.length(), &key_pos);
456  cppcut_assert_equal(to_be_found, is_found);
457  if (is_found) {
458  const grn::dat::Key &key = trie.get_key(key_pos);
459  cppcut_assert_equal(it->second, key.id());
460  cppcut_assert_equal(static_cast<grn::dat::UInt32>(str.length()),
461  key.length());
462  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
463  key.str());
464  }
465  break;
466  }
467  case 1: {
468  const Keyset::iterator it = keyset.find(str);
469  const bool to_be_removed = (it != keyset.end());
470  const bool is_removed = trie.remove(str.c_str(), str.length());
471  cppcut_assert_equal(to_be_removed, is_removed);
472  if (is_removed) {
473  stack.push(it->second);
474  keyset.erase(it);
475  }
476  break;
477  }
478  case 2: {
479  const grn::dat::UInt32 key_id =
480  stack.empty() ? (keyset.size() + 1) : stack.top();
481  const std::pair<Keyset::iterator, bool> it_bool_pair =
482  keyset.insert(std::make_pair(str, key_id));
483  const bool to_be_inserted = it_bool_pair.second;
484  if (!stack.empty() && to_be_inserted) {
485  stack.pop();
486  }
487  grn::dat::UInt32 key_pos;
488  bool is_inserted = !to_be_inserted;
489  try {
490  is_inserted = trie.insert(str.c_str(), str.length(), &key_pos);
491  } catch (const grn::dat::SizeError &ex) {
492  trie.create(trie, NULL, trie.file_size() * 2);
493  is_inserted = trie.insert(str.c_str(), str.length(), &key_pos);
494  }
495  cppcut_assert_equal(to_be_inserted, is_inserted);
496  const grn::dat::Key &key = trie.get_key(key_pos);
497  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
498  key.str());
499  break;
500  }
501  default: {
502  const grn::dat::UInt32 key_id = (trie.max_key_id()) ?
503  ((std::rand() % trie.max_key_id()) + 1) : 0;
504  const grn::dat::Key &src_key = trie.ith_key(key_id);
505  const Keyset::iterator src_it = !src_key.is_valid() ? keyset.end() :
506  keyset.find(std::string(
507  static_cast<const char *>(src_key.ptr()), src_key.length()));
508  cppcut_assert_equal(src_it != keyset.end(), src_key.is_valid());
509  const bool to_be_updated = src_key.is_valid() &&
510  (keyset.find(str) == keyset.end());
511  grn::dat::UInt32 key_pos;
512  bool is_updated = !to_be_updated;
513  try {
514  is_updated = trie.update(key_id, str.c_str(), str.length(),
515  &key_pos);
516  } catch (const grn::dat::SizeError &ex) {
517  trie.create(trie, NULL, trie.file_size() * 2);
518  is_updated = trie.update(key_id, str.c_str(), str.length(),
519  &key_pos);
520  }
521  cppcut_assert_equal(to_be_updated, is_updated);
522  if (is_updated) {
523  const grn::dat::Key &key = trie.get_key(key_pos);
524  cppcut_assert_equal(key_id, key.id());
525  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
526  key.str());
527  keyset.erase(src_it);
528  keyset.insert(std::make_pair(str, key_id));
529  }
530  break;
531  }
532  }
533  }
534  }
535 
536  gpointer sub_test_multi_threaded_random_queries(gpointer data)
537  {
538  volatile Context * const context = static_cast<Context *>(data);
539  cut_set_current_test_context(context->cut_test_context);
540 
541  std::string str;
542  while (context->continue_flag) try {
543  const grn::dat::Trie * const trie = context->trie;
544  create_key(&str, 2, 3);
545  grn::dat::UInt32 key_pos;
546  if (trie->search(str.c_str(), str.length(), &key_pos)) {
547  const grn::dat::Key &key = trie->get_key(key_pos);
548  cppcut_assert_equal(str.length(),
549  static_cast<std::size_t>(key.length()));
550  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
551  key.str());
552  }
553  } catch (...) {
554  cut_fail("sub_test_multi_threaded_random_queries() failed.");
555  }
556  return NULL;
557  }
558 
559  void test_multi_threaded_random_queries(void)
560  {
561  typedef std::stack<grn::dat::UInt32> Stack;
562  typedef std::map<std::string, grn::dat::UInt32> Keyset;
563 
564  grn::dat::Trie tries[32];
565  grn::dat::Trie *trie = &tries[0];
566  trie->create(NULL, 1 << 16);
567 
568  Context context;
569  context.cut_test_context = cut_get_current_test_context();
570  context.trie = trie;
571  context.continue_flag = true;
572 
573  Thread threads[2];
574  for (std::size_t i = 0; i < (sizeof(threads) / sizeof(*threads)); ++i) {
575  threads[i].create(sub_test_multi_threaded_random_queries, &context);
576  }
577 
578  Keyset keyset;
579  Stack stack;
580  std::string str;
581  for (std::size_t i = 0; i < 1000; ++i) {
582  create_key(&str, 2, 3);
583  switch (static_cast<int>(4.0 * std::rand() / RAND_MAX)) {
584  case 0: {
585  const Keyset::const_iterator it = keyset.find(str);
586  const bool to_be_found = (it != keyset.end());
587  grn::dat::UInt32 key_pos;
588  const bool is_found =
589  trie->search(str.c_str(), str.length(), &key_pos);
590  cppcut_assert_equal(to_be_found, is_found);
591  if (is_found) {
592  const grn::dat::Key &key = trie->get_key(key_pos);
593  cppcut_assert_equal(it->second, key.id());
594  cppcut_assert_equal(static_cast<grn::dat::UInt32>(str.length()),
595  key.length());
596  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
597  key.str());
598  }
599  break;
600  }
601  case 1: {
602  const Keyset::iterator it = keyset.find(str);
603  const bool to_be_removed = (it != keyset.end());
604  const bool is_removed = trie->remove(str.c_str(), str.length());
605  cppcut_assert_equal(to_be_removed, is_removed);
606  if (is_removed) {
607  stack.push(it->second);
608  keyset.erase(it);
609  }
610  break;
611  }
612  case 2: {
613  const grn::dat::UInt32 key_id =
614  stack.empty() ? (keyset.size() + 1) : stack.top();
615  const std::pair<Keyset::iterator, bool> it_bool_pair =
616  keyset.insert(std::make_pair(str, key_id));
617  const bool to_be_inserted = it_bool_pair.second;
618  if (!stack.empty() && to_be_inserted) {
619  stack.pop();
620  }
621  grn::dat::UInt32 key_pos;
622  bool is_inserted = !to_be_inserted;
623  try {
624  is_inserted = trie->insert(str.c_str(), str.length(), &key_pos);
625  } catch (const grn::dat::SizeError &ex) {
626  (trie + 1)->create(*trie, NULL, trie->file_size() * 2);
627  context.trie = ++trie;
628  is_inserted = trie->insert(str.c_str(), str.length(), &key_pos);
629  }
630  cppcut_assert_equal(to_be_inserted, is_inserted);
631  const grn::dat::Key &key = trie->get_key(key_pos);
632  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
633  key.str());
634  break;
635  }
636  default: {
637  const grn::dat::UInt32 key_id = (trie->max_key_id()) ?
638  ((std::rand() % trie->max_key_id()) + 1) : 0;
639  const grn::dat::Key &src_key = trie->ith_key(key_id);
640  const Keyset::iterator src_it = !src_key.is_valid() ? keyset.end() :
641  keyset.find(std::string(
642  static_cast<const char *>(src_key.ptr()), src_key.length()));
643  cppcut_assert_equal(src_it != keyset.end(), src_key.is_valid());
644  const bool to_be_updated = src_key.is_valid() &&
645  (keyset.find(str) == keyset.end());
646  grn::dat::UInt32 key_pos;
647  bool is_updated = !to_be_updated;
648  try {
649  is_updated = trie->update(key_id, str.c_str(), str.length(),
650  &key_pos);
651  } catch (const grn::dat::SizeError &ex) {
652  (trie + 1)->create(*trie, NULL, trie->file_size() * 2);
653  context.trie = ++trie;
654  is_updated = trie->update(key_id, str.c_str(), str.length(),
655  &key_pos);
656  }
657  cppcut_assert_equal(to_be_updated, is_updated);
658  if (is_updated) {
659  const grn::dat::Key &key = trie->get_key(key_pos);
660  cppcut_assert_equal(key_id, key.id());
661  cppcut_assert_equal(grn::dat::String(str.c_str(), str.length()),
662  key.str());
663  keyset.erase(src_it);
664  keyset.insert(std::make_pair(str, key_id));
665  }
666  break;
667  }
668  }
669  }
670  context.continue_flag = false;
671  }
672 }
Generated on Sun Nov 10 2013 09:49:04 for Groonga 3.0.9 Source Code Document by   doxygen 1.8.1.2