todo(1) is a program that lists the next tasks in decreasing order of urgency (most urgent tasks first).
"Next" tasks are those which are not blocked by a task it depends that is still not set as done.

I think I'm using a convoluted solution, because I create five different data structures in the program.
First, I collect tasks in a hash table (1) and an unsorted list (2).
While I'm collecting tasks, I get its dependencies and build a graph of tasks (3).
Then, I free the hash table (I use it only to get the dependencies without having to loop over the unsorted list all the time).
Then, I iterate over the unsorted list of tasks to visit each node in the graph and create a topologically sorted list of tasks (4).
Then, I iterate over that sorted list and extract those tasks that are not blocked into an array (5) of unblocked tasks. I sort this array based on the urgency of the tasks.
Finally, I print that array.

To compute the urgency, I do the following:
I compute the difference of days between the deadline and today.
Then I compute the log2 of this difference.
Then I subtract the result by the priority (1 for A, 0 for B, -1 for C).
The result of the subtraction is the urgency. The lower the better.

Here's the manual with a example of usage:

TODO(1)                     General Commands Manual                    TODO(1)

NAME

SYNOPSIS
todo [-dl] file...

DESCRIPTION
standard output those tasks that should be done, and that are not
order of urgency (the most urgent task is the first listed).  If a
hyphen (-) is provided as argument or the argument is absent, todo
reads from the standard input.  The options are as follows:

if they are not explicitly set as done.

-l     Long format.  Display tasks with its internal name, priority and

Each event must begin with an optional status.  Two status are
possible: TODO (which defines a uncompleted task) or DONE (which
defines a completed task).  If no status is supplied, it is considered
as TODO.

After the optional status comes the optional priority.  The priority is
a single uppercase letter between parentheses.  The letter must be A, B
or C.  The lower the letter, the higher the priority; so “A” is the
higher priority.

name is a single alphanumeric word without spaces that names the task.
The task name must be followed by a colon.

description spans from the space after the colon that ends the task
name to the beginning of the first property.

After the optional task description comes the properties.  Properties
are a space-delimited list of name-value pairs separated by colon.  The
following property names and their respective values are listed below.

due    A property of the form due:YYYY-MM-DD specifies the deadline of

deps   A property of the form deps:dep1,dep2,…,depN specifies a comma-

If a task line ends in a backslash (\), the task continues in the next
line.  If a line does not match the format of a task specification,
that line is ignored and a warning is printed to stderr.

EXAMPLES
Consider the following input.

DONE graph:   (B) Learn graphs.
TODO manual:  (C) Write manual for todo(1).
TODO sort:    (B) Learn how to do topological sorting.    deps:graph
TODO data:    (A) Implement data structures for tasks.
TODO parser:  (B) Write code for parsing tasks.           deps:data
TODO algor:   (A) Implement algorithm for sorting tasks.  deps:data,sort
TODO todo:    (B) Write the todo(1) utility.              deps:parser,algor
TODO release: (C) Release todo(1).                        deps:todo,manual

Running todo with the option -l on this input would print the
following:

data:       (A) Implement data structures for tasks.
sort:       (B) Learn how to do topological sorting.
manual:     (C) Write manual for todo(1).

calendar(1), schedule(1)

TODO(1)


Here's the code:

#include <sys/time.h>
#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define SECS_PER_DAY  ((time_t)(24 * 60 * 60))
#define DAYS_PER_WEEK 7
#define MIDDAY        12                /* 12:00 */
#define NHASH         128               /* size of hash table */
#define MULTIPLIER    31                /* multiplier for hash table */
#define NCOLS         10                /* number of collumns reserved for task name in long format */
#define TODO          "TODO"
#define DONE          "DONE"
#define PROP_DEPS     "deps"
#define PROP_DUE      "due"

struct Edge *deps;              /* linked list of dependency edges */
time_t due;                     /* due date, at 12:00 */
int pri;                        /* priority */
int visited;                    /* whether node was visited while sorting */
int done;                       /* whether task is marked as done */
char *date;                     /* due date, in format YYYY-MM-DD*/
char *name;                     /* task name */
char *desc;                     /* task description */
};

struct Edge {
struct Edge *next;              /* next edge on linked list */
};

