diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | README | 47 | ||||
| -rw-r--r-- | sfeed_tail.1 | 41 | ||||
| -rw-r--r-- | sfeed_tail.c | 185 | ||||
| -rw-r--r-- | tree.h | 758 |
5 files changed, 0 insertions, 1033 deletions
@@ -14,7 +14,6 @@ BIN = \ sfeed_mbox\ sfeed_opml_import\ sfeed_plain\ - sfeed_tail\ sfeed_twtxt\ sfeed_web\ sfeed_xmlenc @@ -24,7 +23,6 @@ SCRIPTS = \ SRC = ${BIN:=.c} HDR = \ - tree.h\ util.h\ xml.h @@ -128,7 +128,6 @@ sfeed_opml_export - Generate an OPML XML file from a sfeedrc config file. sfeed_opml_import - Generate a sfeedrc config file from an OPML XML file. sfeed_mbox - Format feed data (TSV) to mbox. sfeed_plain - Format feed data (TSV) to a plain-text list. -sfeed_tail - Format unseen feed data (TSV) to a plain-text list. sfeed_twtxt - Format feed data (TSV) to a twtxt feed. sfeed_update - Update feeds and merge with old feeds in the directory $HOME/.sfeed/feeds by default. @@ -508,52 +507,6 @@ Now run: Now you can view feeds in mutt(1) for example. -Security considerations ------------------------ - -About automated remote resource loading and content execution: - -Some feeds will use a tracking pixel (1x1 image size) in HTML content with some -unique ID. Some even have embedded Javascript code, iframes, CSS. Opening such -content and loading these resources automatically may leak unwanted -information. - -For example on Slashdot: -<img src="http://feeds.feedburner.com/~r/Slashdot/slashdot/~4/someid" - height="1" width="1" alt=""/> - -If such content is opened in a typical webbrowser configuration this is -insecure. Be aware opening a link in a page generated on the local filesystem -or network has different privileges than one on a non-local domain. - -Recommendation: -Do not handle content as HTML and avoid automated remote resource loading in -content. Convert all content to plain-text in your formatting program. - - -About handling links: - -Be careful about handling feed links. - -A malicious link could be: tel:some-phonenumber, file:// or some other protocol -scheme which depending on the viewing program and system can have an action -assigned. - -Another malicious link could be pointing to a local device, for example an -(insecure) router: http://192.168.0.1/?reboot - -Recommendation: -Filter specific by protocol and non-local domain. This can be done using a grep -or awk filter or as a setting in your viewing program. - -See also: -- RFC4287 (Atom): 8. Security Considerations: - https://tools.ietf.org/html/rfc4287#section-8 -- RFC2854: 7. Security Considerations: - https://tools.ietf.org/html/rfc2854 -- Filter examples: see the sfeed README file. - - License ------- diff --git a/sfeed_tail.1 b/sfeed_tail.1 deleted file mode 100644 index 955c423..0000000 --- a/sfeed_tail.1 +++ /dev/null @@ -1,41 +0,0 @@ -.Dd December 14, 2018 -.Dt SFEED_TAIL 1 -.Os -.Sh NAME -.Nm sfeed_tail -.Nd format unseen feed data to a plain-text list -.Sh SYNOPSIS -.Nm -.Ar file... -.Sh DESCRIPTION -.Nm -formats only new and unseen feed data (TSV) from -one or more -.Ar file -to stdout as a plain-text list. -The basename of the -.Ar file -is used as the feed name in the output. -.Pp -Unseen items are printed per line in a similar format to -.Xr sfeed_plain 1 , -duplicate items are ignored. -The list of unique items is determined by the fields: item id, item link and -UNIX timestamp of the item date. -.Pp -.Nm -will also only process and show items that are considered new: the item -timestamp is not older than a day ago. -.Sh IMPLEMENTATION NOTES -.Nm -checks for file modifications every 10 seconds by checking the filesize and -modification time. -Keep in mind that because -.Nm -keeps a list of items it can potentially consume much memory. -.Sh SEE ALSO -.Xr sfeed 1 , -.Xr sfeed_plain 1 , -.Xr tail 1 -.Sh AUTHORS -.An Hiltjo Posthuma Aq Mt hiltjo@codemadness.org diff --git a/sfeed_tail.c b/sfeed_tail.c deleted file mode 100644 index d611cbc..0000000 --- a/sfeed_tail.c +++ /dev/null @@ -1,185 +0,0 @@ -#include <sys/stat.h> -#include <sys/types.h> - -#include <ctype.h> -#include <err.h> -#include <locale.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> - -#include "tree.h" -#include "util.h" - -static char *line; -static size_t linesize; -static int changed, firsttime = 1; -static time_t comparetime; - -struct line { - char *id; - char *link; - char *title; - time_t timestamp; - RB_ENTRY(line) entry; -}; - -int -linecmp(struct line *e1, struct line *e2) -{ - int r; - - if ((r = strcmp(e1->id, e2->id))) - return r; - else if ((r = strcmp(e1->title, e2->title))) - return r; - return strcmp(e1->link, e2->link); -} -RB_HEAD(linetree, line) head = RB_INITIALIZER(&head); -RB_GENERATE_STATIC(linetree, line, entry, linecmp) - -/* remove old entries from the tree that won't be shown anyway. */ -static void -gc(void) -{ - struct line *l, *tmp; - - RB_FOREACH_SAFE(l, linetree, &head, tmp) { - if (l->timestamp < comparetime) { - free(l->id); - free(l->link); - free(l->title); - RB_REMOVE(linetree, &head, l); - free(l); - } - } -} - -static void -printfeed(FILE *fp, const char *feedname) -{ - struct line *add, search; - char *fields[FieldLast]; - ssize_t linelen; - time_t parsedtime; - struct tm *tm; - - while ((linelen = getline(&line, &linesize, fp)) > 0) { - if (line[linelen - 1] == '\n') - line[--linelen] = '\0'; - - if (!parseline(line, fields)) - break; - parsedtime = 0; - if (strtotime(fields[FieldUnixTimestamp], &parsedtime)) - continue; - if (!(tm = localtime(&parsedtime))) - err(1, "localtime"); - - /* old news: skip */ - if (parsedtime < comparetime) - continue; - - search.id = fields[FieldId]; - search.link = fields[FieldLink]; - search.title = fields[FieldTitle]; - search.timestamp = parsedtime; - if (RB_FIND(linetree, &head, &search)) - continue; - - changed = 1; - - if (!(add = calloc(1, sizeof(*add)))) - err(1, "calloc"); - if (!(add->id = strdup(fields[FieldId]))) - err(1, "strdup"); - if (!(add->link = strdup(fields[FieldLink]))) - err(1, "strdup"); - if (!(add->title = strdup(fields[FieldTitle]))) - err(1, "strdup"); - add->timestamp = parsedtime; - RB_INSERT(linetree, &head, add); - - if (feedname[0]) { - printutf8pad(stdout, feedname, 15, ' '); - fputs(" ", stdout); - } - - fprintf(stdout, "%04d-%02d-%02d %02d:%02d ", - tm->tm_year + 1900, tm->tm_mon + 1, tm->tm_mday, - tm->tm_hour, tm->tm_min); - printutf8pad(stdout, fields[FieldTitle], 70, ' '); - printf(" %s\n", fields[FieldLink]); - } -} - -int -main(int argc, char *argv[]) -{ - struct stat *stfiles, st; - char *name; - FILE *fp; - int i, slept = 0; - - if (pledge("stdio rpath", NULL) == -1) - err(1, "pledge"); - - if (argc <= 1) { - fprintf(stderr, "usage: %s <file>...\n", argv[0]); - return 1; - } - - setlocale(LC_CTYPE, ""); - - if (!(stfiles = calloc(argc - 1, sizeof(*stfiles)))) - err(1, "calloc"); - - while (1) { - changed = 0; - - if ((comparetime = time(NULL)) == -1) - err(1, "time"); - /* 1 day is old news */ - comparetime -= 86400; - - for (i = 1; i < argc; i++) { - if (!(fp = fopen(argv[i], "r"))) { - if (firsttime) - err(1, "fopen: %s", argv[i]); - /* don't report when the file is missing after the first run */ - continue; - } - if (fstat(fileno(fp), &st) == -1) { - if (firsttime) - err(1, "fstat: %s", argv[i]); - warn("fstat: %s", argv[i]); - fclose(fp); - continue; - } - - /* did the file change? by size or modification time */ - if (stfiles[i - 1].st_size != st.st_size || - stfiles[i - 1].st_mtime != st.st_mtime) { - name = ((name = strrchr(argv[i], '/'))) ? name + 1 : argv[i]; - printfeed(fp, name); - if (ferror(fp)) - warn("ferror: %s", argv[i]); - memcpy(&stfiles[i - 1], &st, sizeof(st)); - } - - fclose(fp); - } - - /* "garbage collect" on a change or every 5 minutes */ - if (changed || slept > 300) { - gc(); - changed = 0; - slept = 0; - } - sleep(10); - slept += 10; - firsttime = 0; - } - return 0; -} @@ -1,758 +0,0 @@ -/* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */ -/* - * Copyright 2002 Niels Provos <provos@citi.umich.edu> - * 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. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. - */ - -#ifndef _SYS_TREE_H_ -#define _SYS_TREE_H_ - -/* - * This file defines data structures for red-black trees. - * - * A red-black tree is a binary search tree with the node color as an - * extra attribute. It fulfills a set of conditions: - * - every search path from the root to a leaf consists of the - * same number of black nodes, - * - each red node (except for the root) has a black parent, - * - each leaf node is black. - * - * Every operation on a red-black tree is bounded as O(lg n). - * The maximum height of a red-black tree is 2lg (n+1). - */ - -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ -} while (0) - -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (0) - -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif - -#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) - -#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RB_INSERT(struct name *, struct type *); \ -attr struct type *name##_RB_FIND(struct name *, struct type *); \ -attr struct type *name##_RB_NFIND(struct name *, struct type *); \ -attr struct type *name##_RB_NEXT(struct type *); \ -attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ - \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ -{ \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) && \ - RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ -} \ - \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ -{ \ - struct type *tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RB_LEFT(tmp, field)))\ - RB_COLOR(oleft, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RB_RIGHT(tmp, field)))\ - RB_COLOR(oright, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ -} \ - \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field))) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field))); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ -} \ - \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RB_INSERT(struct name *head, struct type *elm) \ -{ \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ -} \ - \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RB_FIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ -} \ - \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_NEXT(struct type *elm) \ -{ \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ -{ \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -attr struct type * \ -name##_RB_MINMAX(struct name *head, int val) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ -} - -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ - (x) = (y)) - - -/* - * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -struct rb_type { - int (*t_compare)(const void *, const void *); - void (*t_augment)(void *); - unsigned int t_offset; /* offset of rb_entry in type */ -}; - -struct rb_tree { - struct rb_entry *rbt_root; -}; - -struct rb_entry { - struct rb_entry *rbt_parent; - struct rb_entry *rbt_left; - struct rb_entry *rbt_right; - unsigned int rbt_color; -}; - -#define RBT_HEAD(_name, _type) \ -struct _name { \ - struct rb_tree rbh_root; \ -} - -#define RBT_ENTRY(_type) struct rb_entry - -static inline void -_rb_init(struct rb_tree *rbt) -{ - rbt->rbt_root = NULL; -} - -static inline int -_rb_empty(struct rb_tree *rbt) -{ - return (rbt->rbt_root == NULL); -} - -void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); -void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); -void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_root(const struct rb_type *, struct rb_tree *); -void *_rb_min(const struct rb_type *, struct rb_tree *); -void *_rb_max(const struct rb_type *, struct rb_tree *); -void *_rb_next(const struct rb_type *, void *); -void *_rb_prev(const struct rb_type *, void *); -void *_rb_left(const struct rb_type *, void *); -void *_rb_right(const struct rb_type *, void *); -void *_rb_parent(const struct rb_type *, void *); -void _rb_set_left(const struct rb_type *, void *, void *); -void _rb_set_right(const struct rb_type *, void *, void *); -void _rb_set_parent(const struct rb_type *, void *, void *); -void _rb_poison(const struct rb_type *, void *, unsigned long); -int _rb_check(const struct rb_type *, void *, unsigned long); - -#define RBT_INITIALIZER(_head) { { NULL } } - -#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ -extern const struct rb_type *const _name##_RBT_TYPE; \ - \ -__unused static inline void \ -_name##_RBT_INIT(struct _name *head) \ -{ \ - _rb_init(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ -{ \ - return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ -{ \ - return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_FIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_ROOT(struct _name *head) \ -{ \ - return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline int \ -_name##_RBT_EMPTY(struct _name *head) \ -{ \ - return _rb_empty(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MIN(struct _name *head) \ -{ \ - return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MAX(struct _name *head) \ -{ \ - return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NEXT(struct _type *elm) \ -{ \ - return _rb_next(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PREV(struct _type *elm) \ -{ \ - return _rb_prev(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_LEFT(struct _type *elm) \ -{ \ - return _rb_left(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_RIGHT(struct _type *elm) \ -{ \ - return _rb_right(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PARENT(struct _type *elm) \ -{ \ - return _rb_parent(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ -{ \ - return _rb_set_left(_name##_RBT_TYPE, elm, left); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ -{ \ - return _rb_set_right(_name##_RBT_TYPE, elm, right); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ -{ \ - return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ -} \ - \ -__unused static inline void \ -_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_poison(_name##_RBT_TYPE, elm, poison); \ -} \ - \ -__unused static inline int \ -_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_check(_name##_RBT_TYPE, elm, poison); \ -} - -#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ -static int \ -_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ -{ \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ -} \ -static const struct rb_type _name##_RBT_INFO = { \ - _name##_RBT_COMPARE, \ - _aug, \ - offsetof(struct _type, _field), \ -}; \ -const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO - -#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ -static void \ -_name##_RBT_AUGMENT(void *ptr) \ -{ \ - struct _type *p = ptr; \ - return _aug(p); \ -} \ -RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) - -#define RBT_GENERATE(_name, _type, _field, _cmp) \ - RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) - -#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) -#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) -#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) -#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) -#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) -#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) -#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) -#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) -#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) -#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) -#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) -#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) -#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) -#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) -#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) -#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) -#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) -#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) -#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) - -#define RBT_FOREACH(_e, _name, _head) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_NEXT(_name, (_e))) - -#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ - (_e) = (_n)) - -#define RBT_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_PREV(_name, (_e))) - -#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ - (_e) = (_n)) - -#endif /* _SYS_TREE_H_ */ |