Class: NativeBtree::Btree

Inherits:
Object
  • Object
show all
Defined in:
lib/native_btree/btree.rb,
ext/native_btree/native_btree.c

Overview

Main Btree class

Constant Summary collapse

INT_COMPARATOR =
Note:

Can be replaced with specific class in future releases

Represents native comparator for integer keys

int_comparator

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Btree

Constructor

Accepts block as “comparator” function. This function will recive two keys for comparison.



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'ext/native_btree/constructor.c', line 38

VALUE
rbtree_initialize(int argc, VALUE* argv, VALUE self)
{
  rb_check_arity(argc, 0, 1);

  EXTRACT_RBTREE_SELF(rbtree);

  gushort flags = 0;

  if (argc > 0) {
    flags = NUM2USHORT(argv[0]);
  }

  init_rbtree((RBTree *) rbtree, flags);

  return self;
}

Instance Method Details

#==(second) ⇒ Boolean

Checks if two trees are equal.

Compares with == method all keys and values from trees by order.

  • Returns false if number of keys are not equal.

  • Returns false if one keys or one values pair are not equal.

  • Returns true if all keys and values are equal.

Parameters:

Returns:

  • (Boolean) —

    result



292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
 
# File 'ext/native_btree/instance.c', line 292

VALUE
rbtree_equal(VALUE self, VALUE second)
{
  EXTRACT_RBTREE_SELF(rbtree);
  EXTRACT_RBTREE(second, rbtree2);

  gint self_size = g_tree_nnodes(rbtree->gtree);
  gint second_size = g_tree_nnodes(rbtree2->gtree);

  VALUE result = Qfalse;

  if (self_size != second_size) {
    goto ret;
  }

  if (self_size == 0) {
    result = Qtrue;
    goto ret;
  }

#ifdef HAS_GTREE_NODE
  if (rbtree_compare_trees(rbtree, rbtree2)) {
    result = Qtrue;
  }
#else
  if (legacy_rbtree_compare(rbtree, rbtree2)) {
    result = Qtrue;
  }
#endif

  ret:
  return result;
}

#[](key) ⇒ Object Also known as: get

Gets value by key from tree.

  • Returns nil if key does not exist.

Parameters:

  • key (Object)

Returns:

  • (Object) —

    result



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'ext/native_btree/instance.c', line 140

VALUE
rbtree_get(VALUE self, VALUE key)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gpointer found = g_tree_lookup(rbtree->gtree, (gpointer) key);

  if (found == NULL) {
    return Qnil;
  }

  VALUE result = (VALUE) found;

  return result;
}

#[]=(key, value) ⇒ Btree Also known as: set

Adds key/value pair in to tree.

Key/value will be replaced if key already exists.

Parameters:

  • key (Object)
  • value (Object)

Returns:



122
123
124
125
126
127
128
129
130
 
# File 'ext/native_btree/instance.c', line 122

VALUE
rbtree_set(VALUE self, VALUE key, VALUE value)
{
  EXTRACT_RBTREE_SELF(rbtree);

  g_tree_replace(rbtree->gtree, (gpointer) key, (gpointer) value);

  return self;
}

#clear ⇒ Btree

Remove all nodes from tree.

Returns:



230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'ext/native_btree/instance.c', line 230

VALUE
rbtree_clear(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  #ifdef HAS_GTREE_REMOVE_ALL
    g_tree_remove_all(rbtree->gtree);
  #else
    g_tree_foreach(rbtree->gtree, rbtree_remove_node, (gpointer) rbtree);
  #endif

  return self;
}

#delete(key) ⇒ Object

Deletes key/value pair from tree.

  • Returns value if key exists

  • Returns nil if key does not exists

  • Returns result of block if block was given

Parameters:

  • key (Object) —

    Key

Returns:

  • (Object) —

    result



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# File 'ext/native_btree/instance.c', line 166

VALUE
rbtree_delete(VALUE self, VALUE key)
{
  EXTRACT_RBTREE_SELF(rbtree);

  VALUE found_key, found_value;
  gboolean found = g_tree_lookup_extended(
    rbtree->gtree,
    (gconstpointer) key,
    (gpointer *) &found_key,
    (gpointer *) &found_value
  );

  if (found) {
    g_tree_remove(rbtree->gtree, (gconstpointer) key);

    return found_value;
  }
  else {
    if (rb_block_given_p()) {
      return rb_yield(key);
    }

    return Qnil;
  }
}

#delete_if ⇒ Btree

Deletes key/value pair from tree by result of block.

Will execute block for each key/value pairs and delete them if block returns true

Returns:



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
 
# File 'ext/native_btree/iterators.c', line 176