/* list and table of tasks */
struct Agenda {
size_t nunblock;                /* number of unblocked tasks */
};

/* time for today, 12:00 */
static time_t today;

/* option flags */
static int dflag;                       /* whether to consider tasks with passed deadline as done */
static int lflag;                       /* whether to display tasks in long format */

/* show usage and exit */
static void
usage(void)
{
(void)fprintf(stderr, "usage: todo [-ld] [file...]\n");
exit(1);
}

/* call malloc checking for error */
static void *
emalloc(size_t size)
{
void *p;

if ((p = malloc(size)) == NULL)
err(1, "malloc");
return p;
}

/* call calloc checking for error */
static void *
ecalloc(size_t nmemb, size_t size)
{
void *p;

if ((p = calloc(nmemb, size)) == NULL)
err(1, "calloc");
return p;
}

/* call strdup checking for error */
static char *
estrdup(const char *s)
{
char *t;

if ((t = strdup(s)) == NULL)
err(1, "strdup");
return t;
}

/* get time for today, at 12:00 */
static time_t
gettoday(void)
{
struct tm *tmorig;
struct tm tm;
time_t t;

if ((t = time(NULL)) == -1)
err(1, NULL);
if ((tmorig = localtime(&t)) == NULL)
err(1, NULL);
tm = *tmorig;
tm.tm_hour = MIDDAY;
tm.tm_min = 0;
tm.tm_sec = 0;
tm.tm_isdst = -1;
if ((t = mktime(&tm)) == -1)
err(1, NULL);
return t;
}

/* compute hash value of string */
static size_t
hash(const char *s)
{
size_t h;
unsigned char *p;

h = 0;
for (p = (unsigned char *)s; *p != '\0'; p++)
h = MULTIPLIER * h + *p;
return h % NHASH;
}

/* find name in agenda, creating if does not exist */
lookup(struct Agenda *agenda, const char *name)
{
size_t h;

h = hash(name);
for (p = agenda->htab[h]; p != NULL; p = p->hnext)
if (strcmp(name, p->name) == 0)
return p;
p = emalloc(sizeof(*p));
p->name = estrdup(name);
p->hnext = agenda->htab[h];
p->unext = agenda->unsort;
agenda->htab[h] = p;
agenda->unsort = p;
return p;
}

/* create agenda and hash table */
static struct Agenda *
newagenda(void)
{
struct Agenda *agenda;

agenda = ecalloc(1, sizeof(*agenda));
agenda->htab = ecalloc(NHASH, sizeof(*(agenda->htab)));
return agenda;
}

static void
{
struct Edge *edge;
char *t;

for (t = strtok(s, ","); t != NULL; t = strtok(NULL, ",")) {
tmp = lookup(agenda, t);
edge = emalloc(sizeof(*edge));
edge->to = tmp;
}
}

static void
{
struct tm *tmorig;
struct tm tm;
time_t t;
char *ep;

if ((tmorig = localtime(&today)) == NULL) {
warn(NULL);
return;
}
tm = *tmorig;
ep = strptime(s, "%Y-%m-%d", &tm);
if (ep == NULL || *ep != '\0') {
errno = EINVAL;
warn("%s", s);
return;
}
tm.tm_hour = MIDDAY;
tm.tm_min = 0;
tm.tm_sec = 0;
tm.tm_isdst = -1;
if ((t = mktime(&tm)) == -1) {
warn(NULL);
return;
}
if (dflag && task->due < today) {
}
}

