From 5250662614d9f914ad8e17ef79f45fe9022b7173 Mon Sep 17 00:00:00 2001
From: NeilBrown <neilb@suse.de>
Date: Tue, 31 Dec 2013 14:06:51 +1100
Subject: [PATCH] ical-date - now in C

This is  a C version of ical.py (which is python).
It can take an ical RRULE and make a useful list of dates.
There is stuff missing, like RDATE/EXDATE handling, but I want to move
on and that stuff can be added when needed.
---
 .gitignore       |    1 +
 lib/ical-dates.c | 1048 ++++++++++++++++++++++++++++++++++++++++++++++
 lib/ical-dates.h |   93 ++++
 lib/ical-test.c  |   44 ++
 4 files changed, 1186 insertions(+)
 create mode 100644 lib/ical-dates.c
 create mode 100644 lib/ical-dates.h
 create mode 100644 lib/ical-test.c

diff --git a/.gitignore b/.gitignore
index 100062e..9f9484e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,2 +1,3 @@
 *.o
 *.pyc
+ical-test
diff --git a/lib/ical-dates.c b/lib/ical-dates.c
new file mode 100644
index 0000000..0f4e9b5
--- /dev/null
+++ b/lib/ical-dates.c
@@ -0,0 +1,1048 @@
+/*
+ * ical-dates: library to handle ical dates/times and recurrences.
+ *
+ * Given a list of strings, typically from an ical file, we produce
+ * a data structure which encodes the relevant date info.
+ * Given such a structure, a start date, end date, and max count, we
+ * produce a list of dates.
+ */
+
+#include <unistd.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <stdio.h>
+#include "ical-dates.h"
+
+static int month_days[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
+static char *days[7] = { "SU","MO","TU","WE","TH","FR","SA"};
+static char *freqs[] = { "SECONDLY","MINUTELY","HOURLY",
+			 "DAILY","WEEKLY","MONTHLY","YEARLY"};
+
+static int daysin(int mon, int yr)
+{
+	if (mon != 2)
+		return month_days[mon-1];
+	if (yr%4 > 0)
+		return 28;
+	if (yr%400 > 0)
+		return 29;
+	return 28;
+}
+
+/* ical_times can be modified by adding/subtracting fields, but
+ * must then be normalised
+ */
+void ical_set_wday(struct ical_time *t)
+{
+	int yday = t->day;
+	int m;
+	int yr, wday;
+	for (m = 1; m < t->mon; m++)
+		yday += daysin(m, t->yr);
+	yr = t->yr - 1;
+	wday = yr + yr/4 - yr/400 + yday + 4;
+	t->yday = yday;
+	t->wday = wday % 7;
+}
+
+void ical_norm_mon(struct ical_time *t)
+{
+	while (t->mon < 1) {
+		t->mon += 12;
+		t->yr -= 1;
+	}
+	while (t->mon > 12) {
+		t->mon -= 12;
+		t->yr += 1;
+	}
+	ical_set_wday(t);
+}
+
+void ical_norm_day(struct ical_time *t)
+{
+	if (t->day >= 1 && t->day <= daysin(t->mon, t->yr)) {
+		if (t->wday < 0)
+			ical_set_wday(t);
+		return;
+	}
+	while (t->day < 1) {
+		t->mon -= 1;
+		ical_norm_mon(t);
+		t->day += daysin(t->mon, t->yr);
+	}
+	while (t->day > daysin(t->mon, t->yr)) {
+		t->day -= daysin(t->mon, t->yr);
+		t->mon += 1;
+		ical_norm_mon(t);
+	}
+	ical_set_wday(t);
+}
+
+void ical_norm_hr(struct ical_time *t)
+{
+	if (t->hr >= 0 && t->hr < 24)
+		return;
+	while (t->hr >= 24) {
+		t->hr -= 24;
+		t->day += 1;
+	}
+	while (t->hr < 0) {
+		t->hr += 24;
+		t->day -= 1;
+	}
+	t->wday = -1; // force wday/yday update
+	ical_norm_day(t);
+}
+
+void ical_norm_min(struct ical_time *t)
+{
+	if (t->min >= 0 && t->min < 60)
+		return;
+	while (t->min >= 60) {
+		t->min -= 60;
+		t->hr += 1;
+	}
+	while (t->min < 0) {
+		t->min += 60;
+		t->hr -= 1;
+	}
+	ical_norm_hr(t);
+}
+
+void ical_norm_sec(struct ical_time *t)
+{
+	if (t->sec >= 0 && t->sec < 60)
+		return;
+	while (t->sec >= 60) {
+		t->sec -= 60;
+		t->min += 1;
+	}
+	while (t->sec < 0) {
+		t->sec += 60;
+		t->min -= 1;
+	}
+	ical_norm_min(t);
+}
+
+int ical_ordered(const struct ical_time *a, const struct ical_time *b)
+{
+	if (a->yr != b->yr)
+		return a->yr - b->yr;
+	if (a->yday != b->yday)
+		return a->yday - b->yday;
+	return (a->hr*3600 + a->min*60 + a->sec) -
+		(b->hr*3600 + b->min*60 + b->sec);
+}
+
+static int ical_orderedv(const void *av, const void *bv)
+{
+	const struct ical_time *a = av;
+	const struct ical_time *b = bv;
+	return ical_ordered(a,b);
+}
+
+void ical_next(struct ical_iter *it)
+{
+	switch (it->unit) {
+	case Secondly:
+		it->now.sec += it->step;
+		ical_norm_sec(&it->now);
+		break;
+	case Minutely:
+		it->now.min += it->step;
+		ical_norm_min(&it->now);
+		break;
+	case Hourly:
+		it->now.hr += it->step;
+		ical_norm_hr(&it->now);
+		break;
+	case Daily:
+		it->now.day += it->step;
+		ical_norm_day(&it->now);
+		break;
+	case Weekly:
+		it->now.day += it->step * 7;
+		ical_norm_day(&it->now);
+		break;
+	case Monthly:
+		it->now.mon += it->step;
+		ical_norm_mon(&it->now);
+		break;
+	case Yearly:
+		it->now.yr += it->step;
+		ical_set_wday(&it->now);
+		break;
+	case BadInterval:
+		break;
+	}
+}
+
+static void list_add(struct ical_list *l, int v)
+{
+	if (l->cnt >= l->size) {
+		l->size = l->cnt + 8;
+		l->v = realloc(l->v, l->size * sizeof(v));
+	}
+	l->v[l->cnt++] = v;
+}
+
+void ical_list_free(struct ical_list *l)
+{
+	free(l->v);
+}
+
+static void timelist_add(struct ical_timelist *tl, struct ical_time *tm)
+{
+	if (tl->cnt >= tl->size) {
+		tl->size = tl->cnt + 8;
+		tl->v = realloc(tl->v, tl->size * sizeof(*tm));
+	}
+	tl->v[tl->cnt++] = *tm;
+}
+
+void ical_timelist_free(struct ical_timelist *tl)
+{
+	free(tl->v);
+}
+
+/* When parsing we destroy the argument string */
+static int parse_bysimple(struct ical_list *list, char *arg, int min, int max, int neg)
+{
+	while (*arg) {
+		char *w = arg;
+		int l = strcspn(arg, ",");
+		int v;
+		char *e;
+		if (arg[l])
+			arg[l++] = 0;
+		arg += l;
+		v = strtol(w, &e, 10);
+		if (!*w || *e)
+			return 0;
+		if ((v < 0 && !neg) ||
+		    abs(v) < min ||
+		    abs(v) > max)
+			return 0;
+		list_add(list, v);
+	}
+	return 1;
+}
+
+static int match_day(char *d)
+{
+	int n;
+	for (n = 0; n < 7; n++)
+		if (strcmp(d, days[n]) == 0)
+			return n;
+	return -1;
+}
+
+static int parse_byday(struct ical_list lists[7], char *arg)
+{
+	while (*arg) {
+		char *w = arg;
+		int d, v;
+		int l = strspn(arg, "0123456789+-SUMOTWEHFRA");
+		arg += l;
+		if (arg[0] == ',')
+			*arg++ = 0;
+		else if (arg[0])
+			return 0;
+		if (l < 2)
+			return 0;
+		d = match_day(w+l-2);
+		if (d < 0)
+			return 0;
+		if (l == 2)
+			v = 0;
+		else {
+			char *e;
+			v = strtol(w, &e, 10);
+			if (e != w+l-2)
+				return 0;
+		}
+		list_add(&lists[d], v);
+	}
+	return 1;
+}
+
+static enum ical_interval parse_freq(char *arg)
+{
+	enum ical_interval rv;
+	for (rv = Secondly; rv < BadInterval; rv++)
+		if (strcmp(arg, freqs[rv]) == 0)
+			return rv;
+	return BadInterval;
+}
+
+int ical_parse_rrule(struct ical_rrule *rr, char *arg, char *tz)
+{
+	/* ';' separated list of X=Y assignments where Y is a
+	 * ',' separated list of values
+	 */
+	memset(rr, 0, sizeof(*rr));
+	rr->wkst = 1; // MO by default
+	rr->unit = BadInterval;
+	rr->step = 1;
+	while (*arg) {
+		char *w = arg;
+		int l = strcspn(arg, ";");
+		int t;
+		char *b;
+
+		if (arg[l])
+			arg[l++] = 0;
+		arg += l;
+
+		t = strcspn(w, "=");
+		if (w[t] == 0)
+			return 0;
+		w[t++] = 0;
+		b = w+t;
+
+		if (strcmp(w, "FREQ") == 0) {
+			rr->unit = parse_freq(b);
+		} else if (strcmp(w, "INTERVAL") == 0) {
+			char *e;
+			rr->step = strtol(b, &e, 10);
+			if (rr->step < 1 || *b == 0 || *e != 0)
+				return 0;
+		} else if (strcmp(w, "COUNT") == 0) {
+			char *e;
+			rr->count = strtol(b, &e, 10);
+			if (rr->count < 1 || *b == 0 || *e != 0)
+				return 0;
+		} else if (strcmp(w, "UNTIL") == 0) {
+			if (ical_parse_time(&rr->until, b, tz) == 0)
+				return 0;
+		} else if (strcmp(w, "BYMONTH") == 0) {
+			if (parse_bysimple(&rr->bymonth, b, 1, 31, 0) == 0)
+				return 0;
+		} else if (strcmp(w, "BYWEEKNO") == 0) {
+			if (parse_bysimple(&rr->byweekno, b, 0, 53, 1) == 0)
+				return 0;
+		} else if (strcmp(w, "BYYEARDAY") == 0) {
+			if (parse_bysimple(&rr->byyday, b, 1, 366, 1) == 0)
+				return 0;
+		} else if (strcmp(w, "BYMONTHDAY") == 0) {
+			if (parse_bysimple(&rr->bymday, b, 1, 31, 1) == 0)
+				return 0;
+		} else if (strcmp(w, "BYDAY") == 0) {
+			if (parse_byday(rr->bydays, b) == 0)
+				return 0;
+			rr->any_bydays = 1;
+		} else if (strcmp(w, "BYHOUR") == 0) {
+			if (parse_bysimple(&rr->byhr, b, 0, 23, 0) == 0)
+				return 0;
+		} else if (strcmp(w, "BYMINUTE") == 0) {
+			if (parse_bysimple(&rr->bymin, b, 0, 59, 0) == 0)
+				return 0;
+		} else if (strcmp(w, "BYSECOND") == 0) {
+			if (parse_bysimple(&rr->bysec, b, 0, 59, 0) == 0)
+				return 0;
+		} else if (strcmp(w, "BYSETPOS") == 0) {
+			if (parse_bysimple(&rr->setpos, b, 1, 366, 1) == 0)
+				return 0;
+		} else if (strcmp(w, "WKST") == 0) {
+			rr->wkst = match_day(b);
+			if (rr->wkst < 0)
+				return 0;
+		} else
+			return 0;
+	}
+	/* FREQ is required. Everything else is optional */
+	if (rr->unit == BadInterval)
+		return 0;
+	return 1;
+}
+
+void ical_rrule_free(struct ical_rrule *rr)
+{
+	int i;
+	ical_list_free(&rr->bysec);
+	ical_list_free(&rr->bymin);
+	ical_list_free(&rr->byhr);
+	ical_list_free(&rr->bymonth);
+	ical_list_free(&rr->bymday);
+	ical_list_free(&rr->byyday);
+	ical_list_free(&rr->byweekno);
+	ical_list_free(&rr->setpos);
+	for (i=0; i<7; i++)
+		ical_list_free(&rr->bydays[i]);
+}
+
+static int getnum(char *arg, int len)
+{
+	int n = 0;
+	while (len) {
+		n = n*10 + arg[0] - '0';
+		arg++;
+		len--;
+	}
+	return n;
+}
+
+int ical_parse_time(struct ical_time *tm, char *arg, char *tz)
+{
+	/* 'arg' can by a date or datetime possibly followed by
+	 * another date-or-datetime or a period.
+	 * For now we just parse the start date[time]
+	 */
+	int l;
+
+	memset(tm, 0, sizeof(*tm));
+	l = strspn(arg, "0123456789");
+	if (l != 8)
+		return 0;
+	tm->yr = getnum(arg, 4);
+	tm->mon = getnum(arg+4, 2);
+	tm->day = getnum(arg+6, 2);
+	if (tm->mon < 1 || tm->mon > 12 ||
+	    tm->day < 1 || tm->day > daysin(tm->mon, tm->yr))
+		return 0;
+	ical_set_wday(tm);
+	if (arg[l] == 0)
+		return 1;
+	if (arg[l] != '/') {
+		if (arg[l] != 'T')
+			/* Need a time now! */
+			return 0;
+		arg += l+1;
+		l = strspn(arg, "0123456789");
+		if (l != 6)
+			return 0;
+		tm->hr = getnum(arg, 2);
+		tm->min = getnum(arg+2, 2);
+		tm->sec = getnum(arg+4, 2);
+		tm->time_set = 1;
+		if (tm->sec == 60)
+			/* Leap-sec.  Cannot cope, sorry */
+			tm->sec = 59;
+		if (tm->hr >= 24 || tm->min >= 60 || tm->sec >= 60)
+			return 0;
+		if (arg[l] == 'Z') {
+			tm->zone = "UTC";
+			l++;
+		} else
+			tm->zone = tz;
+		if (arg[l] == 0)
+			return 1;
+		if (arg[l] != '/')
+			return 0;
+	}
+	/* Ignore duration */
+	return 1;
+}
+
+int ical_parse_time_list(struct ical_timelist *tl, char *arg, char *tz)
+{
+	while (*arg) {
+		char *w = arg;
+		int l = strcspn(arg, ",");
+		struct ical_time tm;
+
+		if (arg[l])
+			arg[l++] = 0;
+		arg += l;
+		if (ical_parse_time(&tm, w, tz) == 0)
+			return 0;
+		timelist_add(tl, &tm);
+	}
+	return 1;
+}
+
+int ical_parse_dates_line(struct ical_dates *id, char *arg)
+{
+	int l = strcspn(arg, ":");
+	char *body, *param;
+	char *tz = NULL;
+
+	if (arg[l] == 0)
+		return 0;
+	arg[l++] = 0;
+	body = arg+l;
+
+	param = arg;
+	/* Look at params, but only care about TZID= */
+	while ((param = strchr(param, ';')) != NULL) {
+		*param++ = 0;
+		if (strncmp(param, "TZID=", 5) == 0)
+			tz = param + 5;
+	}
+
+	if (strcmp(arg, "DTSTART") == 0)
+		return ical_parse_time(&id->start, body, tz);
+	if (strcmp(arg, "RRULE") == 0)
+		return ical_parse_rrule(&id->rr, body, tz);
+	if (strcmp(arg, "RDATE") == 0)
+		return ical_parse_time_list(&id->rdate, body, tz);
+	if (strcmp(arg, "EXDATE") == 0)
+		return ical_parse_time_list(&id->exdate, body, tz);
+
+	/*put it back like we found it */
+	arg[--l] = ':';
+	while (l) {
+		l--;
+		if (!arg[l])
+			arg[l] = ';';
+	}
+	return -1;
+}
+
+void ical_dates_free(struct ical_dates *d)
+{
+	ical_rrule_free(&d->rr);
+	ical_timelist_free(&d->rdate);
+	ical_timelist_free(&d->exdate);
+}
+
+static int inlist(struct ical_list *l, int v)
+{
+	int i;
+	for (i = 0; i < l->cnt; i++)
+		if (l->v[i] == v)
+			return 1;
+	return 0;
+}
+
+static int set_mon(struct ical_time *tm, int v, int wkst)
+{
+	if (tm->day > daysin(v, tm->yr))
+		return 0;
+	tm->mon = v;
+	return 1;
+}
+
+static int get_mon(struct ical_time *tm)
+{
+	return tm->mon;
+}
+
+static int set_mday(struct ical_time *tm, int v, int wkst)
+{
+	int d = daysin(tm->mon, tm->yr);
+	if (v < 0)
+		v = d + 1 + v;
+	if (v < 1 || v > d)
+		return 0;
+	tm->day = v;
+	return 1;
+}
+
+static int test_mday(struct ical_time *tm, int v)
+{
+	if (v > 0)
+		return tm->day == v;
+	v = daysin(tm->mon, tm->yr) + 1 + v;
+	return tm->day == v;
+}
+
+static int set_yday(struct ical_time *tm, int v, int wkst)
+{
+	int d = daysin(2, tm->yr) - 28 + 365;
+	int m;
+	if (v < 0)
+		v = d + 1 + v;
+	if (v < 1 || v > d)
+		return 0;
+	tm->yday = v;
+	for (m=1; m<=12; m++) {
+		int md = daysin(m, tm->yr);
+		if (v <= md)
+			break;
+		v -= md;
+	}
+	tm->mon = m;
+	tm->day = v;
+	return 1;
+}
+
+static int test_yday(struct ical_time *tm, int v)
+{
+	if (v < 0) {
+		int d = daysin(2, tm->yr) - 28 + 365;
+		v = d + 1 + v;
+	}
+	return tm->yday == v;
+}
+
+static int set_weekno(struct ical_time *tm, int v, int wkst)
+{
+	struct ical_time st = *tm;
+	int i;
+	if (v >= 0) {
+		st.mon = 1;
+		st.day = -2;
+		ical_norm_day(&st);
+		ical_set_wday(&st);
+		while (st.wday != wkst) {
+			st.day ++;
+			ical_norm_day(&st);
+			ical_set_wday(&st);
+		}
+		st.day += (v-1)*7;
+	} else {
+		st.mon = 12;
+		st.day = 28;
+		ical_set_wday(&st);
+		while (st.wday != wkst) {
+			st.day --;
+			ical_set_wday(&st);
+		}
+		st.day -= (-1-v)*7;
+	}
+	ical_norm_day(&st);
+	ical_set_wday(&st);
+	/* Now at the start of the week */
+	for (i=0; i<7; i++) {
+		if (st.yr == tm->yr &&
+		    st.wday == tm->wday) {
+			*tm = st;
+			return 1;
+		}
+		st.day++;
+		ical_norm_day(&st);
+		ical_set_wday(&st);
+	}
+	return 0;
+}
+
+static int set_hr(struct ical_time *tm, int v, int wkst)
+{
+	tm->hr = v;
+	return 1;
+}
+
+static int get_hr(struct ical_time *tm)
+{
+	return tm->hr;
+}
+
+static int set_min(struct ical_time *tm, int v, int wkst)
+{
+	tm->min = v;
+	return 1;
+}
+
+static int get_min(struct ical_time *tm)
+{
+	return tm->min;
+}
+
+static int set_sec(struct ical_time *tm, int v, int wkst)
+{
+	tm->sec = v;
+	return 1;
+}
+
+static int get_sec(struct ical_time *tm)
+{
+	return tm->sec;
+}
+
+static void expand(struct ical_timelist *tl,
+		   int (*set)(struct ical_time *tm, int v, int wkst),
+		   struct ical_list *l, int wkst)
+{
+	struct ical_timelist newl = {0};
+	int i, j;
+	for (i = 0; i < tl->cnt; i++) {
+		for (j = 0; j < l->cnt; j++) {
+			struct ical_time t = tl->v[i];
+			if (set(&t, l->v[j], wkst)) {
+				ical_set_wday(&t);
+				timelist_add(&newl, &t);
+			}
+		}
+	}
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void expand_byday(struct ical_timelist *tl,
+			 struct ical_list *dl, int wkst, enum ical_interval xtype)
+{
+	struct ical_timelist newl = {0};
+	int i, days, d;
+	for (i = 0; i < tl->cnt; i++) {
+		struct ical_time st;
+
+		st = tl->v[i];
+		if (xtype == Yearly) {
+			/* Every relevant day in this year */
+			st.mon = 1;
+			st.day = 1;
+			days = daysin(2, st.yr) - 28 + 365;
+		} else if (xtype == Monthly) {
+			/* Every relevant day in this month */
+			st.day = 1;
+			days = daysin(st.mon, st.yr);
+		} else {
+			/* The relevant day in this week */
+			while (st.wday != wkst) {
+				st.day -= 1;
+				st.wday = -1;
+				ical_norm_day(&st);
+			}
+			days = 7;
+		}
+		ical_set_wday(&st);
+		for (d = 0 ; d < days; d++) {
+			struct ical_list *l = dl + st.wday;
+			if (inlist(l, 0) || inlist(l, d/7+1) || inlist(l, -((days-d)/7+1)))
+				timelist_add(&newl, &st);
+			st.day++;
+			ical_norm_day(&st);
+			ical_set_wday(&st);
+		}
+	}
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void filter(struct ical_timelist *tl, int(*get)(struct ical_time *tm),
+		   struct ical_list *l)
+{
+	struct ical_timelist newl = {0};
+	int i;
+	for (i = 0; i < tl->cnt; i++)
+		if (inlist(l, get(&tl->v[i])))
+			timelist_add(&newl, &tl->v[i]);
+
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void filter_byday(struct ical_timelist *tl,
+			 struct ical_list *l)
+{
+	struct ical_timelist newl = {0};
+	int i;
+	for (i = 0; i < tl->cnt; i++)
+		if (inlist(l+tl->v[i].wday, 0))
+			timelist_add(&newl, &tl->v[i]);
+
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void filter_test(struct ical_timelist *tl,
+			int(*test)(struct ical_time *tm, int v),
+			struct ical_list *l)
+{
+	struct ical_timelist newl = {0};
+	int i, j;
+	for (i = 0; i < tl->cnt; i++)
+		for (j = 0; j < l->cnt; j++)
+			if (test(&tl->v[i], l->v[j])) {
+				timelist_add(&newl, &tl->v[i]);
+				break;
+			}
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void filter_setpos(struct ical_timelist *tl, struct ical_list *l)
+{
+	struct ical_timelist newl = {0};
+	int i;
+	for (i = 0; i < l->cnt; i++) {
+		int j = l->v[i];
+		if (j < 0) {
+			j = tl->cnt + j;
+			if (inlist(l, j))
+				j = -1;
+		} else
+			j -= 1;
+		if (j >= 0 && j < tl->cnt)
+			timelist_add(&newl, &tl->v[i]);
+	}
+	ical_timelist_free(tl);
+	*tl = newl;
+}
+
+static void dedup(struct ical_timelist *tl)
+{
+	int i;
+	for (i = 1; i < tl->cnt; i++) {
+		if (ical_ordered(&tl->v[i-1], &tl->v[i]) == 0) {
+			tl->cnt--;
+			memmove(&tl->v[i], &tl->v[i+1], (tl->cnt - i)*sizeof(tl->v[0]));
+			i--;
+		}
+	}
+}
+
+static void trim(struct ical_timelist *tl, struct ical_time *tm)
+{
+	int i;
+	for (i = 0; i < tl->cnt; i++)
+		if (ical_ordered(&tl->v[i], tm) >= 0)
+			break;
+	if (i == 0)
+		return;
+	tl->cnt -= i;
+	memmove(tl->v, tl->v+i, tl->cnt * sizeof(tl->v[0]));
+}
+
+static void timelist_join(struct ical_timelist *a, struct ical_timelist *b)
+{
+	if (a->size < a->cnt + b->cnt) {
+		a->size = a->cnt + b->cnt;
+		a->v = realloc(a->v, a->size * sizeof(a->v[0]));
+	}
+	memcpy(&a->v[a->cnt], b->v, b->cnt * sizeof(b->v[0]));
+	a->cnt += b->cnt;
+	ical_timelist_free(b);
+}
+
+void ical_rr_dates(struct ical_time *start, struct ical_rrule *rr,
+		   struct ical_time *from, int max,
+		   struct ical_timelist *rv)
+{
+	/* generate dates from the given info an return some in 'rv'
+	 * We only report dates at or after 'from' and at most 'max'
+	 * of them.
+	 */
+	struct ical_time last;
+	struct ical_iter it;
+
+	if (start->mon == 0 || rr->unit == BadInterval)
+		return;
+
+	it.now = *start;
+	it.unit = rr->unit;
+	it.step = rr->step;
+	last = *start;
+
+	if (rr->count  > 0 && rr->count < max)
+		max = rr->count;
+
+	for ( ;
+	      (rv->cnt < max &&
+	       (rr->until.mon == 0 || ical_ordered(&last, &rr->until) < 0));
+	      ical_next(&it)
+		) {
+		struct ical_timelist nl = {0};
+		timelist_add(&nl, &it.now);
+
+		/* BYMONTH */
+		if (rr->bymonth.cnt) {
+			if (rr->unit > Monthly)
+				expand(&nl, set_mon, &rr->bymonth, rr->wkst);
+			else
+				filter(&nl, get_mon, &rr->bymonth);
+		}
+		/* BYWEEKNO */
+		if (rr->byweekno.cnt) {
+			if (rr->unit == Yearly)
+				expand(&nl, set_weekno, &rr->byweekno, rr->wkst);
+		}
+		/* BYYEARDAY */
+		if (rr->byyday.cnt) {
+			if (rr->unit == Yearly)
+				expand(&nl, set_yday, &rr->byyday, rr->wkst);
+			else if (rr->unit < Daily)
+				filter_test(&nl, test_yday, &rr->byyday);
+		}
+		/* BYMONTHDAY */
+		if (rr->bymday.cnt) {
+			if (rr->unit > Weekly)
+				expand(&nl, set_mday, &rr->bymday, rr->wkst);
+			else if (rr->unit < Weekly)
+				filter_test(&nl, test_mday, &rr->bymday);
+		}
+		/* BYDAY */
+		if (rr->any_bydays) {
+			enum ical_interval xtype = BadInterval;
+			switch (rr->unit) {
+			case Weekly:
+				xtype = Weekly; break;
+			case Monthly:
+				if (rr->bymday.cnt == 0)
+					xtype = Monthly;
+				break;
+			case Yearly:
+				if (rr->byyday.cnt || rr->bymday.cnt)
+					/* select, not expand */;
+				else if (rr->byweekno.cnt)
+					xtype = Weekly;
+				else if (rr->bymonth.cnt)
+					xtype = Monthly;
+				else
+					xtype = Yearly;
+			default:;
+			}
+			if (xtype == BadInterval)
+				filter_byday(&nl, rr->bydays);
+			else
+				expand_byday(&nl, rr->bydays, rr->wkst, xtype);
+		}
+		/* BYHOUR */
+		if (rr->byhr.cnt) {
+			if (rr->unit > Hourly)
+				expand(&nl, set_hr, &rr->byhr, rr->wkst);
+			else
+				filter(&nl, get_hr, &rr->byhr);
+		}
+		/* BYMINUTE */
+		if (rr->bymin.cnt) {
+			if (rr->unit > Minutely)
+				expand(&nl, set_min, &rr->bymin, rr->wkst);
+			else
+				filter(&nl, get_min, &rr->bymin);
+		}
+		/* BYSECOND */
+		if (rr->bysec.cnt) {
+			if (rr->unit > Secondly)
+				expand(&nl, set_sec, &rr->bysec, rr->wkst);
+			else
+				filter(&nl, get_sec, &rr->bysec);
+		}
+		/* BYSETPOS */
+		qsort(nl.v, nl.cnt, sizeof(nl.v[0]), ical_orderedv);
+		dedup(&nl);
+		if (rr->setpos.cnt)
+			filter_setpos(&nl, &rr->setpos);
+		trim(&nl, start);
+		if (rr->count <= 0)
+			trim(&nl, from);
+		timelist_join(rv, &nl);
+		if (rv->cnt)
+			last = rv->v[rv->cnt-1];
+	}
+	trim(rv, from);
+	if (rv->cnt > max)
+		rv->cnt = max;
+}
+
+int ical_strftime(char *buf, int max, const char *fmt, struct ical_time *itm)
+{
+	struct tm tm;
+	tm.tm_sec = itm->sec;
+	tm.tm_min = itm->min;
+	tm.tm_hour = itm->hr;
+	tm.tm_mday = itm->day;
+	tm.tm_mon = itm->mon - 1;
+	tm.tm_year = itm->yr - 1900;
+	tm.tm_wday = itm->wday;
+	tm.tm_yday = itm->yday - 1;
+	tm.tm_isdst = 0;
+	return strftime(buf, max, fmt, &tm);
+}
+
+void ical_localtime(struct ical_time *itm, const time_t *timep)
+{
+	struct tm tm;
+	localtime_r(timep, &tm);
+	itm->time_set = 1;
+	itm->dur_set = 0;
+	itm->sec = tm.tm_sec;
+	itm->min = tm.tm_min;
+	itm->hr = tm.tm_hour;
+	itm->day = tm.tm_mday;
+	itm->mon = tm.tm_mon + 1;
+	itm->yr = tm.tm_year + 1900;
+	itm->wday = tm.tm_wday;
+	itm->yday = tm.tm_yday + 1;
+	itm->zone = tzname[tm.tm_isdst];
+}
+
+time_t ical_mktime(struct ical_time *itm)
+{
+	struct tm tm;
+	tm.tm_sec = itm->sec;
+	tm.tm_min = itm->min;
+	tm.tm_hour = itm->hr;
+	tm.tm_mday = itm->day;
+	tm.tm_mon = itm->mon - 1;
+	tm.tm_year = itm->yr - 1900;
+	tm.tm_wday = itm->wday;
+	tm.tm_yday = itm->yday - 1;
+	tm.tm_isdst = -1;
+	return mktime(&tm);
+}
+
+int ical_fmt_time(char *buf, int size, struct ical_time *tm)
+{
+	int rv = 0;
+	buf[0] = 0;
+	if (tm->mon == 0)
+		return rv;
+	rv += snprintf(buf+rv, size-rv, "%04d%02d%02d", tm->yr, tm->mon, tm->day);
+	if (tm->time_set == 0)
+		return rv;
+	rv += snprintf(buf+rv, size-rv, "T%02d%02d%02d%s", tm->hr, tm->min, tm->sec,
+		     (tm->zone && strcmp(tm->zone, "UTC")==0) ? "Z":"");
+	return rv;
+}
+
+int fmt_list(char *buf, int size, char *str, struct ical_list *l)
+{
+	int rv = 0;
+	int i;
+	rv += snprintf(buf+rv, size-rv, "%s", str);
+	for (i = 0; i < l->cnt; i++) {
+		if (i && rv < size)
+			buf[rv++] = ',';
+		rv += snprintf(buf+rv, size-rv, "%d", l->v[i]);
+	}
+	return rv;
+}
+
+int fmt_days(char *buf, int size, char *str, struct ical_list *l)
+{
+	int rv = 0;
+	int d,i;
+	int first = 1;
+	rv += snprintf(buf+rv, size-rv, "%s", str);
+	for (d = 0; d < 7; d++)
+		for (i = 0; i < l[d].cnt; i++) {
+			if (!first && rv < size)
+				buf[rv++] = ',';
+			first = 0;
+			if (l[d].v[i])
+				rv += snprintf(buf+rv, size-rv, "%d%s", l[d].v[i], days[d]);
+			else
+				rv += snprintf(buf+rv, size-rv, "%s", days[d]);
+		}
+	return rv;
+}
+
+int ical_fmt_rr(char *buf, int size, struct ical_rrule *rr)
+{
+	int rv = 0;
+	if (rr->unit == BadInterval)
+		return 0;
+
+	rv += snprintf(buf+rv, size-rv, "FREQ=%s", freqs[rr->unit]);
+	if (rr->step > 1)
+		rv += snprintf(buf+rv, size-rv, ";INTERVAL=%d", rr->step);
+	if (rr->count > 0)
+		rv += snprintf(buf+rv, size-rv, ";COUNT=%d", rr->count);
+	if (rr->until.mon) {
+		rv += snprintf(buf+rv, size-rv, ";UNTIL=");
+		rv += ical_fmt_time(buf+rv, size-rv, &rr->until);
+	}
+	if (rr->wkst != 1)
+		rv += snprintf(buf+rv, size-rv, ";WKST=%s", days[rr->wkst]);
+	if (rr->bymonth.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYMONTH=", &rr->bymonth);
+	if (rr->byweekno.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYWEEKNO=", &rr->byweekno);
+	if (rr->byyday.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYYEARDAY=", &rr->byyday);
+	if (rr->bymday.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYMONTHDAY=", &rr->bymday);
+	if (rr->any_bydays)
+		rv += fmt_days(buf+rv, size-rv, ";BYDAY=", rr->bydays);
+	if (rr->byhr.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYHOUR=", &rr->byhr);
+	if (rr->bymin.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYMINUTE=", &rr->bymin);
+	if (rr->bysec.cnt)
+		rv += fmt_list(buf+rv, size-rv, ";BYSECOND=", &rr->bysec);
+
+	return rv;
+}
diff --git a/lib/ical-dates.h b/lib/ical-dates.h
new file mode 100644
index 0000000..ed7fc5f
--- /dev/null
+++ b/lib/ical-dates.h
@@ -0,0 +1,93 @@
+
+enum ical_interval {
+	Secondly, Minutely, Hourly, Daily, Weekly, Monthly, Yearly,
+	BadInterval
+};
+/*
+ * A date/time/period is stored in a 'struct ical_time'
+ */
+struct ical_time {
+	short hr, min, sec;
+	short yr, mon, day;
+	short wday, yday;
+	short time_set;
+	short days;
+	int secs;
+	short dur_set;
+	char *zone;
+};
+
+struct ical_list {
+	int cnt, size;
+	int *v;
+};
+struct ical_timelist {
+	int cnt, size;
+	struct ical_time *v;
+};
+
+/*
+ * An ical_iter can step through dates given a unit and step size
+ */
+struct ical_iter {
+	struct  ical_time now;
+	enum ical_interval unit;
+	int step;
+};
+
+/*
+ * An ical_rrule holds the various fields from an RRULE
+ */
+struct ical_rrule {
+	enum ical_interval unit;
+	int step;
+	int count;
+	struct ical_time until; /* mon==0 if not set */
+	int wkst;
+	int any_bydays;
+	struct ical_list bysec, bymin, byhr, bymonth;
+	struct ical_list bydays[7];
+	struct ical_list bymday, byyday, byweekno;
+	struct ical_list setpos;
+};
+
+struct ical_dates {
+	struct ical_time start;
+	struct ical_rrule rr;
+	struct ical_timelist rdate, exdate;
+};
+
+/* ical_times can be modified by adding/subtracting fields, but
+ * must then be normalised
+ */
+void ical_set_wday(struct ical_time *t);
+void ical_norm_mon(struct ical_time *t);
+void ical_norm_day(struct ical_time *t);
+void ical_norm_hr(struct ical_time *t);
+void ical_norm_min(struct ical_time *t);
+void ical_norm_sec(struct ical_time *t);
+
+/* Advance it->now to next thing */
+void ical_next(struct ical_iter *it);
+int ical_ordered(const struct ical_time *a, const struct ical_time *b);
+
+/* Parse various structures.  'arg' string will be destroyed */
+int ical_parse_rrule(struct ical_rrule *rr, char *arg, char *tz);
+int ical_parse_time(struct ical_time *tm, char *arg, char *tz);
+int ical_parse_time_list(struct ical_timelist *tl, char *arg, char *tz);
+int ical_parse_dates_line(struct ical_dates *id, char *arg);
+
+void ical_rr_dates(struct ical_time *start, struct ical_rrule *rr,
+		   struct ical_time *from, int max,
+		   struct ical_timelist *rv);
+int ical_strftime(char *buf, int max, const char *fmt, struct ical_time *itm);
+void ical_localtime(struct ical_time *itm, const time_t *timep);
+time_t ical_mktime(struct ical_time *itm);
+
+void ical_list_free(struct ical_list *l);
+void ical_timelist_free(struct ical_timelist *tl);
+void ical_rrule_free(struct ical_rrule *rr);
+void ical_dates_free(struct ical_dates *d);
+
+int ical_fmt_time(char *buf, int size, struct ical_time *tm);
+int ical_fmt_rr(char *buf, int size, struct ical_rrule *rr);
diff --git a/lib/ical-test.c b/lib/ical-test.c
new file mode 100644
index 0000000..1e906ba
--- /dev/null
+++ b/lib/ical-test.c
@@ -0,0 +1,44 @@
+
+#include <unistd.h>
+#include <stdlib.h>
+#include <memory.h>
+#include <stdio.h>
+
+#include "ical-dates.h"
+
+int main(int argc, char *argv[])
+{
+	struct ical_dates d;
+	int a;
+	int i;
+	struct ical_timelist res;
+	char buf[100];
+
+	memset(&d, 0, sizeof(d));
+
+	for (a = 1; a < argc; a++) {
+		char *s = strdup(argv[a]);
+		switch(ical_parse_dates_line(&d, s)) {
+		case 0:
+			printf("Bad line: %s\n", s);
+			exit(2);
+		case 1:
+			/* cool */
+			break;
+		default:
+			printf("Don't know about %s\n", argv[a]);
+			break;
+		}
+		free(s);
+	}
+	ical_fmt_rr(buf, sizeof(buf), &d.rr);
+	memset(&res, 0, sizeof(res));
+	ical_rr_dates(&d.start, &d.rr, &d.start, 100, &res);
+	printf("%d dates in %s\n", res.cnt, buf);
+	for (i = 0; i < res.cnt; i++) {
+		char buf[100];
+		ical_strftime(buf, 100, "%Y/%m/%d %T %A", &res.v[i]);
+		printf(" %s %ld\n", buf, ical_mktime(&res.v[i]));
+	}
+	return 0;
+}
-- 
2.39.5