src/libicalss/icalspanlist.c

   1 /* -*- Mode: C -*-
   2     ======================================================================
   3     FILE: icalspanlist.c
   4     CREATOR: ebusboom 23 aug 2000
   5
   6     $Id: icalspanlist.c,v 1.15 2008-01-02 20:07:42 dothebart Exp $
   7     $Locker:  $
   8
   9     (C) COPYRIGHT 2000, Eric Busboom, http://www.softwarestudio.org
  10
  11     This program is free software; you can redistribute it and/or modify
  12     it under the terms of either:
  13
  14     The LGPL as published by the Free Software Foundation, version
  15     2.1, available at: http://www.fsf.org/copyleft/lesser.html
  16
  17     Or:
  18
  19     The Mozilla Public License Version 1.0. You may obtain a copy of
  20     the License at http://www.mozilla.org/MPL/
  21
  22
  23     ======================================================================*/
  24
  25 #ifdef HAVE_CONFIG_H
  26 #include "config.h"
  27 #endif
  28
  29 #include <libical/ical.h>
  30 #include "icalspanlist.h"
  31
  32 #include <stdlib.h> /* for free and malloc */
  33 #include <string.h>
  34
  35 struct icalspanlist_impl {
  36   pvl_list spans;               /**< list of icaltime_span data **/
  37   struct icaltimetype start;    /**< start time of span **/
  38   struct icaltimetype end;      /**< end time of span **/
  39 };
  40
  41 /** @brief Internal comparison function for two spans
  42  *
  43  *  @param  a   a spanlist.
  44  *  @param  b   another spanlist.
  45  *
  46  *  @return     -1, 0, 1 depending on the comparison of the start times.
  47  *
  48  * Used to insert spans into the tree in sorted order.
  49  */
  50
  51 static int compare_span(void* a, void* b)
  52 {
  53     struct icaltime_span *span_a = (struct icaltime_span *)a ;
  54     struct icaltime_span *span_b = (struct icaltime_span *)b ;
  55
  56     if(span_a->start == span_b->start){
  57         return 0;
  58     } else if(span_a->start < span_b->start){
  59         return -1;
  60     }  else { /*if(span_a->start > span->b.start)*/
  61         return 1;
  62     }
  63 }
  64
  65
  66 /** @brief callback function for collecting spanlists of a
  67  *         series of events.
  68  *
  69  *  @param   comp  A valid icalcomponent.
  70  *  @param   span  The span to insert into data.
  71  *  @param   data  The actual spanlist to insert into
  72  *
  73  *  This callback is used by icalcomponent_foreach_recurrence()
  74  *  to build up a spanlist.
  75  */
  76
  77 static void icalspanlist_new_callback(icalcomponent *comp,
  78                                             struct icaltime_span *span,
  79                                             void *data)
  80 {
  81   icaltime_span *s;
  82   icalspanlist *sl = (icalspanlist*) data;
  83
  84   if (span->is_busy == 0)
  85     return;
  86
  87   if ((s=(icaltime_span *) malloc(sizeof(icaltime_span))) == 0) {
  88     icalerror_set_errno(ICAL_NEWFAILED_ERROR);
  89     return;
  90   }
  91
  92   /** copy span data into allocated memory.. **/
  93   *s = *span;
  94   pvl_insert_ordered(sl->spans, compare_span, (void*)s);
  95 }
  96
  97
  98
  99 /** @brief Make a free list from a set of VEVENT components.
 100  *
 101  *  @param set    A valid icalset containing VEVENTS
 102  *  @param start  The free list starts at this date/time
 103  *  @param end    The free list ends at this date/time
 104  *
 105  *  @return        A spanlist corresponding to the VEVENTS
 106  *
 107  * Given a set of components,  a start time and an end time
 108  * return a spanlist that contains the free/busy times.
 109  */
 110
 111 icalspanlist* icalspanlist_new(icalset *set,
 112                                struct icaltimetype start,
 113                                struct icaltimetype end)
 114 {
 115     struct icaltime_span range;
 116     pvl_elem itr;
 117     icalcomponent *c,*inner;
 118     icalcomponent_kind kind, inner_kind;
 119     icalspanlist *sl;
 120     struct icaltime_span *freetime;
 121
 122     if ( ( sl = (struct icalspanlist_impl*)
 123            malloc(sizeof(struct icalspanlist_impl))) == 0) {
 124         icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 125         return 0;
 126     }
 127
 128     sl->spans =  pvl_newlist();
 129     sl->start =  start;
 130     sl->end   =  end;
 131
 132     range.start = icaltime_as_timet(start);
 133     range.end = icaltime_as_timet(end);
 134
 135     /* Get a list of spans of busy time from the events in the set
 136        and order the spans based on the start time */
 137
 138    for(c = icalset_get_first_component(set);
 139         c != 0;
 140         c = icalset_get_next_component(set)){
 141
 142        kind  = icalcomponent_isa(c);
 143        inner = icalcomponent_get_inner(c);
 144
 145        if(!inner){
 146            continue;
 147        }
 148
 149        inner_kind = icalcomponent_isa(inner);
 150
 151        if( kind != ICAL_VEVENT_COMPONENT &&
 152            inner_kind != ICAL_VEVENT_COMPONENT){
 153            continue;
 154        }
 155
 156        icalerror_clear_errno();
 157
 158        icalcomponent_foreach_recurrence(c, start, end,
 159                                         icalspanlist_new_callback,
 160                                         (void*)sl);
 161
 162    }
 163
 164     /* Now Fill in the free time spans. loop through the spans. if the
 165        start of the range is not within the span, create a free entry
 166        that runs from the start of the range to the start of the
 167        span. */
 168
 169      for( itr = pvl_head(sl->spans);
 170          itr != 0;
 171          itr = pvl_next(itr))
 172     {
 173         struct icaltime_span *s = (struct icaltime_span*)pvl_data(itr);
 174
 175         if ((freetime=(struct icaltime_span *)
 176              malloc(sizeof(struct icaltime_span))) == 0){
 177             icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 178             icalspanlist_free(sl);
 179             return 0;
 180             }
 181
 182         if(range.start < s->start){
 183             freetime->start = range.start;
 184             freetime->end = s->start;
 185
 186             freetime->is_busy = 0;
 187
 188
 189             pvl_insert_ordered(sl->spans,compare_span,(void*)freetime);
 190         } else {
 191             free(freetime);
 192         }
 193
 194         range.start = s->end;
 195     }
 196
 197      /* If the end of the range is null, then assume that everything
 198         after the last item in the calendar is open and add a span
 199         that indicates this */
 200
 201      if( icaltime_is_null_time(end)){
 202          struct icaltime_span* last_span;
 203
 204          last_span = (struct icaltime_span*)pvl_data(pvl_tail(sl->spans));
 205
 206          if (last_span != 0){
 207
 208              if ((freetime=(struct icaltime_span *)
 209                   malloc(sizeof(struct icaltime_span))) == 0){
 210                  icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 211                  icalspanlist_free(sl);
 212                  return 0;
 213              }
 214
 215              freetime->is_busy = 0;
 216              freetime->start = last_span->end;
 217              freetime->end = freetime->start;
 218              pvl_insert_ordered(sl->spans,compare_span,(void*)freetime);
 219          }
 220      }
 221
 222
 223      return sl;
 224 }
 225
 226 /** @brief Destructor.
 227  *  @param s A valid icalspanlist
 228  *
 229  *  Free memory associated with the spanlist
 230  */
 231
 232 void icalspanlist_free(icalspanlist* s)
 233 {
 234     struct icaltime_span *span;
 235
 236     if (s == NULL)
 237       return;
 238
 239     while( (span=pvl_pop(s->spans)) != 0){
 240         free(span);
 241     }
 242
 243     pvl_free(s->spans);
 244
 245     s->spans = 0;
 246
 247     free(s);
 248 }
 249
 250
 251 /** @brief (Debug) print out spanlist to stdout.
 252  *  @param sl A valid icalspanlist.
 253  */
 254
 255 void icalspanlist_dump(icalspanlist* sl){
 256      int i = 0;
 257      pvl_elem itr;
 258
 259      for( itr = pvl_head(sl->spans);
 260          itr != 0;
 261          itr = pvl_next(itr))
 262     {
 263         struct icaltime_span *s = (struct icaltime_span*)pvl_data(itr);
 264
 265         printf("#%02d %d start: %s",++i,s->is_busy,ctime(&s->start));
 266         printf("      end  : %s",ctime(&s->end));
 267
 268     }
 269 }
 270
 271 icalcomponent* icalspanlist_make_free_list(icalspanlist* sl);
 272 icalcomponent* icalspanlist_make_busy_list(icalspanlist* sl);
 273
 274
 275 /** @brief Find next free time span in a spanlist.
 276  *
 277  *  @param  sl     The spanlist to search.
 278  *  @param  t      The time to start looking.
 279  *
 280  *  Given a spanlist and a time, find the next period of time
 281  *  that is free
 282  */
 283
 284 struct icalperiodtype icalspanlist_next_free_time(icalspanlist* sl,
 285                                                 struct icaltimetype t)
 286 {
 287      pvl_elem itr;
 288      struct icalperiodtype period;
 289      struct icaltime_span *s;
 290
 291      time_t rangett= icaltime_as_timet(t);
 292
 293      period.start = icaltime_null_time();
 294      period.end = icaltime_null_time();
 295
 296      itr = pvl_head(sl->spans);
 297      s = (struct icaltime_span *)pvl_data(itr);
 298
 299      if (s == 0){
 300          /* No elements in span */
 301          return period;
 302      }
 303
 304      /* Is the reference time before the first span? If so, assume
 305         that the reference time is free */
 306      if(rangett <s->start ){
 307          /* End of period is start of first span if span is busy, end
 308             of the span if it is free */
 309          period.start =  t;
 310
 311          if (s->is_busy == 1){
 312              period.end =  icaltime_from_timet(s->start,0);
 313          } else {
 314              period.end =  icaltime_from_timet(s->end,0);
 315          }
 316
 317          return period;
 318      }
 319
 320      /* Otherwise, find the first free span that contains the
 321         reference time. */
 322      for( itr = pvl_head(sl->spans);
 323          itr != 0;
 324          itr = pvl_next(itr))
 325     {
 326         s = (struct icaltime_span *)pvl_data(itr);
 327
 328         if(s->is_busy == 0 && s->start >= rangett &&
 329             ( rangett < s->end || s->end == s->start)){
 330
 331             if (rangett < s->start){
 332                 period.start = icaltime_from_timet(s->start,0);
 333             } else {
 334                 period.start = icaltime_from_timet(rangett,0);
 335             }
 336
 337             period.end = icaltime_from_timet(s->end,0);
 338
 339             return period;
 340         }
 341
 342     }
 343
 344      period.start = icaltime_null_time();
 345      period.end = icaltime_null_time();
 346
 347      return period;
 348 }
 349
 350 struct icalperiodtype icalspanlist_next_busy_time(icalspanlist* sl,
 351                                                 struct icaltimetype t);
 352
 353
 354 /** @brief Returns an hour-by-hour array of free/busy times over a
 355  *         given period.
 356  *
 357  *  @param sl        A valid icalspanlist
 358  *  @param delta_t   The time slice to divide by, in seconds.  Default 3600.
 359  *
 360  *  @return A pointer to an array of integers containing the number of
 361  *       busy events in each delta_t time period.  The final entry
 362  *       contains the value -1.
 363  *
 364  *  This calculation is somewhat tricky.  This is due to the fact that
 365  *  the time range contains the start time, but does not contain the
 366  *  end time.  To perform a proper calculation we subtract one second
 367  *  off the end times to get a true containing time.
 368  *
 369  *  Also note that if you supplying a spanlist that does not start or
 370  *  end on a time boundary divisible by delta_t you may get results
 371  *  that are not quite what you expect.
 372  */
 373
 374 int* icalspanlist_as_freebusy_matrix(icalspanlist* sl, int delta_t) {
 375   pvl_elem itr;
 376   int spanduration_secs;
 377   int *matrix;
 378   int matrix_slots;
 379   time_t sl_start, sl_end;
 380
 381   icalerror_check_arg_rz( (sl!=0), "spanlist");
 382
 383   if (!delta_t)
 384     delta_t = 3600;
 385
 386   /** calculate the start and end time as time_t **/
 387   sl_start = icaltime_as_timet_with_zone(sl->start, icaltimezone_get_utc_timezone());
 388   sl_end   = icaltime_as_timet_with_zone(sl->end, icaltimezone_get_utc_timezone());
 389
 390
 391   /** insure that the time period falls on a time boundary divisable
 392       by delta_t */
 393
 394   sl_start /= delta_t;
 395   sl_start *= delta_t;
 396
 397   sl_end /= delta_t;
 398   sl_end *= delta_t;
 399
 400
 401   /** find the duration of this spanlist **/
 402   spanduration_secs = sl_end - sl_start;
 403
 404
 405   /** malloc our matrix, add one extra slot for a final -1 **/
 406   matrix_slots = spanduration_secs/delta_t + 1;
 407
 408   matrix = (int*) malloc(sizeof(int) * matrix_slots);
 409   if (matrix == NULL) {
 410     icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 411     return NULL;
 412   }
 413   memset(matrix, 0, sizeof(int) * matrix_slots);
 414   matrix[matrix_slots-1] = -1;
 415
 416   /* loop through each span and mark the slots in the array */
 417
 418   for( itr = pvl_head(sl->spans);  itr != 0;  itr = pvl_next(itr)) {
 419     struct icaltime_span *s = (struct icaltime_span*)pvl_data(itr);
 420
 421     if (s->is_busy == 1) {
 422       int offset_start = s->start/delta_t - sl_start/delta_t;
 423       int offset_end   = (s->end - 1) /delta_t  - sl_start/delta_t + 1;
 424       int i;
 425
 426       if (offset_end >= matrix_slots)
 427         offset_end = matrix_slots - 1;
 428
 429       i = offset_start;
 430       for (i=offset_start; i < offset_end; i++) {
 431         matrix[i]++;
 432       }
 433     }
 434   }
 435   return matrix;
 436 }
 437
 438
 439 /** @brief Return a VFREEBUSY component for the corresponding spanlist
 440  *
 441  *   @param sl         A valid icalspanlist, from icalspanlist_new()
 442  *   @param organizer  The organizer specified as MAILTO:user@domain
 443  *   @param attendee   The attendee specified as MAILTO:user@domain
 444  *
 445  *   @return            A valid icalcomponent or NULL.
 446  *
 447  * This function returns a VFREEBUSY component for the given spanlist.
 448  * The start time is mapped to DTSTART, the end time to DTEND.
 449  * Each busy span is represented as a separate FREEBUSY entry.
 450  * An attendee parameter is required, and organizer parameter is
 451  * optional.
 452  */
 453
 454 icalcomponent *icalspanlist_as_vfreebusy(icalspanlist* sl,
 455                                          const char* organizer,
 456                                          const char* attendee) {
 457   icalcomponent *comp;
 458   icalproperty *p;
 459   struct icaltimetype atime = icaltime_from_timet( time(0),0);
 460   pvl_elem itr;
 461   icaltimezone *utc_zone;
 462   icalparameter *param;
 463
 464   if (!attendee) {
 465     icalerror_set_errno(ICAL_USAGE_ERROR);
 466     return 0;
 467   }
 468
 469   utc_zone = icaltimezone_get_utc_timezone ();
 470
 471   comp = icalcomponent_new_vfreebusy();
 472
 473   icalcomponent_add_property(comp, icalproperty_new_dtstart(sl->start));
 474   icalcomponent_add_property(comp, icalproperty_new_dtend(sl->end));
 475   icalcomponent_add_property(comp, icalproperty_new_dtstamp(atime));
 476
 477   if (organizer) {
 478     icalcomponent_add_property(comp, icalproperty_new_organizer(organizer));
 479   }
 480   icalcomponent_add_property(comp, icalproperty_new_attendee(attendee));
 481
 482   /* now add the freebusy sections.. */
 483
 484   for( itr = pvl_head(sl->spans);  itr != 0;  itr = pvl_next(itr)) {
 485     struct icalperiodtype period;
 486     struct icaltime_span *s = (struct icaltime_span*)pvl_data(itr);
 487
 488     if (s->is_busy == 1) {
 489
 490       period.start = icaltime_from_timet_with_zone (s->start, 0, utc_zone);
 491       period.end   = icaltime_from_timet_with_zone (s->end, 0, utc_zone);
 492       period.duration = icaldurationtype_null_duration();
 493
 494
 495       p = icalproperty_new_freebusy(period);
 496       param = icalparameter_new_fbtype(ICAL_FBTYPE_BUSY);
 497       icalproperty_add_parameter(p, param);
 498
 499       icalcomponent_add_property(comp, p);
 500     }
 501
 502   }
 503
 504   return comp;
 505 }
 506
 507
 508 /** @brief Return a spanlist corresponding to the VFREEBUSY portion of
 509  *         an icalcomponent.
 510  *
 511  *   @param   c        A valid icalcomponent.
 512  *
 513  *   @return           A valid icalspanlist or NULL if no VFREEBUSY section.
 514  *
 515  */
 516
 517
 518 icalspanlist *icalspanlist_from_vfreebusy(icalcomponent* comp)
 519 {
 520   icalcomponent *inner;
 521   icalproperty  *prop;
 522   icalspanlist  *sl;
 523
 524   icalerror_check_arg_rz((comp != NULL), "comp");
 525
 526   inner = icalcomponent_get_inner(comp);
 527   if (!inner) return NULL;
 528
 529   if ( ( sl = (icalspanlist*) malloc(sizeof(icalspanlist))) == 0) {
 530     icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 531     return 0;
 532   }
 533   sl->spans =  pvl_newlist();
 534
 535   /* cycle through each FREEBUSY property, adding to the spanlist */
 536   for (prop = icalcomponent_get_first_property(inner, ICAL_FREEBUSY_PROPERTY);
 537        prop != NULL;
 538        prop = icalcomponent_get_next_property(inner, ICAL_FREEBUSY_PROPERTY)) {
 539     icaltime_span *s = (icaltime_span *) malloc(sizeof(icaltime_span));
 540     icalparameter *param;
 541     struct icalperiodtype period;
 542     icalparameter_fbtype fbtype;
 543
 544     if (s == 0) {
 545       icalerror_set_errno(ICAL_NEWFAILED_ERROR);
 546       icalspanlist_free(sl);
 547       return 0;
 548     }
 549
 550     param = icalproperty_get_first_parameter(prop, ICAL_FBTYPE_PARAMETER);
 551     fbtype = (param) ? icalparameter_get_fbtype(param) : ICAL_FBTYPE_BUSY;
 552
 553     switch (fbtype) {
 554     case ICAL_FBTYPE_FREE:
 555     case ICAL_FBTYPE_NONE:
 556     case ICAL_FBTYPE_X:
 557       s->is_busy = 1;
 558       break;
 559     default:
 560       s->is_busy = 0;
 561     }
 562
 563     period = icalproperty_get_freebusy(prop);
 564     s->start = icaltime_as_timet_with_zone(period.start, icaltimezone_get_utc_timezone());
 565     s->end = icaltime_as_timet_with_zone(period.end, icaltimezone_get_utc_timezone());
 566 ;
 567     pvl_insert_ordered(sl->spans, compare_span, (void*)s);
 568   }
 569   /** @todo calculate start/end limits.. fill in holes? **/
 570   return sl;
 571 }