/* parse s for a new task and add it into agenda; we change s */
static void
{
size_t len;
int done;
char *name, *prop, *val;
char *t, *end, *colon;
int pri;

while (isspace(*(unsigned char *)s))
s++;
done = 0;
if (strncmp(s, TODO, sizeof(TODO) - 1) == 0) {
s += sizeof(TODO) - 1;
} else if (strncmp(s, DONE, sizeof(DONE) - 1) == 0) {
done = 1;
s += sizeof(DONE) - 1;
}
while (isspace(*(unsigned char *)s))
s++;
name = NULL;
for (t = s; *t != '\0' && !isspace(*(unsigned char *)t); t++) {
if (*t == ':') {
name = s;
*t = '\0';
s = t + 1;
break;
}
}
if (name == NULL)
return;
while (isspace(*(unsigned char *)s))
s++;
pri = 0;
if (s[0] == '(' && s[1] >= 'A' && s[1] <= 'C' && s[2] == ')') {
switch (s[1]) {
case 'A':
pri = +1;
break;
default:
pri = 0;
break;
case 'C':
pri = -1;
break;
}
s += 3;
}
while (isspace(*(unsigned char *)s))
s++;
len = strlen(s);
for (t = &s[len - 1]; t >= s; t--) {
colon = NULL;
while (t >= s && isspace(*(unsigned char *)t))
t--;
end = t + 1;
while (t >= s && !isspace(*(unsigned char *)t)) {
if (*t == ':') {
colon = t;
*colon = '\0';
}
t--;
}
if (colon) {
*t = '\0';
*end = '\0';
prop = t + 1;
val = colon + 1;
if (strcmp(prop, PROP_DUE) == 0) {
} else if (strcmp(prop, PROP_DEPS) == 0) {
} else {
warnx("unknown property \"%s\"", prop);
}
} else {
break;
}
}
len = strlen(s);
for (t = &s[len - 1]; isspace(*(unsigned char *)t) && t >= s; t--)
*t = '\0';
}

static void
{
char buf[BUFSIZ];

while (fgets(buf, sizeof(buf), fp) != NULL) {
}
}

/* visit task and their dependencies */
static void
{
struct Edge *edge;

return;
for (edge = task->deps; edge != NULL; edge = edge->next)
if (agenda->stail != NULL)
}

static int
comparetask(const void *a, const void *b)
{
time_t timea, timeb;
time_t tmpa, tmpb;

tmpa = (taska->due != 0) ? (taska->due - today) / SECS_PER_DAY : DAYS_PER_WEEK;
tmpb = (taskb->due != 0) ? (taskb->due - today) / SECS_PER_DAY : DAYS_PER_WEEK;
timea = timeb = 0;
if (tmpa < 0) {
tmpa = -tmpa;
while (tmpa >>= 1) {
--timea;
}
} else {
while (tmpa >>= 1) {
++timea;
}
}
if (tmpb < 0) {
tmpb = -tmpb;
while (tmpb >>= 1) {
--timeb;
}
} else {
while (tmpb >>= 1) {
++timeb;
}
}
if (timea < timeb)
return -1;
if (timea > timeb)
return +1;
return 0;
}

/* perform topological sort on agenda */
static void
{
struct Edge *edge;
int cont;

free(agenda->htab);
}
continue;
cont = 0;
for (edge = task->deps; edge != NULL; edge = edge->next) {
if (!edge->to->done) {
cont = 1;
break;
}
}
if (cont) {
continue;
}
}
}
}

static void
{
size_t i;
int n;

for (i = 0; i < agenda->nunblock; i++) {
if (lflag) {
n = (n > 0 && n < NCOLS) ? NCOLS - n : 0;
(void)printf(":%*c (%c) %s", n, ' ', (task->pri < 0 ? 'C' : (task->pri > 0 ? 'A' : 'B')), task->desc);
}
} else {
}
printf("\n");
}
}

/* free agenda and its tasks */
static void
freeagenda(struct Agenda *agenda)
{
struct Edge *edge, *etmp;

for (edge = task->deps; edge != NULL; ) {
etmp = edge;
edge = edge->next;
free(etmp);
}
free(ttmp->name);
free(ttmp->desc);
free(ttmp->date);
free(ttmp);
}
free(agenda->array);
free(agenda);
}

/* todo: print next tasks */
int
main(int argc, char *argv[])
{
static struct Agenda *agenda;
FILE *fp;
int exitval, ch;

today = gettoday();
while ((ch = getopt(argc, argv, "dl")) != -1) {
switch (ch) {
case 'd':
dflag = 1;
break;
case 'l':
lflag = 1;
break;
default:
usage();
break;
}
}
argc -= optind;
argv += optind;
exitval = 0;
agenda = newagenda();
if (argc == 0) {
} else {
for (; *argv != NULL; argv++) {
if (strcmp(*argv, "-") == 0) {
continue;
}
if ((fp = fopen(*argv, "r")) == NULL) {
warn("%s", *argv);
exitval = 1;
continue;
}
fclose(fp);
}
}
freeagenda(agenda);
return exitval;
}


