commit: 495ef1b140c06f5f6ef435c717dce24db05e9d97
parent:
author: Chris Noxz <chris@noxz.tech>
date: Thu, 19 Sep 2019 17:12:49 +0200
Initial commit of fork of scron
9 files changed, 1442 insertions(+)
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,23 @@
+MIT/X Consortium License
+
+© 2014-2015 Ari Malinen <ari.malinen@gmail.com>
+© 2014 sin <sin@2f30.org>
+© 2014 Hiltjo Posthuma <hiltjo@codemadness.org>
+
+Permission is hereby granted, free of charge, to any person obtaining a
+copy of this software and associated documentation files (the "Software"),
+to deal in the Software without restriction, including without limitation
+the rights to use, copy, modify, merge, publish, distribute, sublicense,
+and/or sell copies of the Software, and to permit persons to whom the
+Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/Makefile b/Makefile
@@ -0,0 +1,24 @@
+CFLAGS += -std=c99 -Wall -Wextra -pedantic -D_POSIX_C_SOURCE=200809L -D_BSD_SOURCE
+PREFIX = /usr/local
+MANPREFIX = $(PREFIX)/man
+
+BIN = crond
+MAN = scron.1
+
+all: $(BIN)
+
+install: all
+ mkdir -p $(DESTDIR)$(PREFIX)/bin
+ cp -f $(BIN) $(DESTDIR)$(PREFIX)/bin
+ mkdir -p $(DESTDIR)$(MANPREFIX)/man1
+ cp -f $(MAN) $(DESTDIR)$(MANPREFIX)/man1
+
+uninstall:
+ rm -f $(DESTDIR)$(PREFIX)/bin/$(BIN)
+ rm -f $(DESTDIR)$(MANPREFIX)/man1/$(MAN)
+
+clean:
+ rm -f $(BIN)
+
+.PHONY:
+ all install uninstall clean
diff --git a/README b/README
@@ -0,0 +1,33 @@
+scron
+=====
+Simple cron daemon.
+
+Features
+--------
+* Schedule commands to be run at specified dates and times.
+* Single daemon and configiguration file.
+* Log job output: 'command &>> /var/log/cron.log'.
+* Run job as different user: 'su -c 'command' user'.
+* Log to stdout or syslog.
+* No mail support.
+
+Configuration
+-------------
+Columns:
+ minute, hour, day of month, month, day of week, command
+
+Separator:
+ Any number of tabs or spaces.
+
+Value:
+ * (wildcard), 30 (number), */N (repeat), 1-5 (range), or 1,3,6 (list)
+
+Example of crontab file:
+ # Run updatedb at 6:00 every day
+ 0 6 * * * updatedb
+
+ # Run at 5:30 every business day. Log output to /var/log/backup.log.
+ 30 5 * * 1-5 syncbackup &>> /var/log/backup.log
+
+ # Run as user postmaster at 5:00 every third day of month.
+ 0 5 */3 * * su -c 'mail -s "Hello world" a@b.com' postmaster
diff --git a/TODO b/TODO
@@ -0,0 +1,2 @@
+* Detect clock changes
+* DST support?
diff --git a/arg.h b/arg.h
@@ -0,0 +1,63 @@
+/*
+ * Copy me if you can.
+ * by 20h
+ */
+
+#ifndef ARG_H__
+#define ARG_H__
+
+extern char *argv0;
+
+/* use main(int argc, char *argv[]) */
+#define ARGBEGIN for (argv0 = *argv, argv++, argc--;\
+ argv[0] && argv[0][1]\
+ && argv[0][0] == '-';\
+ argc--, argv++) {\
+ char argc_;\
+ char **argv_;\
+ int brk_;\
+ if (argv[0][1] == '-' && argv[0][2] == '\0') {\
+ argv++;\
+ argc--;\
+ break;\
+ }\
+ for (brk_ = 0, argv[0]++, argv_ = argv;\
+ argv[0][0] && !brk_;\
+ argv[0]++) {\
+ if (argv_ != argv)\
+ break;\
+ argc_ = argv[0][0];\
+ switch (argc_)
+
+/* Handles obsolete -NUM syntax */
+#define ARGNUM case '0':\
+ case '1':\
+ case '2':\
+ case '3':\
+ case '4':\
+ case '5':\
+ case '6':\
+ case '7':\
+ case '8':\
+ case '9'
+
+#define ARGEND }\
+ }
+
+#define ARGC() argc_
+
+#define ARGNUMF(base) (brk_ = 1, estrtol(argv[0], (base)))
+
+#define EARGF(x) ((argv[0][1] == '\0' && argv[1] == NULL)?\
+ ((x), abort(), (char *)0) :\
+ (brk_ = 1, (argv[0][1] != '\0')?\
+ (&argv[0][1]) :\
+ (argc--, argv++, argv[0])))
+
+#define ARGF() ((argv[0][1] == '\0' && argv[1] == NULL)?\
+ (char *)0 :\
+ (brk_ = 1, (argv[0][1] != '\0')?\
+ (&argv[0][1]) :\
+ (argc--, argv++, argv[0])))
+
+#endif
diff --git a/crond b/crond
diff --git a/crond.c b/crond.c
@@ -0,0 +1,604 @@
+/* See LICENSE file for copyright and license details. */
+#include <sys/types.h>
+#include <sys/wait.h>
+
+#include <errno.h>
+#include <limits.h>
+#include <signal.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <ctype.h>
+#include <string.h>
+#include <syslog.h>
+#include <time.h>
+#include <unistd.h>
+
+#include "arg.h"
+#include "queue.h"
+
+#define VERSION "0.4"
+
+#define LEN(x) (sizeof (x) / sizeof *(x))
+
+struct field {
+ enum {
+ ERROR,
+ WILDCARD,
+ NUMBER,
+ RANGE,
+ REPEAT,
+ LIST
+ } type;
+ long *val;
+ int len;
+};
+
+struct ctabentry {
+ struct field min;
+ struct field hour;
+ struct field mday;
+ struct field mon;
+ struct field wday;
+ char *cmd;
+ TAILQ_ENTRY(ctabentry) entry;
+};
+
+struct jobentry {
+ char *cmd;
+ pid_t pid;
+ TAILQ_ENTRY(jobentry) entry;
+};
+
+char *argv0;
+static sig_atomic_t chldreap;
+static sig_atomic_t reload;
+static sig_atomic_t quit;
+static TAILQ_HEAD(, ctabentry) ctabhead = TAILQ_HEAD_INITIALIZER(ctabhead);
+static TAILQ_HEAD(, jobentry) jobhead = TAILQ_HEAD_INITIALIZER(jobhead);
+static char *config = "/etc/crontab";
+static char *pidfile = "/var/run/crond.pid";
+static int nflag;
+
+static void
+loginfo(const char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+ if (nflag == 0)
+ vsyslog(LOG_INFO, fmt, ap);
+ else
+ vfprintf(stdout, fmt, ap);
+ fflush(stdout);
+ va_end(ap);
+}
+
+static void
+logwarn(const char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+ if (nflag == 0)
+ vsyslog(LOG_WARNING, fmt, ap);
+ else
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+}
+
+static void
+logerr(const char *fmt, ...)
+{
+ va_list ap;
+ va_start(ap, fmt);
+ if (nflag == 0)
+ vsyslog(LOG_ERR, fmt, ap);
+ else
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+}
+
+static void *
+emalloc(size_t size)
+{
+ void *p;
+ p = malloc(size);
+ if (!p) {
+ logerr("error: out of memory\n");
+ if (nflag == 0)
+ unlink(pidfile);
+ exit(EXIT_FAILURE);
+ }
+ return p;
+}
+
+static char *
+estrdup(const char *s)
+{
+ char *p;
+
+ p = strdup(s);
+ if (!p) {
+ logerr("error: out of memory\n");
+ if (nflag == 0)
+ unlink(pidfile);
+ exit(EXIT_FAILURE);
+ }
+ return p;
+}
+
+static void
+runjob(char *cmd)
+{
+ struct jobentry *je;
+ time_t t;
+ pid_t pid;
+
+ t = time(NULL);
+
+ /* If command is already running, skip it */
+ TAILQ_FOREACH(je, &jobhead, entry) {
+ if (strcmp(je->cmd, cmd) == 0) {
+ loginfo("already running %s pid: %d at %s",
+ je->cmd, je->pid, ctime(&t));
+ return;
+ }
+ }
+
+ pid = fork();
+ if (pid < 0) {
+ logerr("error: failed to fork job: %s time: %s",
+ cmd, ctime(&t));
+ return;
+ } else if (pid == 0) {
+ setsid();
+ loginfo("run: %s pid: %d at %s",
+ cmd, getpid(), ctime(&t));
+ execl("/bin/sh", "/bin/sh", "-c", cmd, (char *)NULL);
+ logerr("error: failed to execute job: %s time: %s",
+ cmd, ctime(&t));
+ _exit(EXIT_FAILURE);
+ } else {
+ je = emalloc(sizeof(*je));
+ je->cmd = estrdup(cmd);
+ je->pid = pid;
+ TAILQ_INSERT_TAIL(&jobhead, je, entry);
+ }
+}
+
+static void
+waitjob(void)
+{
+ struct jobentry *je, *tmp;
+ int status;
+ time_t t;
+ pid_t pid;
+
+ t = time(NULL);
+
+ while ((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
+ je = NULL;
+ TAILQ_FOREACH(tmp, &jobhead, entry) {
+ if (tmp->pid == pid) {
+ je = tmp;
+ break;
+ }
+ }
+ if (je) {
+ TAILQ_REMOVE(&jobhead, je, entry);
+ free(je->cmd);
+ free(je);
+ }
+ if (WIFEXITED(status) == 1)
+ loginfo("complete: pid: %d returned: %d time: %s",
+ pid, WEXITSTATUS(status), ctime(&t));
+ else if (WIFSIGNALED(status) == 1)
+ loginfo("complete: pid: %d terminated by signal: %s time: %s",
+ pid, strsignal(WTERMSIG(status)), ctime(&t));
+ else if (WIFSTOPPED(status) == 1)
+ loginfo("complete: pid: %d stopped by signal: %s time: %s",
+ pid, strsignal(WSTOPSIG(status)), ctime(&t));
+ }
+}
+
+static int
+isleap(int year)
+{
+ if (year % 400 == 0)
+ return 1;
+ if (year % 100 == 0)
+ return 0;
+ return (year % 4 == 0);
+}
+
+static int
+daysinmon(int mon, int year)
+{
+ int days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
+ if (year < 1900)
+ year += 1900;
+ if (isleap(year))
+ days[1] = 29;
+ return days[mon];
+}
+
+static int
+matchentry(struct ctabentry *cte, struct tm *tm)
+{
+ struct {
+ struct field *f;
+ int tm;
+ int len;
+ } matchtbl[] = {
+ { .f = &cte->min, .tm = tm->tm_min, .len = 60 },
+ { .f = &cte->hour, .tm = tm->tm_hour, .len = 24 },
+ { .f = &cte->mday, .tm = tm->tm_mday, .len = daysinmon(tm->tm_mon, tm->tm_year) },
+ { .f = &cte->mon, .tm = tm->tm_mon, .len = 12 },
+ { .f = &cte->wday, .tm = tm->tm_wday, .len = 7 },
+ };
+ size_t i;
+ int j;
+
+ for (i = 0; i < LEN(matchtbl); i++) {
+ switch (matchtbl[i].f->type) {
+ case WILDCARD:
+ continue;
+ case NUMBER:
+ if (matchtbl[i].f->val[0] == matchtbl[i].tm)
+ continue;
+ break;
+ case RANGE:
+ if (matchtbl[i].f->val[0] <= matchtbl[i].tm)
+ if (matchtbl[i].f->val[1] >= matchtbl[i].tm)
+ continue;
+ break;
+ case REPEAT:
+ if (matchtbl[i].tm > 0) {
+ if (matchtbl[i].tm % matchtbl[i].f->val[0] == 0)
+ continue;
+ } else {
+ if (matchtbl[i].len % matchtbl[i].f->val[0] == 0)
+ continue;
+ }
+ break;
+ case LIST:
+ for (j = 0; j < matchtbl[i].f->len; j++)
+ if (matchtbl[i].f->val[j] == matchtbl[i].tm)
+ break;
+ if (j < matchtbl[i].f->len)
+ continue;
+ break;
+ default:
+ break;
+ }
+ break;
+ }
+ if (i != LEN(matchtbl))
+ return 0;
+ return 1;
+}
+
+static int
+parsefield(const char *field, long low, long high, struct field *f)
+{
+ int i;
+ char *e1, *e2;
+ const char *p;
+
+ p = field;
+ while (isdigit(*p))
+ p++;
+
+ f->type = ERROR;
+
+ switch (*p) {
+ case '*':
+ if (strcmp(field, "*") == 0) {
+ f->val = NULL;
+ f->len = 0;
+ f->type = WILDCARD;
+ } else if (strncmp(field, "*/", 2) == 0) {
+ f->val = emalloc(sizeof(*f->val));
+ f->len = 1;
+
+ errno = 0;
+ f->val[0] = strtol(field + 2, &e1, 10);
+ if (e1[0] != '\0' || errno != 0 || f->val[0] == 0)
+ break;
+
+ f->type = REPEAT;
+ }
+ break;
+ case '\0':
+ f->val = emalloc(sizeof(*f->val));
+ f->len = 1;
+
+ errno = 0;
+ f->val[0] = strtol(field, &e1, 10);
+ if (e1[0] != '\0' || errno != 0)
+ break;
+
+ f->type = NUMBER;
+ break;
+ case '-':
+ f->val = emalloc(2 * sizeof(*f->val));
+ f->len = 2;
+
+ errno = 0;
+ f->val[0] = strtol(field, &e1, 10);
+ if (e1[0] != '-' || errno != 0)
+ break;
+
+ errno = 0;
+ f->val[1] = strtol(e1 + 1, &e2, 10);
+ if (e2[0] != '\0' || errno != 0)
+ break;
+
+ f->type = RANGE;
+ break;
+ case ',':
+ for (i = 1; isdigit(*p) || *p == ','; p++)
+ if (*p == ',')
+ i++;
+ f->val = emalloc(i * sizeof(*f->val));
+ f->len = i;
+
+ errno = 0;
+ f->val[0] = strtol(field, &e1, 10);
+ if (f->val[0] < low || f->val[0] > high)
+ break;
+
+ for (i = 1; *e1 == ',' && errno == 0; i++) {
+ errno = 0;
+ f->val[i] = strtol(e1 + 1, &e2, 10);
+ e1 = e2;
+ }
+ if (e1[0] != '\0' || errno != 0)
+ break;
+
+ f->type = LIST;
+ break;
+ default:
+ return -1;
+ }
+
+ for (i = 0; i < f->len; i++)
+ if (f->val[i] < low || f->val[i] > high)
+ f->type = ERROR;
+
+ if (f->type == ERROR) {
+ free(f->val);
+ return -1;
+ }
+
+ return 0;
+}
+
+static void
+freecte(struct ctabentry *cte, int nfields)
+{
+ switch (nfields) {
+ case 6:
+ free(cte->cmd);
+ case 5:
+ free(cte->wday.val);
+ case 4:
+ free(cte->mon.val);
+ case 3:
+ free(cte->mday.val);
+ case 2:
+ free(cte->hour.val);
+ case 1:
+ free(cte->min.val);
+ }
+ free(cte);
+}
+
+static void
+unloadentries(void)
+{
+ struct ctabentry *cte, *tmp;
+
+ for (cte = TAILQ_FIRST(&ctabhead); cte; cte = tmp) {
+ tmp = TAILQ_NEXT(cte, entry);
+ TAILQ_REMOVE(&ctabhead, cte, entry);
+ freecte(cte, 6);
+ }
+}
+
+static int
+loadentries(void)
+{
+ struct ctabentry *cte;
+ FILE *fp;
+ char *line = NULL, *p, *col;
+ int r = 0, y;
+ size_t size = 0;
+ ssize_t len;
+ struct fieldlimits {
+ char *name;
+ long min;
+ long max;
+ struct field *f;
+ } flim[] = {
+ { "min", 0, 59, NULL },
+ { "hour", 0, 23, NULL },
+ { "mday", 1, 31, NULL },
+ { "mon", 1, 12, NULL },
+ { "wday", 0, 6, NULL }
+ };
+ size_t x;
+
+ if ((fp = fopen(config, "r")) == NULL) {
+ logerr("error: can't open %s: %s\n", config, strerror(errno));
+ return -1;
+ }
+
+ for (y = 0; (len = getline(&line, &size, fp)) != -1; y++) {
+ p = line;
+ if (line[0] == '#' || line[0] == '\n' || line[0] == '\0')
+ continue;
+
+ cte = emalloc(sizeof(*cte));
+ flim[0].f = &cte->min;
+ flim[1].f = &cte->hour;
+ flim[2].f = &cte->mday;
+ flim[3].f = &cte->mon;
+ flim[4].f = &cte->wday;
+
+ for (x = 0; x < LEN(flim); x++) {
+ do
+ col = strsep(&p, "\t\n ");
+ while (col && col[0] == '\0');
+
+ if (!col || parsefield(col, flim[x].min, flim[x].max, flim[x].f) < 0) {
+ logerr("error: failed to parse `%s' field on line %d\n",
+ flim[x].name, y + 1);
+ freecte(cte, x);
+ r = -1;
+ break;
+ }
+ }
+
+ if (r == -1)
+ break;
+
+ col = strsep(&p, "\n");
+ if (col)
+ while (col[0] == '\t' || col[0] == ' ')
+ col++;
+ if (!col || col[0] == '\0') {
+ logerr("error: missing `cmd' field on line %d\n",
+ y + 1);
+ freecte(cte, 5);
+ r = -1;
+ break;
+ }
+ cte->cmd = estrdup(col);
+
+ TAILQ_INSERT_TAIL(&ctabhead, cte, entry);
+ }
+
+ if (r < 0)
+ unloadentries();
+
+ free(line);
+ fclose(fp);
+
+ return r;
+}
+
+static void
+reloadentries(void)
+{
+ unloadentries();
+ if (loadentries() < 0)
+ logwarn("warning: discarding old crontab entries\n");
+}
+
+static void
+sighandler(int sig)
+{
+ switch (sig) {
+ case SIGCHLD:
+ chldreap = 1;
+ break;
+ case SIGHUP:
+ reload = 1;
+ break;
+ case SIGTERM:
+ quit = 1;
+ break;
+ }
+}
+
+static void
+usage(void)
+{
+ fprintf(stderr, VERSION " (c) 2014-2015\n");
+ fprintf(stderr, "usage: %s [-f file] [-n]\n", argv0);
+ fprintf(stderr, " -f config file\n");
+ fprintf(stderr, " -n do not daemonize\n");
+ exit(EXIT_FAILURE);
+}
+
+int
+main(int argc, char *argv[])
+{
+ FILE *fp;
+ struct ctabentry *cte;
+ time_t t;
+ struct tm *tm;
+ struct sigaction sa;
+
+ ARGBEGIN {
+ case 'n':
+ nflag = 1;
+ break;
+ case 'f':
+ config = EARGF(usage());
+ break;
+ default:
+ usage();
+ } ARGEND;
+
+ if (argc > 0)
+ usage();
+
+ if (nflag == 0) {
+ openlog(argv[0], LOG_CONS | LOG_PID, LOG_CRON);
+ if (daemon(1, 0) < 0) {
+ logerr("error: failed to daemonize %s\n", strerror(errno));
+ return EXIT_FAILURE;
+ }
+ if ((fp = fopen(pidfile, "w"))) {
+ fprintf(fp, "%d\n", getpid());
+ fclose(fp);
+ }
+ }
+
+ sa.sa_handler = sighandler;
+ sigfillset(&sa.sa_mask);
+ sa.sa_flags = SA_RESTART;
+ sigaction(SIGCHLD, &sa, NULL);
+ sigaction(SIGHUP, &sa, NULL);
+ sigaction(SIGTERM, &sa, NULL);
+
+ loadentries();
+
+ while (1) {
+ t = time(NULL);
+ sleep(60 - t % 60);
+
+ if (quit == 1) {
+ if (nflag == 0)
+ unlink(pidfile);
+ unloadentries();
+ /* Don't wait or kill forked processes, just exit */
+ break;
+ }
+
+ if (reload == 1 || chldreap == 1) {
+ if (reload == 1) {
+ reloadentries();
+ reload = 0;
+ }
+ if (chldreap == 1) {
+ waitjob();
+ chldreap = 0;
+ }
+ continue;
+ }
+
+ TAILQ_FOREACH(cte, &ctabhead, entry) {
+ t = time(NULL);
+ tm = localtime(&t);
+ if (matchentry(cte, tm) == 1)
+ runjob(cte->cmd);
+ }
+ }
+
+ if (nflag == 0)
+ closelog();
+
+ return EXIT_SUCCESS;
+}
diff --git a/queue.h b/queue.h
@@ -0,0 +1,648 @@
+/* $OpenBSD: queue.h,v 1.38 2013/07/03 15:05:21 fgsch Exp $ */
+/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
+
+/*
+ * Copyright (c) 1991, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * @(#)queue.h 8.5 (Berkeley) 8/20/94
+ */
+
+#ifndef _SYS_QUEUE_H_
+#define _SYS_QUEUE_H_
+
+/*
+ * This file defines five types of data structures: singly-linked lists,
+ * lists, simple queues, tail queues, and circular queues.
+ *
+ *
+ * A singly-linked list is headed by a single forward pointer. The elements
+ * are singly linked for minimum space and pointer manipulation overhead at
+ * the expense of O(n) removal for arbitrary elements. New elements can be
+ * added to the list after an existing element or at the head of the list.
+ * Elements being removed from the head of the list should use the explicit
+ * macro for this purpose for optimum efficiency. A singly-linked list may
+ * only be traversed in the forward direction. Singly-linked lists are ideal
+ * for applications with large datasets and few or no removals or for
+ * implementing a LIFO queue.
+ *
+ * A list is headed by a single forward pointer (or an array of forward
+ * pointers for a hash table header). The elements are doubly linked
+ * so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before
+ * or after an existing element or at the head of the list. A list
+ * may only be traversed in the forward direction.
+ *
+ * A simple queue is headed by a pair of pointers, one the head of the
+ * list and the other to the tail of the list. The elements are singly
+ * linked to save space, so elements can only be removed from the
+ * head of the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the
+ * list. A simple queue may only be traversed in the forward direction.
+ *
+ * A tail queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or
+ * after an existing element, at the head of the list, or at the end of
+ * the list. A tail queue may be traversed in either direction.
+ *
+ * A circle queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the list.
+ * A circle queue may be traversed in either direction, but has a more
+ * complex end of list detection.
+ *
+ * For details on the use of these macros, see the queue(3) manual page.
+ */
+
+#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
+#define _Q_INVALIDATE(a) (a) = ((void *)-1)
+#else
+#define _Q_INVALIDATE(a)
+#endif
+
+/*
+ * Singly-linked List definitions.
+ */
+#define SLIST_HEAD(name, type) \
+struct name { \
+ struct type *slh_first; /* first element */ \
+}
+
+#define SLIST_HEAD_INITIALIZER(head) \
+ { NULL }
+
+#define SLIST_ENTRY(type) \
+struct { \
+ struct type *sle_next; /* next element */ \
+}
+
+/*
+ * Singly-linked List access methods.
+ */
+#define SLIST_FIRST(head) ((head)->slh_first)
+#define SLIST_END(head) NULL
+#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
+#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
+
+#define SLIST_FOREACH(var, head, field) \
+ for((var) = SLIST_FIRST(head); \
+ (var) != SLIST_END(head); \
+ (var) = SLIST_NEXT(var, field))
+
+#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = SLIST_FIRST(head); \
+ (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
+ (var) = (tvar))
+
+/*
+ * Singly-linked List functions.
+ */
+#define SLIST_INIT(head) { \
+ SLIST_FIRST(head) = SLIST_END(head); \
+}
+
+#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
+ (elm)->field.sle_next = (slistelm)->field.sle_next; \
+ (slistelm)->field.sle_next = (elm); \
+} while (0)
+
+#define SLIST_INSERT_HEAD(head, elm, field) do { \
+ (elm)->field.sle_next = (head)->slh_first; \
+ (head)->slh_first = (elm); \
+} while (0)
+
+#define SLIST_REMOVE_AFTER(elm, field) do { \
+ (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
+} while (0)
+
+#define SLIST_REMOVE_HEAD(head, field) do { \
+ (head)->slh_first = (head)->slh_first->field.sle_next; \
+} while (0)
+
+#define SLIST_REMOVE(head, elm, type, field) do { \
+ if ((head)->slh_first == (elm)) { \
+ SLIST_REMOVE_HEAD((head), field); \
+ } else { \
+ struct type *curelm = (head)->slh_first; \
+ \
+ while (curelm->field.sle_next != (elm)) \
+ curelm = curelm->field.sle_next; \
+ curelm->field.sle_next = \
+ curelm->field.sle_next->field.sle_next; \
+ _Q_INVALIDATE((elm)->field.sle_next); \
+ } \
+} while (0)
+
+/*
+ * List definitions.
+ */
+#define LIST_HEAD(name, type) \
+struct name { \
+ struct type *lh_first; /* first element */ \
+}
+
+#define LIST_HEAD_INITIALIZER(head) \
+ { NULL }
+
+#define LIST_ENTRY(type) \
+struct { \
+ struct type *le_next; /* next element */ \
+ struct type **le_prev; /* address of previous next element */ \
+}
+
+/*
+ * List access methods
+ */
+#define LIST_FIRST(head) ((head)->lh_first)
+#define LIST_END(head) NULL
+#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
+#define LIST_NEXT(elm, field) ((elm)->field.le_next)
+
+#define LIST_FOREACH(var, head, field) \
+ for((var) = LIST_FIRST(head); \
+ (var)!= LIST_END(head); \
+ (var) = LIST_NEXT(var, field))
+
+#define LIST_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = LIST_FIRST(head); \
+ (var) && ((tvar) = LIST_NEXT(var, field), 1); \
+ (var) = (tvar))
+
+/*
+ * List functions.
+ */
+#define LIST_INIT(head) do { \
+ LIST_FIRST(head) = LIST_END(head); \
+} while (0)
+
+#define LIST_INSERT_AFTER(listelm, elm, field) do { \
+ if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
+ (listelm)->field.le_next->field.le_prev = \
+ &(elm)->field.le_next; \
+ (listelm)->field.le_next = (elm); \
+ (elm)->field.le_prev = &(listelm)->field.le_next; \
+} while (0)
+
+#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.le_prev = (listelm)->field.le_prev; \
+ (elm)->field.le_next = (listelm); \
+ *(listelm)->field.le_prev = (elm); \
+ (listelm)->field.le_prev = &(elm)->field.le_next; \
+} while (0)
+
+#define LIST_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.le_next = (head)->lh_first) != NULL) \
+ (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
+ (head)->lh_first = (elm); \
+ (elm)->field.le_prev = &(head)->lh_first; \
+} while (0)
+
+#define LIST_REMOVE(elm, field) do { \
+ if ((elm)->field.le_next != NULL) \
+ (elm)->field.le_next->field.le_prev = \
+ (elm)->field.le_prev; \
+ *(elm)->field.le_prev = (elm)->field.le_next; \
+ _Q_INVALIDATE((elm)->field.le_prev); \
+ _Q_INVALIDATE((elm)->field.le_next); \
+} while (0)
+
+#define LIST_REPLACE(elm, elm2, field) do { \
+ if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
+ (elm2)->field.le_next->field.le_prev = \
+ &(elm2)->field.le_next; \
+ (elm2)->field.le_prev = (elm)->field.le_prev; \
+ *(elm2)->field.le_prev = (elm2); \
+ _Q_INVALIDATE((elm)->field.le_prev); \
+ _Q_INVALIDATE((elm)->field.le_next); \
+} while (0)
+
+/*
+ * Simple queue definitions.
+ */
+#define SIMPLEQ_HEAD(name, type) \
+struct name { \
+ struct type *sqh_first; /* first element */ \
+ struct type **sqh_last; /* addr of last next element */ \
+}
+
+#define SIMPLEQ_HEAD_INITIALIZER(head) \
+ { NULL, &(head).sqh_first }
+
+#define SIMPLEQ_ENTRY(type) \
+struct { \
+ struct type *sqe_next; /* next element */ \
+}
+
+/*
+ * Simple queue access methods.
+ */
+#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
+#define SIMPLEQ_END(head) NULL
+#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
+#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
+
+#define SIMPLEQ_FOREACH(var, head, field) \
+ for((var) = SIMPLEQ_FIRST(head); \
+ (var) != SIMPLEQ_END(head); \
+ (var) = SIMPLEQ_NEXT(var, field))
+
+#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = SIMPLEQ_FIRST(head); \
+ (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
+ (var) = (tvar))
+
+/*
+ * Simple queue functions.
+ */
+#define SIMPLEQ_INIT(head) do { \
+ (head)->sqh_first = NULL; \
+ (head)->sqh_last = &(head)->sqh_first; \
+} while (0)
+
+#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
+ (head)->sqh_last = &(elm)->field.sqe_next; \
+ (head)->sqh_first = (elm); \
+} while (0)
+
+#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.sqe_next = NULL; \
+ *(head)->sqh_last = (elm); \
+ (head)->sqh_last = &(elm)->field.sqe_next; \
+} while (0)
+
+#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
+ (head)->sqh_last = &(elm)->field.sqe_next; \
+ (listelm)->field.sqe_next = (elm); \
+} while (0)
+
+#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
+ if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
+ (head)->sqh_last = &(head)->sqh_first; \
+} while (0)
+
+#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
+ if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
+ == NULL) \
+ (head)->sqh_last = &(elm)->field.sqe_next; \
+} while (0)
+
+/*
+ * XOR Simple queue definitions.
+ */
+#define XSIMPLEQ_HEAD(name, type) \
+struct name { \
+ struct type *sqx_first; /* first element */ \
+ struct type **sqx_last; /* addr of last next element */ \
+ unsigned long sqx_cookie; \
+}
+
+#define XSIMPLEQ_ENTRY(type) \
+struct { \
+ struct type *sqx_next; /* next element */ \
+}
+
+/*
+ * XOR Simple queue access methods.
+ */
+#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
+ (unsigned long)(ptr)))
+#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
+#define XSIMPLEQ_END(head) NULL
+#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
+#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
+
+
+#define XSIMPLEQ_FOREACH(var, head, field) \
+ for ((var) = XSIMPLEQ_FIRST(head); \
+ (var) != XSIMPLEQ_END(head); \
+ (var) = XSIMPLEQ_NEXT(head, var, field))
+
+#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = XSIMPLEQ_FIRST(head); \
+ (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
+ (var) = (tvar))
+
+/*
+ * XOR Simple queue functions.
+ */
+#define XSIMPLEQ_INIT(head) do { \
+ arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
+ (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
+ (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
+} while (0)
+
+#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.sqx_next = (head)->sqx_first) == \
+ XSIMPLEQ_XOR(head, NULL)) \
+ (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
+ (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
+} while (0)
+
+#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
+ *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
+ (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
+} while (0)
+
+#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
+ XSIMPLEQ_XOR(head, NULL)) \
+ (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
+ (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
+} while (0)
+
+#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
+ if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
+ (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
+ (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
+} while (0)
+
+#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
+ if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
+ (elm)->field.sqx_next)->field.sqx_next) \
+ == XSIMPLEQ_XOR(head, NULL)) \
+ (head)->sqx_last = \
+ XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
+} while (0)
+
+
+/*
+ * Tail queue definitions.
+ */
+#define TAILQ_HEAD(name, type) \
+struct name { \
+ struct type *tqh_first; /* first element */ \
+ struct type **tqh_last; /* addr of last next element */ \
+}
+
+#define TAILQ_HEAD_INITIALIZER(head) \
+ { NULL, &(head).tqh_first }
+
+#define TAILQ_ENTRY(type) \
+struct { \
+ struct type *tqe_next; /* next element */ \
+ struct type **tqe_prev; /* address of previous next element */ \
+}
+
+/*
+ * tail queue access methods
+ */
+#define TAILQ_FIRST(head) ((head)->tqh_first)
+#define TAILQ_END(head) NULL
+#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
+#define TAILQ_LAST(head, headname) \
+ (*(((struct headname *)((head)->tqh_last))->tqh_last))
+/* XXX */
+#define TAILQ_PREV(elm, headname, field) \
+ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+#define TAILQ_EMPTY(head) \
+ (TAILQ_FIRST(head) == TAILQ_END(head))
+
+#define TAILQ_FOREACH(var, head, field) \
+ for((var) = TAILQ_FIRST(head); \
+ (var) != TAILQ_END(head); \
+ (var) = TAILQ_NEXT(var, field))
+
+#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = TAILQ_FIRST(head); \
+ (var) != TAILQ_END(head) && \
+ ((tvar) = TAILQ_NEXT(var, field), 1); \
+ (var) = (tvar))
+
+
+#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
+ for((var) = TAILQ_LAST(head, headname); \
+ (var) != TAILQ_END(head); \
+ (var) = TAILQ_PREV(var, headname, field))
+
+#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
+ for ((var) = TAILQ_LAST(head, headname); \
+ (var) != TAILQ_END(head) && \
+ ((tvar) = TAILQ_PREV(var, headname, field), 1); \
+ (var) = (tvar))
+
+/*
+ * Tail queue functions.
+ */
+#define TAILQ_INIT(head) do { \
+ (head)->tqh_first = NULL; \
+ (head)->tqh_last = &(head)->tqh_first; \
+} while (0)
+
+#define TAILQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
+ (head)->tqh_first->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (head)->tqh_first = (elm); \
+ (elm)->field.tqe_prev = &(head)->tqh_first; \
+} while (0)
+
+#define TAILQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.tqe_next = NULL; \
+ (elm)->field.tqe_prev = (head)->tqh_last; \
+ *(head)->tqh_last = (elm); \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+} while (0)
+
+#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
+ (elm)->field.tqe_next->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (listelm)->field.tqe_next = (elm); \
+ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
+} while (0)
+
+#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
+ (elm)->field.tqe_next = (listelm); \
+ *(listelm)->field.tqe_prev = (elm); \
+ (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
+} while (0)
+
+#define TAILQ_REMOVE(head, elm, field) do { \
+ if (((elm)->field.tqe_next) != NULL) \
+ (elm)->field.tqe_next->field.tqe_prev = \
+ (elm)->field.tqe_prev; \
+ else \
+ (head)->tqh_last = (elm)->field.tqe_prev; \
+ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
+ _Q_INVALIDATE((elm)->field.tqe_prev); \
+ _Q_INVALIDATE((elm)->field.tqe_next); \
+} while (0)
+
+#define TAILQ_REPLACE(head, elm, elm2, field) do { \
+ if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
+ (elm2)->field.tqe_next->field.tqe_prev = \
+ &(elm2)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm2)->field.tqe_next; \
+ (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
+ *(elm2)->field.tqe_prev = (elm2); \
+ _Q_INVALIDATE((elm)->field.tqe_prev); \
+ _Q_INVALIDATE((elm)->field.tqe_next); \
+} while (0)
+
+/*
+ * Circular queue definitions.
+ */
+#define CIRCLEQ_HEAD(name, type) \
+struct name { \
+ struct type *cqh_first; /* first element */ \
+ struct type *cqh_last; /* last element */ \
+}
+
+#define CIRCLEQ_HEAD_INITIALIZER(head) \
+ { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
+
+#define CIRCLEQ_ENTRY(type) \
+struct { \
+ struct type *cqe_next; /* next element */ \
+ struct type *cqe_prev; /* previous element */ \
+}
+
+/*
+ * Circular queue access methods
+ */
+#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
+#define CIRCLEQ_LAST(head) ((head)->cqh_last)
+#define CIRCLEQ_END(head) ((void *)(head))
+#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
+#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
+#define CIRCLEQ_EMPTY(head) \
+ (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
+
+#define CIRCLEQ_FOREACH(var, head, field) \
+ for((var) = CIRCLEQ_FIRST(head); \
+ (var) != CIRCLEQ_END(head); \
+ (var) = CIRCLEQ_NEXT(var, field))
+
+#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
+ for ((var) = CIRCLEQ_FIRST(head); \
+ (var) != CIRCLEQ_END(head) && \
+ ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
+ (var) = (tvar))
+
+#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
+ for((var) = CIRCLEQ_LAST(head); \
+ (var) != CIRCLEQ_END(head); \
+ (var) = CIRCLEQ_PREV(var, field))
+
+#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
+ for ((var) = CIRCLEQ_LAST(head, headname); \
+ (var) != CIRCLEQ_END(head) && \
+ ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
+ (var) = (tvar))
+
+/*
+ * Circular queue functions.
+ */
+#define CIRCLEQ_INIT(head) do { \
+ (head)->cqh_first = CIRCLEQ_END(head); \
+ (head)->cqh_last = CIRCLEQ_END(head); \
+} while (0)
+
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ (elm)->field.cqe_next = (listelm)->field.cqe_next; \
+ (elm)->field.cqe_prev = (listelm); \
+ if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
+ (head)->cqh_last = (elm); \
+ else \
+ (listelm)->field.cqe_next->field.cqe_prev = (elm); \
+ (listelm)->field.cqe_next = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
+ (elm)->field.cqe_next = (listelm); \
+ (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
+ if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
+ (head)->cqh_first = (elm); \
+ else \
+ (listelm)->field.cqe_prev->field.cqe_next = (elm); \
+ (listelm)->field.cqe_prev = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
+ (elm)->field.cqe_next = (head)->cqh_first; \
+ (elm)->field.cqe_prev = CIRCLEQ_END(head); \
+ if ((head)->cqh_last == CIRCLEQ_END(head)) \
+ (head)->cqh_last = (elm); \
+ else \
+ (head)->cqh_first->field.cqe_prev = (elm); \
+ (head)->cqh_first = (elm); \
+} while (0)
+
+#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.cqe_next = CIRCLEQ_END(head); \
+ (elm)->field.cqe_prev = (head)->cqh_last; \
+ if ((head)->cqh_first == CIRCLEQ_END(head)) \
+ (head)->cqh_first = (elm); \
+ else \
+ (head)->cqh_last->field.cqe_next = (elm); \
+ (head)->cqh_last = (elm); \
+} while (0)
+
+#define CIRCLEQ_REMOVE(head, elm, field) do { \
+ if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
+ (head)->cqh_last = (elm)->field.cqe_prev; \
+ else \
+ (elm)->field.cqe_next->field.cqe_prev = \
+ (elm)->field.cqe_prev; \
+ if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
+ (head)->cqh_first = (elm)->field.cqe_next; \
+ else \
+ (elm)->field.cqe_prev->field.cqe_next = \
+ (elm)->field.cqe_next; \
+ _Q_INVALIDATE((elm)->field.cqe_prev); \
+ _Q_INVALIDATE((elm)->field.cqe_next); \
+} while (0)
+
+#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
+ if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
+ CIRCLEQ_END(head)) \
+ (head)->cqh_last = (elm2); \
+ else \
+ (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
+ if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
+ CIRCLEQ_END(head)) \
+ (head)->cqh_first = (elm2); \
+ else \
+ (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
+ _Q_INVALIDATE((elm)->field.cqe_prev); \
+ _Q_INVALIDATE((elm)->field.cqe_next); \
+} while (0)
+
+#endif /* !_SYS_QUEUE_H_ */
diff --git a/scron.1 b/scron.1
@@ -0,0 +1,45 @@
+.Dd Feb 6, 2015
+.Dt SCRON 1
+.Os
+.Sh NAME
+.Nm scron
+.Nd clock daemon
+.Sh SYNOPSIS
+.Nm
+.Op Fl f Ar file
+.Op Fl n
+.Sh DESCRIPTION
+.Nm
+schedules commands to be run at specified dates and times.
+.Pp
+.Sh OPTIONS
+.Bl -tag -width Ds
+.It Fl f Ar file
+Use the specified
+.Ar file
+instead of the default
+.Ar /etc/crontab .
+.It Fl n
+Do not daemonize.
+.El
+.Sh CONFIGURATION
+Configuration is done by editing the crontab file.
+
+Columns:
+ minute, hour, day of month, month, day of week, command
+
+Separator:
+ Any number of tabs or spaces.
+
+Value:
+ * (wildcard), 30 (number), */N (repeat), 1-5 (range), or 1,3,6 (list)
+.Sh EXAMPLE
+Example of crontab file:
+ # Run updatedb at 6:00 every day
+ 0 6 * * * updatedb
+
+ # Run at 5:30 every business day. Log output to /var/log/backup.log.
+ 30 5 * * 1-5 syncbackup &>> /var/log/backup.log
+
+ # Run as user postmaster at 5:00 every third day of month.
+ 0 5 */3 * * su -c 'mail -s "Hello world" a@b.com' postmaster