VALUE
rbtree_delete_if(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  GPtrArray *to_delete = g_ptr_array_new();

  RETURN_SIZED_ENUMERATOR(self, 0, 0, rbtree_enum_length);

  VALUE block = rb_block_proc();

  RBTreeSearchContext context = {
    block,
    NULL,
    0,
    0,
    to_delete
  };

  g_tree_foreach(rbtree->gtree, rbtree_delete_if_cb, &context);

  for (guint i = 0; i < to_delete->len; i++) {
    g_tree_remove(rbtree->gtree, g_ptr_array_index(to_delete, i));
  }

  g_ptr_array_free(to_delete, TRUE);

  return self;
}

#each ⇒ Btree

Execute block for each key/value pairs

Returns:



56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'ext/native_btree/iterators.c', line 56

VALUE
rbtree_each(VALUE self)
{
  RETURN_SIZED_ENUMERATOR(self, 0, 0, rbtree_enum_length);

  EXTRACT_RBTREE_SELF(rbtree);

  VALUE block = rb_block_proc();

  g_tree_foreach(rbtree->gtree, foraech_callbac, (gpointer) block);

  return self;
}

#each_key ⇒ Btree

Execute block for each key

Returns:



75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'ext/native_btree/iterators.c', line 75

VALUE
rbtree_each_key(VALUE self)
{
  RETURN_SIZED_ENUMERATOR(self, 0, 0, rbtree_enum_length);

  EXTRACT_RBTREE_SELF(rbtree);

  VALUE block = rb_block_proc();

  g_tree_foreach(rbtree->gtree, foraech_key_callbac, (gpointer) block);

  return self;
}

#each_value ⇒ Btree

Execute block for each value

Returns:



94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'ext/native_btree/iterators.c', line 94

VALUE
rbtree_each_value(VALUE self)
{
  RETURN_SIZED_ENUMERATOR(self, 0, 0, rbtree_enum_length);

  EXTRACT_RBTREE_SELF(rbtree);

  VALUE block = rb_block_proc();

  g_tree_foreach(rbtree->gtree, foraech_value_callbac, (gpointer) block);

  return self;
}

#empty? ⇒ Boolean

Checks that self tree is empty.

Returns:

  • (Boolean) —

    result



270
271
272
273
274
275
276
277
278
 
# File 'ext/native_btree/instance.c', line 270

VALUE
rbtree_is_empty(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gint size = g_tree_nnodes(rbtree->gtree);

  return size > 0 ? Qfalse : Qtrue;
}

#filter ⇒ Btree Also known as: select

Filters btree by block call

If block returns true, key/value will include in result tree

Returns:



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'ext/native_btree/search.c', line 53

VALUE
rbtree_filter(VALUE self)
{
  rb_need_block();
  EXTRACT_RBTREE_SELF(rbtree);

  VALUE block = rb_block_proc();

  VALUE new_tree = rbtree_clone_wrap(rbtree);

  EXTRACT_RBTREE(new_tree, new_rbtree);

  RBTreeSearchContext data = {
    block,
    new_rbtree,
    0,
    0,
    NULL
  };

  g_tree_foreach(rbtree->gtree, filter_callback, &data);

  return new_tree;
}

#filter! ⇒ Btree Also known as: select!

Filters btree by block call

Same as #filter but returns changed self.

Returns:



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'ext/native_btree/search.c', line 85

VALUE
rbtree_filter_bang(VALUE self)
{
  rb_need_block();
  EXTRACT_RBTREE_SELF(rbtree);

  VALUE block = rb_block_proc();

  GPtrArray *to_remove = g_ptr_array_new();

  RBTreeSearchContext data = {
    block,
    NULL,
    0,
    0,
    (gconstpointer) to_remove
  };

  g_tree_foreach(rbtree->gtree, filter_bang_callback, &data);

  for (size_t i = 0; i < to_remove->len; i++) {
    g_tree_remove(rbtree->gtree, g_ptr_array_index(to_remove, i));
  }

  g_ptr_array_free(to_remove, TRUE);

  return self;
}

#first ⇒ Object Also known as: min

Returns value from smallest key

Returns:

  • (Object) —

    result



331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
 
# File 'ext/native_btree/instance.c', line 331

VALUE
rbtree_first(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

#ifdef HAS_GTREE_NODE
  GTreeNode *node = g_tree_node_first(rbtree->gtree);

  if (!node) {
    return Qnil;
  }

  return (VALUE) g_tree_node_value(node);
#else
  RBTreeSearchContext context = {
    Qnil,
    NULL,
    1,
    0,
    NULL
  };

  g_tree_foreach(rbtree->gtree, rbtree_first_cb, &context);

  if (context.counter) {
    return Qnil;
  }

  return (VALUE) context.something;
#endif
}

#height ⇒ Integer

Returns tree height

Returns:

  • (Integer) —

    maximum nodes in path from root to leaf