EDIT: I removed the topological sort and released todo(1) on github with another utility of mine.

• To handle 16-bit systems, (since code not tagged *nix), ((time_t)(24 * 60 * 60)) should be ((time_t) 24 * 60 * 60) to avoid overflow. (taska->due - today) / SECS_PER_DAY assumes time_T is a count of seconds. Use difftime() for portability. Aug 31 '21 at 20:22
• I didn't know time_t could not be a count of seconds in some platforms. But difftime returns a double... I'll try it but... that's unusual. The return of difftime(3) is guaranteed to be in seconds, so I can divide it by SECS_PER_DAY and get the number of days between tasks due date and today? I just discovered timespecsub(3), a BSD innovation, but I won't use it. Aug 31 '21 at 22:14
• C's time functions are lacking - sigh - no mkgmtime(), timezone weaknesses, ... Aug 31 '21 at 23:10

The manpage looks very nice! There's a few small improvements that could be made:

• Spelling: "decrescend" should be "decreasing".
• Some conflicting statements are made, like "Each event must begin with an optional status." Consider rewriting this to avoid any confusion. Perhaps also start with a single line showing the syntax of each line, like so:
[status] [priority] task-name: [description] [name:value]...

• Also, the description says the priority comes after status and before the task name, but the example shows the priority coming after the task name.
• Put the description of the file format in its own section.
• Show off all features in the examples section, in particular I am not seeing the "due" option being used, nor line continuation using backslashes.

# Avoid using #define if a static const variable will do

Instead of defining constants using #define, prefer declaring them as static const variables instead. This avoids having to deal with macro issues like needing lots of parentheses, and ensures those constants also have a type associated with them. For example:

static const time_t SECS_PER_DAY = 24 * 60 * 60;
static const int DAYS_PER_WEEK = 7;
...
static const char PROP_DUE[] = "due";


# Reduce the number of data structures

I think I'm using a convoluted solution, because I create five different data structures in the program.

Indeed, it's a bit much, and you could get rid of some. Instead of having hash maps and linked lists, you could store everything in arrays: one array of struct Tasks, and perhaps some others with pointers to Tasks if necessary. This whole array can then be sorted using qsort(), and then you can do $$\\mathcal{O}(\log N)\$$ lookups using bsearch().

While hash maps are the fastest for sufficiently large numbers of tasks, a sorted array will probably outperform it for a small number of tasks.

Another option is to not use your own hash map implementation, but use the POSIX hcreate() and related functions.

# Unnecessary topological sort

You mention you do a topological sort of the tasks, then iterate over that sorted list and print out all the unblocked tasks. However, just determining whether tasks are blocked or not does not require a topological sort at all. Instead, just add a flag bool blocked to struct Task, make sure it is false when a new Task is created. Then after reading in all the tasks, just iterate over all of them, and for each task check its dependencies. If it depends on a task that is not yet DONE, then just set blocked = true. Then do another pass to print out only the tasks that have blocked == false. If you only allow dependencies on tasks that have already been read in, then you can even do the check of being blocked inside addtask().

# Rename lookup() to lookup_or_create()

The lookup function also is used to create new tasks, so I would rename it lookup_or_create(). Alternatively, have separate lookup() and newtask() functions.

# Initialize all elements when creating a new Task

In lookup(), when you create a new Task, you only initialize some of the elements of this struct. I recommend you ensure all of them are properly initialized, by just using ecalloc() instead of emalloc(). This will avoid surprises.

The function addtask() is quite long. Try to separate it into several sections and add a comment to each section describing what is done. It should look something like this:

// Strip leading spaces
while (isspace((unsigned char)*s))
s++;

// Check for the optional state
done = 0;
if (strncmp(s, TODO, sizeof(TODO) - 1) == 0) {
...
}
...

...

// And so on...


Even better would be to create separate functions for each section, so that addtask() would look like this instead:

done = readstatus(&s);

if (name == NULL)
return;
...


Where for example readstatus() would look like:

static void skipspaces(char **s) {
while (isspace((unsigned char)**s))
++*s;
}

skipspace(s);

if (strncmp(*s, ...)) {
*s += ...;
} else if (...) {
...
return true;
}

