1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2 /*
3 * Copyright 2008
4 *
5 * This library is free software: you can redistribute it and/or modify it
6 * under the terms of the GNU Lesser General Public License as published by
7 * the Free Software Foundation.
8 *
9 * This library is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
11 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
12 * for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library. If not, see <http://www.gnu.org/licenses/>.
16 *
17 * Authors: Stanislav Slusny <slusnys@gmail.com>
18 */
19
20 /**
21 * SECTION: e-cal-backend-intervaltree
22 * @include: libedata-cal/libedata-cal.h
23 * @short_description: A utility for calculating intervals and recurrances
24 *
25 * Implementation of the interval node as described in Introduction to
26 * Algorithms book by Cormen et al, chapter 14.3.
27 *
28 * Basically, the interval tree is the red-black tree, the node key is
29 * the start of the interval.
30 */
31
32 #include "evolution-data-server-config.h"
33
34 #include <stdio.h>
35 #include <string.h>
36
37 #include "e-cal-backend-intervaltree.h"
38
39 #define d(x) x
40
41 #define _TIME_MIN ((time_t) 0) /* Min valid time_t */
42 #define _TIME_MAX ((time_t) INT_MAX) /* Max valid time_t */
43 #define DIRECTION_GO_LEFT 0
44 #define DIRECTION_GO_RIGHT 1
45
46 typedef struct _EIntervalNode EIntervalNode;
47
48 static EIntervalNode *
49 intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x);
50
51 struct _EIntervalNode {
52 /* start of the interval - the key of the node */
53 time_t start;
54 /* end of the interval */
55 time_t end;
56 /* maximum value of any interval stored in subtree rooted at node */
57 time_t max;
58 /* minimum value of any interval stored in subtree rooted at node */
59 time_t min;
60 /* color of the node (red or black) */
61 gboolean red;
62
63 ECalComponent *comp;
64
65 /* left child */
66 EIntervalNode * left;
67 /* right child */
68 EIntervalNode * right;
69 EIntervalNode * parent;
70 };
71
72 struct _EIntervalTreePrivate {
73 EIntervalNode *root;
74 EIntervalNode *nil;
75 GHashTable *id_node_hash;
76 GRecMutex mutex;
77 };
78
G_DEFINE_TYPE_WITH_PRIVATE(EIntervalTree,e_intervaltree,G_TYPE_OBJECT)79 G_DEFINE_TYPE_WITH_PRIVATE (EIntervalTree, e_intervaltree, G_TYPE_OBJECT)
80
81 static inline gint
82 get_direction (EIntervalNode *x,
83 time_t z_start,
84 time_t z_end)
85 {
86 if (x->start == z_start)
87 return x->end > z_end;
88
89 if (x->start > z_start)
90 return DIRECTION_GO_LEFT;
91 else
92 return DIRECTION_GO_RIGHT;
93 }
94
95 static inline gchar *
component_key(const gchar * uid,const gchar * rid)96 component_key (const gchar *uid,
97 const gchar *rid)
98 {
99 if (rid)
100 return g_strdup_printf ("%s_%s", uid, rid);
101 else
102 return g_strdup_printf ("%s", uid);
103 }
104
105 /**
106 * compare_intervals:
107 *
108 * Compares two intervals.
109 *
110 * Returns: 0 if interval overlaps, -1 if first interval ends before
111 * the second starts, 1 otherwise.
112 *
113 **/
114 static inline gint
compare_intervals(time_t x_start,time_t x_end,time_t y_start,time_t y_end)115 compare_intervals (time_t x_start,
116 time_t x_end,
117 time_t y_start,
118 time_t y_end)
119 {
120 /* assumption: x_start <= x_end */
121 /* assumption: y_start <= y_end */
122
123 /* x is left of y */
124 if (x_end < y_start)
125 return -1;
126
127 /* x is right of y */
128 if (y_end < x_start)
129 return 1;
130
131 /* x and y overlap */
132 return 0;
133 }
134
135 /**
136 * left_rotate:
137 * @tree: interval tree
138 * @x: Node, where will be applied the operation
139 *
140 * Carry out left rotation on the node @x in tree @tree.
141 * Caller should hold the lock
142 **/
143 static void
left_rotate(EIntervalTree * tree,EIntervalNode * x)144 left_rotate (EIntervalTree *tree,
145 EIntervalNode *x)
146 {
147 EIntervalNode *y;
148 EIntervalNode *nil;
149
150 g_return_if_fail (E_IS_INTERVALTREE (tree));
151 g_return_if_fail (x != NULL);
152
153 nil = tree->priv->nil;
154 y = x->right;
155 x->right = y->left;
156
157 if (y->left != nil)
158 y->left->parent = x;
159
160 y->parent = x->parent;
161
162 /* instead of checking if x->parent is the root as in the book, we */
163 /* count on the root sentinel to implicitly take care of this case */
164 if (x == x->parent->left)
165 x->parent->left = y;
166 else
167 x->parent->right = y;
168
169 y->left = x;
170 x->parent = y;
171
172 /* update max and min field */
173 x->max = MAX (x->left->max, MAX (x->end, x->right->max));
174 y->max = MAX (x->max, MAX (y->end, y->right->max));
175 x->min = MIN (x->left->min, x->start);
176 y->min = MIN (x->min, y->start);
177 }
178
179 /**
180 * right_rotate:
181 * @tree: interval tree
182 * @y: Node, where will be applied the operation
183 *
184 * Carry out right rotation on the node @y in tree @tree.
185 * Caller should hold the lock
186 **/
187 static void
right_rotate(EIntervalTree * tree,EIntervalNode * y)188 right_rotate (EIntervalTree *tree,
189 EIntervalNode *y)
190 {
191 EIntervalNode *x;
192 EIntervalNode *nil;
193
194 g_return_if_fail (E_IS_INTERVALTREE (tree));
195 g_return_if_fail (y != NULL);
196
197 nil = tree->priv->nil;
198 x = y->left;
199 y->left = x->right;
200
201 if (nil != x->right)
202 x->right->parent = y;
203
204 x->parent = y->parent;
205
206 if (y == y->parent->left)
207 y->parent->left = x;
208 else
209 y->parent->right = x;
210
211 x->right = y;
212 y->parent = x;
213
214 /* update max and min field */
215 y->max = MAX (y->left->max, MAX (y->right->max, y->end));
216 x->max = MAX (x->left->max, MAX (y->max, x->end));
217 y->min = MIN (y->left->min, y->start);
218 x->min = MIN (x->left->min, x->start);
219 }
220
221 static void
fixup_min_max_fields(EIntervalTree * tree,EIntervalNode * node)222 fixup_min_max_fields (EIntervalTree *tree,
223 EIntervalNode *node)
224 {
225 while (node && node != tree->priv->root) {
226 node->max = MAX (node->end, MAX (node->left->max, node->right->max));
227 node->min = MIN (node->start, node->left->min);
228
229 node = node->parent;
230 }
231 }
232
233 /* Caller should hold the lock */
234 static void
binary_tree_insert(EIntervalTree * tree,EIntervalNode * z)235 binary_tree_insert (EIntervalTree *tree,
236 EIntervalNode *z)
237 {
238 EIntervalNode *x;
239 EIntervalNode *y;
240 EIntervalNode *nil;
241
242 g_return_if_fail (E_IS_INTERVALTREE (tree));
243 g_return_if_fail (z != NULL);
244
245 nil = tree->priv->nil;
246
247 z->left = z->right = nil;
248 y = tree->priv->root;
249 x = tree->priv->root->left;
250
251 while (x != nil) {
252 y = x;
253
254 if (get_direction (x, z->start, z->end) == DIRECTION_GO_LEFT)
255 x = x->left;
256 else
257 x = x->right;
258 }
259
260 z->parent = y;
261
262 if ((y == tree->priv->root) || (get_direction (y, z->start, z->end) == DIRECTION_GO_LEFT))
263 y->left = z;
264 else
265 y->right = z;
266
267 /* update min and max fields */
268 y->min = MIN (y->left->min, y->start);
269 y->max = MAX (y->left->max, MAX (y->end, y->right->max));
270 }
271
272 static EIntervalNode *
intervaltree_node_next(EIntervalTree * tree,EIntervalNode * x)273 intervaltree_node_next (EIntervalTree *tree,
274 EIntervalNode *x)
275 {
276 EIntervalNode *y, *nil, *root;
277
278 g_return_val_if_fail (E_IS_INTERVALTREE (tree), NULL);
279 g_return_val_if_fail (x != NULL, NULL);
280
281 g_return_val_if_fail (x != tree->priv->nil, NULL);
282
283 nil = tree->priv->nil;
284 root = tree->priv->root;
285
286 if (nil != (y = x->right)) {
287 /* find out minimum of right subtree of x (assignment to y is ok) */
288 while (y->left != nil)
289 y = y->left;
290
291 return y;
292 }
293
294 y = x->parent;
295
296 while (x == y->right) {
297 x = y;
298 y = y->parent;
299 }
300
301 if (y == root)
302 return nil;
303
304 return y;
305 }
306
307 /* Caller should hold the lock */
308 static void
intervaltree_fixup_deletion(EIntervalTree * tree,EIntervalNode * x)309 intervaltree_fixup_deletion (EIntervalTree *tree,
310 EIntervalNode *x)
311 {
312 EIntervalNode *root = tree->priv->root->left;
313 EIntervalNode *w;
314
315 while ((!x->red) && (root != x)) {
316 if (!x->parent)
317 break;
318
319 if (x == x->parent->left) {
320 w = x->parent->right;
321
322 if (w->red) {
323 w->red = FALSE;
324 x->parent->red = TRUE;
325 left_rotate (tree, x->parent);
326 w = x->parent->right;
327 }
328
329 if ((!w->right->red) && (!w->left->red)) {
330 w->red = TRUE;
331 x = x->parent;
332 } else {
333 if (!w->right->red) {
334 w->left->red = FALSE;
335 w->red = TRUE;
336 right_rotate (tree, w);
337 w = x->parent->right;
338 }
339
340 w->red = x->parent->red;
341 x->parent->red = FALSE;
342 w->right->red = FALSE;
343 left_rotate (tree, x->parent);
344 x = root; /* this is to exit while loop */
345 }
346 } else {
347 w = x->parent->left;
348
349 if (w->red) {
350 w->red = FALSE;
351 x->parent->red = TRUE;
352 right_rotate (tree, x->parent);
353 w = x->parent->left;
354 }
355
356 if ((!w->right->red) && (!w->left->red)) {
357 w->red = TRUE;
358 x = x->parent;
359 } else {
360 if (!w->left->red) {
361 w->right->red = FALSE;
362 w->red = TRUE;
363 left_rotate (tree, w);
364 w = x->parent->left;
365 }
366
367 w->red = x->parent->red;
368 x->parent->red = FALSE;
369 w->left->red = FALSE;
370 right_rotate (tree, x->parent);
371 x = root; /* this is to exit while loop */
372 }
373 }
374 }
375
376 x->red = 0;
377 }
378
379 /* * Caller should hold the lock. * */
380 static EIntervalNode *
intervaltree_search_component(EIntervalTree * tree,const gchar * searched_uid,const gchar * searched_rid)381 intervaltree_search_component (EIntervalTree *tree,
382 const gchar *searched_uid,
383 const gchar *searched_rid)
384 {
385 EIntervalNode *node;
386 gchar *key;
387
388 g_return_val_if_fail (E_IS_INTERVALTREE (tree), NULL);
389 g_return_val_if_fail (searched_uid != NULL, NULL);
390
391 if (!searched_uid) {
392 g_warning (
393 "Searching the interval tree, the component "
394 " does not have a valid UID skipping it\n");
395
396 return NULL;
397 }
398
399 key = component_key (searched_uid, searched_rid);
400 node = g_hash_table_lookup (tree->priv->id_node_hash, key);
401 g_free (key);
402
403 return node;
404 }
405
406 static void
intervaltree_finalize(GObject * object)407 intervaltree_finalize (GObject *object)
408 {
409 EIntervalTreePrivate *priv;
410
411 priv = E_INTERVALTREE (object)->priv;
412
413 g_free (priv->root);
414 g_free (priv->nil);
415
416 if (priv->id_node_hash != NULL)
417 g_hash_table_destroy (priv->id_node_hash);
418
419 g_rec_mutex_clear (&priv->mutex);
420
421 /* Chain up to parent's finalize() method. */
422 G_OBJECT_CLASS (e_intervaltree_parent_class)->finalize (object);
423 }
424
425 static void
e_intervaltree_class_init(EIntervalTreeClass * class)426 e_intervaltree_class_init (EIntervalTreeClass *class)
427 {
428 GObjectClass *object_class;
429
430 object_class = G_OBJECT_CLASS (class);
431 object_class->finalize = intervaltree_finalize;
432 }
433
434 static void
e_intervaltree_init(EIntervalTree * tree)435 e_intervaltree_init (EIntervalTree *tree)
436 {
437 EIntervalNode *root, *nil;
438
439 tree->priv = e_intervaltree_get_instance_private (tree);
440
441 tree->priv->nil = nil = g_new (EIntervalNode, 1);
442 nil->parent = nil->left = nil->right = nil;
443 nil->red = FALSE;
444 nil->start = nil->end = nil->max = _TIME_MIN;
445 nil->min = _TIME_MAX;
446
447 tree->priv->root = root = g_new (EIntervalNode, 1);
448 root->parent = root->left = root->right = nil;
449 root->red = FALSE;
450 root->start = _TIME_MAX;
451 root->end = 0;
452 root->max = _TIME_MAX;
453 root->min = _TIME_MIN;
454
455 g_rec_mutex_init (&tree->priv->mutex);
456
457 tree->priv->id_node_hash = g_hash_table_new_full (
458 (GHashFunc) g_str_hash,
459 (GEqualFunc) g_str_equal,
460 (GDestroyNotify) g_free,
461 (GDestroyNotify) NULL);
462 }
463
464 /**
465 * e_intervaltree_new:
466 *
467 * Creates a new #EIntervalTree.
468 *
469 * Returns: The newly-created #EIntervalTree.
470 *
471 * Since: 2.32
472 **/
473 EIntervalTree *
e_intervaltree_new(void)474 e_intervaltree_new (void)
475 {
476 return g_object_new (E_TYPE_INTERVALTREE, NULL);
477 }
478
479 /**
480 * e_intervaltree_insert:
481 * @tree: interval tree
482 * @start: start of the interval
483 * @end: end of the interval
484 * @comp: Component
485 *
486 * Since: 2.32
487 **/
488 gboolean
e_intervaltree_insert(EIntervalTree * tree,time_t start,time_t end,ECalComponent * comp)489 e_intervaltree_insert (EIntervalTree *tree,
490 time_t start,
491 time_t end,
492 ECalComponent *comp)
493 {
494 EIntervalNode *y;
495 EIntervalNode *x;
496 EIntervalNode *newNode;
497 const gchar *uid;
498 gchar *rid;
499
500 g_return_val_if_fail (E_IS_INTERVALTREE (tree), FALSE);
501 g_return_val_if_fail (E_IS_CAL_COMPONENT (comp), FALSE);
502
503 g_rec_mutex_lock (&tree->priv->mutex);
504
505 uid = e_cal_component_get_uid (comp);
506 rid = e_cal_component_get_recurid_as_string (comp);
507 e_intervaltree_remove (tree, uid, rid);
508
509 x = g_new (EIntervalNode, 1);
510 x->min = x->start = start;
511 x->max = x->end = end;
512 x->comp = g_object_ref (comp);
513
514 binary_tree_insert (tree, x);
515 newNode = x;
516 x->red = TRUE;
517
518 fixup_min_max_fields (tree, x->parent);
519 while (x->parent->red) {
520 /* use sentinel instead of checking for root */
521 if (x->parent == x->parent->parent->left) {
522 y = x->parent->parent->right;
523
524 if (y->red) {
525 x->parent->red = FALSE;
526 y->red = FALSE;
527 x->parent->parent->red = TRUE;
528 x = x->parent->parent;
529 } else {
530 if (x == x->parent->right) {
531 x = x ->parent;
532 left_rotate (tree, x);
533 }
534
535 x->parent->red = FALSE;
536 x->parent->parent->red = TRUE;
537 right_rotate (tree, x->parent->parent);
538 }
539 } else {
540 /* case for x->parent == x->parent->parent->right */
541 y = x->parent->parent->left;
542
543 if (y->red) {
544 x->parent->red = FALSE;
545 y->red = FALSE;
546 x->parent->parent->red = TRUE;
547 x = x->parent->parent;
548 } else {
549 if (x == x->parent->left) {
550 x = x->parent;
551 right_rotate (tree, x);
552 }
553
554 x->parent->red = FALSE;
555 x->parent->parent->red = TRUE;
556 left_rotate (tree, x->parent->parent);
557 }
558 }
559 }
560
561 tree->priv->root->left->red = FALSE;
562 g_hash_table_insert (
563 tree->priv->id_node_hash,
564 component_key (uid, rid), newNode);
565 g_free (rid);
566
567 g_rec_mutex_unlock (&tree->priv->mutex);
568
569 return TRUE;
570 }
571
572 /**
573 * e_intervaltree_remove:
574 * @tree: an #EIntervalTree
575 * @uid: the uid of the component to remove
576 * @rid: the recurrance id of the component to remove
577 *
578 * Since: 2.32
579 **/
580 gboolean
e_intervaltree_remove(EIntervalTree * tree,const gchar * uid,const gchar * rid)581 e_intervaltree_remove (EIntervalTree *tree,
582 const gchar *uid,
583 const gchar *rid)
584 {
585 EIntervalNode *y = NULL;
586 EIntervalNode *x = NULL;
587 EIntervalNode *z = NULL;
588 EIntervalNode *nil, *root;
589 gchar *key;
590
591 g_return_val_if_fail (E_IS_INTERVALTREE (tree), FALSE);
592
593 nil = tree->priv->nil;
594 root = tree->priv->root;
595 g_rec_mutex_lock (&tree->priv->mutex);
596
597 z = intervaltree_search_component (tree, uid, rid);
598
599 if (!z || z == nil) {
600 g_rec_mutex_unlock (&tree->priv->mutex);
601 return FALSE;
602 }
603
604 y = ((z->left == nil) || (z->right == nil)) ? z :
605 intervaltree_node_next (tree, z);
606 g_return_val_if_fail (y, FALSE);
607 x = (y->left == nil) ? y->right : y->left;
608 g_return_val_if_fail (x, FALSE);
609 /* y is to be spliced out. x is its only child */
610
611 x->parent = y->parent;
612
613 if (root && root == x->parent)
614 root->left = x;
615 else if (y->parent) {
616 if (y == y->parent->left)
617 y->parent->left = x;
618 else
619 y->parent->right = x;
620 }
621
622 if (z && y != z) {
623 /* y (the succesor of z) is the node to be spliced out */
624 g_return_val_if_fail (y != tree->priv->nil, FALSE);
625
626 y->max = _TIME_MIN;
627 y->min = _TIME_MAX;
628 y->left = z->left;
629 y->right = z->right;
630 y->parent = z->parent;
631 z->left->parent = z->right->parent = y;
632
633 if (z->parent) {
634 if (z == z->parent->left)
635 z->parent->left = y;
636 else
637 z->parent->right = y;
638
639 }
640
641 fixup_min_max_fields (tree, x->parent);
642
643 if (!(y->red)) {
644 y->red = z->red;
645 intervaltree_fixup_deletion (tree, x);
646 }
647 else
648 y->red = z->red;
649 } else {
650 /* z is the node to be spliced out */
651
652 fixup_min_max_fields (tree, x->parent);
653
654 if (!(y->red))
655 intervaltree_fixup_deletion (tree, x);
656 }
657
658 key = component_key (uid, rid);
659 g_hash_table_remove (tree->priv->id_node_hash, key);
660 g_free (key);
661
662 g_object_unref (z->comp);
663 g_free (z);
664 g_rec_mutex_unlock (&tree->priv->mutex);
665
666 return TRUE;
667 }
668
669 /**
670 * e_intervaltree_search:
671 * @tree: interval tree
672 * @start: start of the interval
673 * @end: end of the interval
674 *
675 * Returns: (element-type ECalComponent) (nullable) (transfer full): list of #ECalComponent-s
676 * that overlap given interval, or %NULL.
677 *
678 * Since: 2.32
679 **/
680 GList *
e_intervaltree_search(EIntervalTree * tree,time_t start,time_t end)681 e_intervaltree_search (EIntervalTree *tree,
682 time_t start,
683 time_t end)
684 {
685 EIntervalNode *node;
686 GList *list = NULL;
687 GList *stack_start = NULL, *pos;
688
689 g_return_val_if_fail (E_IS_INTERVALTREE (tree), NULL);
690
691 g_rec_mutex_lock (&tree->priv->mutex);
692
693 stack_start = pos = g_list_insert (
694 stack_start, tree->priv->root->left, -1);
695
696 while (pos != NULL) {
697 node = (EIntervalNode *) pos->data;
698
699 if (node != tree->priv->nil) {
700 if (compare_intervals (node->start, node->end, start, end) == 0) {
701 list = g_list_insert (list, node->comp, -1);
702 g_object_ref (node->comp);
703 }
704
705 if (compare_intervals (node->left->min, node->left->max, start, end) == 0)
706 pos = g_list_insert (pos, node->left, -1);
707
708 if (compare_intervals (node->right->min, node->right->max, start, end) == 0)
709 pos = g_list_insert (pos, node->right, -1);
710 }
711
712 pos = pos->next;
713 }
714
715 g_list_free (stack_start);
716
717 g_rec_mutex_unlock (&tree->priv->mutex);
718
719 return list;
720 }
721
722 /**
723 * e_intervaltree_destroy:
724 * @tree: an #EIntervalTree
725 *
726 * Since: 2.32
727 **/
728 void
e_intervaltree_destroy(EIntervalTree * tree)729 e_intervaltree_destroy (EIntervalTree *tree)
730 {
731 EIntervalNode *node;
732 GList *stack_start = NULL, *pos;
733
734 g_return_if_fail (E_IS_INTERVALTREE (tree));
735
736 stack_start = pos = g_list_insert (
737 stack_start, tree->priv->root->left, -1);
738
739 while (pos != NULL) {
740 node = (EIntervalNode *) pos->data;
741
742 if (node != tree->priv->nil) {
743 pos = g_list_insert (pos, node->left, -1);
744 pos = g_list_insert (pos, node->right, -1);
745
746 g_object_unref (node->comp);
747 g_free (node);
748 }
749
750 pos = pos->next;
751 }
752
753 g_list_free (stack_start);
754 g_object_unref (tree);
755 }
756
757 #ifdef E_INTERVALTREE_DEBUG
758 static void
e_intervaltree_node_dump(EIntervalTree * tree,EIntervalNode * node,gint indent)759 e_intervaltree_node_dump (EIntervalTree *tree,
760 EIntervalNode *node,
761 gint indent)
762 {
763 /*
764 gchar start_time[32] = {0}, end_time[32] = {0};
765 struct tm tm_start_time, tm_end_time;
766 *
767 localtime_r (&node->start, &tm_start_time);
768 localtime_r (&node->end, &tm_end_time);
769 strftime (start_time, sizeof (start_time), "%Y-%m-%d T%H:%M:%S", &tm_start_time);
770 strftime (end_time, sizeof (end_time), "%Y-%m-%d T%H:%M:%S", &tm_end_time);
771 g_print ("%*s[%s - %s]\n", indent, "", start_time, end_time);
772 */
773 if (node != tree->priv->nil) {
774 g_print (
775 "%*s[%" G_GINT64_FORMAT "- %" G_GINT64_FORMAT "] [%" G_GINT64_FORMAT "- %" G_GINT64_FORMAT "] red %d\n", indent, "", (gint64) node->start,
776 (gint64) node->end, (gint64) node->min, (gint64) node->max, node->red);
777 } else {
778 g_print ("%*s[ - ]\n", indent, "");
779 return;
780 }
781
782 e_intervaltree_node_dump (tree, node->left, indent + 2);
783 e_intervaltree_node_dump (tree, node->right, indent + 2);
784 }
785
786 void
e_intervaltree_dump(EIntervalTree * tree)787 e_intervaltree_dump (EIntervalTree *tree)
788 {
789 g_return_if_fail (E_IS_INTERVALTREE (tree));
790
791 if (tree->priv->root)
792 e_intervaltree_node_dump (tree, tree->priv->root, 0);
793 }
794 #endif
795
796