198
199
200
201
202
203
204
205
206
207
 
# File 'ext/native_btree/instance.c', line 198

VALUE
rbtree_height(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gint size = g_tree_height(rbtree->gtree);
  VALUE result = INT2NUM(size);

  return result;
}

#include?(key) ⇒ Boolean

Checks that the given key is in the tree.

Parameters:

  • key (Object)

Returns:

  • (Boolean) —

    result



251
252
253
254
255
256
257
258
259
260
261
262
263
 
# File 'ext/native_btree/instance.c', line 251

VALUE
rbtree_is_include(VALUE self, VALUE key)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gpointer exists = g_tree_lookup(rbtree->gtree, (gconstpointer) key);

  if (exists == NULL) {
    return Qfalse;
  }

  return Qtrue;
}

#last ⇒ Object Also known as: max

Returns value from largest key

Returns:

  • (Object) —

    result



368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
 
# File 'ext/native_btree/instance.c', line 368

VALUE
rbtree_last(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

#ifdef HAS_GTREE_NODE
  GTreeNode *node = g_tree_node_last(rbtree->gtree);

  if (!node) {
    return Qnil;
  }

  return (VALUE) g_tree_node_value(node);
#else
  RBTreeSearchContext context = {
    Qnil,
    NULL,
    0,
    0,
    NULL
  };

  g_tree_foreach(rbtree->gtree, rbtree_last_cb, &context);

  if (!context.counter) {
    return Qnil;
  }

  return (VALUE) context.something;
#endif
}

#reverse_each ⇒ Btree

Execute block for each key/value pairs in reverse order

Returns:



113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'ext/native_btree/iterators.c', line 113

VALUE
rbtree_reverse_each(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  RETURN_SIZED_ENUMERATOR(self, 0, 0, rbtree_enum_length);

#ifdef HAS_GTREE_NODE
  GTreeNode *current = g_tree_node_last(rbtree->gtree);

  VALUE key, val;
  while (current) {
    key = (VALUE) g_tree_node_key(current);
    val = (VALUE) g_tree_node_value(current);

    rb_yield_values(2, val, key);

    current = g_tree_node_previous(current);
  }
#else
  GPtrArray *buff = rbtree_to_ptr_array(rbtree);

  VALUE key, val;
  for (glong i = buff->len - 1; i > 0; i--) {
    val = (VALUE) g_ptr_array_index(buff, i);
    key = (VALUE) g_ptr_array_index(buff, --i);

    rb_yield_values(2, val, key);
  }

  g_ptr_array_free(buff, TRUE);
#endif

  return self;
}

#select_after ⇒ Object

#select_before ⇒ Object

#size ⇒ Integer

Returns number of nodes

Returns:

  • (Integer) —

    number of nodes



214
215
216
217
218
219
220
221
222
223
 
# File 'ext/native_btree/instance.c', line 214

VALUE
rbtree_size(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gint size = g_tree_nnodes(rbtree->gtree);
  VALUE result = INT2NUM(size);

  return result;
}

#to_a ⇒ Array

Converts tree to array

Coverts tree to array of arrays with key and value

Returns:

  • (Array) —

    result



53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'ext/native_btree/conversion.c', line 53

VALUE
rbtree_to_a(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  gint tree_size = g_tree_nnodes(rbtree->gtree);

  VALUE array = rb_ary_new2(tree_size);

  g_tree_foreach(rbtree->gtree, rbtree_to_a_callback, (gpointer) array);

  return array;
}

#to_h ⇒ Hash

Converts tree to Hash

Returns:

  • (Hash) —

    result



34
35
36
37
38
39
40
41
42
43
44
 
# File 'ext/native_btree/conversion.c', line 34

VALUE
rbtree_to_h(VALUE self)
{
  EXTRACT_RBTREE_SELF(rbtree);

  VALUE hash = rb_hash_new();

  g_tree_foreach(rbtree->gtree, rbtree_to_h_callback, (gpointer) hash);

  return hash;
}

#to_proc ⇒ Proc

Returns a Proc object that maps a key to its value

Returns:

  • (Proc) —

    block



88
89
90
91
92
 
# File 'ext/native_btree/conversion.c', line 88

VALUE
rbtree_to_proc(VALUE self)
{
  return rb_proc_new(to_proc_proc, self);
}

#to_s ⇒ String Also known as: inspect

Converts tree to string.

Under hood will convert tree to Hash.

Returns:

  • (String) —

    result



101
102
103
104
105
106
107
108
109
 
# File 'ext/native_btree/conversion.c', line 101

VALUE
rbtree_to_s(VALUE self)
{
  VALUE h = rbtree_to_h(self);

  VALUE str = rb_sprintf("#<NativeBtree::Btree:%"PRIsVALUE">", h);

  return str;
}