return false;
}


# Missing error checking

You check whether files are opened correctly, but you don't check if the files were read correctly. After reading in all the lines, use feof() to check whether you actually reached the end of the file. If not, something has gone wrong.

Also consider exitting the program immediately upon any read error, instead of just setting exitval = 1. The user might not notice the non-zero exit code, and you are printing potentially incorrect data.

Furthermore, also consider exitting with an error message and non-zero exit code if parsing the lines failed, and if other errors are detected such as cyclical dependencies.

You might also want to check that printing the tasks was done succesfully. Consider someone redirecting standard output to a file on a file system that is nearly full. In case writing fails, you again want to print an error message to standard error, and exit with a non-zero exit code. To do this correctly, I recommend you do this right at the end of main() by first calling fflush(), then using ferror() to check if any error was encountered while writing to stdout.

I also recommend you use EXIT_SUCCESS and EXIT_FAILURE as the exit codes.

• Thanks for the answer! I edited the OP to add a link to a github repo with an updated version of todo(1). Indeed, the topological sort was unnecessary so I removed it. I'm not using hsearch(1) because OpenBSD's implementation seems to differ from Linux's in how the key element of ENTRY must be allocated (but I might be wrong). Aug 31 '21 at 13:25
• btw, I'm not exiting on a read error because I want to follow cat(1)'s behavior of ignoring nonexistent files and just print an error to stderr(4) and exit with nonzero status after processing all the other files. Aug 31 '21 at 13:41
   agenda->htab = ecalloc(NHASH, sizeof(*(agenda->htab)));


GCC's static analyzer can't find a corresponding call to free() for this allocation. It gets through Valgrind at runtime, but that's only because sorttasks() has been called, which is fragile. And if sorttasks() gets called more than once, we'll be accessing freed memory, which is UB.

I would modify sorttasks to set agenda->htab = NULL after freeing the memory, and add free(agenda->htab) to freeagenda(). That will make the code much more robust (and keep the static analysis on our side).

Also, it's a poor assumption that calloc() produces null pointers - that's not universally true for all architectures.

The order of functions in the file makes it harder to find things. In particular, I would expect newagenda() and freeagenda() to be adjacent.

In freeagenda(), there's no need for the variables to be at function scope. They can be reduced to where they are used (and given better names):

static void
freeagenda(struct Agenda *agenda)
{
for (struct Edge *edge = task->deps;  edge;  ) {
struct Edge *next_edge = edge->next;
free(edge);
edge = next_edge;
}
}
free(agenda->array);
free(agenda);
}


static void
usage(void)
{
(void)fprintf(stderr, "usage: todo [-ld] [file...]\n");
exit(1);
}


This usage message is useful only as an error. We could adapt it to provide --help:

static void __attribute__((noreturn))
usage(int is_err)
{
fputs("usage: todo [-ld] [file...]\n", is_err ? stderr : stdout);
exit(is_err);
}


It's a shame not to see the unit tests for the parsing. There's a lot of problem cases to consider, and I would expect the tests to be present, to give confidence in future changes. I wouldn't accept this without the accompanying test suite.

(This is a partial review - I got a higher-priority interrupt and not sure whether I'll return to this.)

• "it's a poor assumption that calloc() produces null pointers" is curious. Why poor? C spec does have "The calloc function returns either a null pointer or a pointer to the allocated space." Aug 31 '21 at 16:49
• Re; freeagenda(), perhaps tolerate freeagenda(NULL), just like free(NULL) is OK. Easier to do clean-up. Aug 31 '21 at 16:52
• @chux-ReinstateMonica I think they mean after successful calloc, the return value has length all-bits-zero, not guaranteed to be a null-pointer. I see only struct Task that has 2 fields which would be affected.
– Neil
Aug 31 '21 at 20:56
• @Neil Fair point. Yes,some esoteric platforms do not have a pointer of all zero bits as a null pointer. I suspect Darwinian code pressure has lead to their extinction - even if allowed by spec. Aug 31 '21 at 21:01
• @chux, yes Neil's interpretation is what I meant. Sorry for not being clearer. I've never used a platform where all-zeros isn't a null pointer (or even any where there are other null pointers), but thought I should point out the lack of guarantee. Sep 1 '21 at 6:59