iAdd caching support - dedup - deduplicating backup program Err bitreich.org 70 hgit clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ URL:git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/ bitreich.org 70 1Log /scm/dedup/log.gph bitreich.org 70 1Files /scm/dedup/files.gph bitreich.org 70 1Refs /scm/dedup/refs.gph bitreich.org 70 1Tags /scm/dedup/tag bitreich.org 70 1README /scm/dedup/file/README.gph bitreich.org 70 1LICENSE /scm/dedup/file/LICENSE.gph bitreich.org 70 i--- Err bitreich.org 70 1commit f555828eafd191899b749a9e41b1bc006206ef62 /scm/dedup/commit/f555828eafd191899b749a9e41b1bc006206ef62.gph bitreich.org 70 1parent c0f3292de8c30657c13d7564a0655e65df8e0459 /scm/dedup/commit/c0f3292de8c30657c13d7564a0655e65df8e0459.gph bitreich.org 70 hAuthor: sin URL:mailto:sin@2f30.org bitreich.org 70 iDate: Wed, 21 Mar 2018 11:57:07 +0000 Err bitreich.org 70 i Err bitreich.org 70 iAdd caching support Err bitreich.org 70 i Err bitreich.org 70 iDiffstat: Err bitreich.org 70 i M Makefile | 4 ++-- Err bitreich.org 70 i M dedup.c | 153 +++++++++++++++++++++++++------ Err bitreich.org 70 i A tree.h | 1016 +++++++++++++++++++++++++++++++ Err bitreich.org 70 i Err bitreich.org 70 i3 files changed, 1144 insertions(+), 29 deletions(-) Err bitreich.org 70 i--- Err bitreich.org 70 1diff --git a/Makefile b/Makefile /scm/dedup/file/Makefile.gph bitreich.org 70 i@@ -3,7 +3,7 @@ PREFIX = /usr/local Err bitreich.org 70 i SRC = dedup.c Err bitreich.org 70 i OBJ = dedup.o Err bitreich.org 70 i BIN = dedup Err bitreich.org 70 i-DISTFILES = $(SRC) LICENSE Makefile arg.h Err bitreich.org 70 i+DISTFILES = $(SRC) LICENSE Makefile arg.h tree.h Err bitreich.org 70 i Err bitreich.org 70 i CFLAGS = -g -Wall Err bitreich.org 70 i CPPFLAGS = -I/usr/local/include Err bitreich.org 70 i@@ -11,7 +11,7 @@ LDLIBS = -lcrypto Err bitreich.org 70 i Err bitreich.org 70 i all: $(BIN) Err bitreich.org 70 i Err bitreich.org 70 i-dedup.o: arg.h Err bitreich.org 70 i+dedup.o: arg.h tree.h Err bitreich.org 70 i Err bitreich.org 70 i clean: Err bitreich.org 70 i rm -f $(OBJ) $(BIN) $(BIN)-$(VERSION).tar.gz Err bitreich.org 70 1diff --git a/dedup.c b/dedup.c /scm/dedup/file/dedup.c.gph bitreich.org 70 i@@ -8,9 +8,12 @@ Err bitreich.org 70 i #include Err bitreich.org 70 i #include Err bitreich.org 70 i #include "arg.h" Err bitreich.org 70 i+#include "tree.h" Err bitreich.org 70 i Err bitreich.org 70 i #define INDEXF ".index" Err bitreich.org 70 i #define STOREF ".store" Err bitreich.org 70 i+#define CACHEF ".cache" Err bitreich.org 70 i+ Err bitreich.org 70 i #define BLKSIZ 32768 Err bitreich.org 70 i Err bitreich.org 70 i struct enthdr { Err bitreich.org 70 i@@ -32,9 +35,21 @@ struct blk { Err bitreich.org 70 i unsigned char data[BLKSIZ]; Err bitreich.org 70 i } __attribute__((packed)); Err bitreich.org 70 i Err bitreich.org 70 i+struct cent { Err bitreich.org 70 i+ unsigned char md[SHA256_DIGEST_LENGTH]; Err bitreich.org 70 i+ uint64_t blkidx; Err bitreich.org 70 i+} __attribute__((packed)); Err bitreich.org 70 i+ Err bitreich.org 70 i+struct hash_ent { Err bitreich.org 70 i+ struct cent cent; Err bitreich.org 70 i+ RB_ENTRY(hash_ent) e; Err bitreich.org 70 i+}; Err bitreich.org 70 i+ Err bitreich.org 70 i+RB_HEAD(hash_tree, hash_ent) hash_tree_head; Err bitreich.org 70 i struct enthdr enthdr; Err bitreich.org 70 i int ifd; Err bitreich.org 70 i int sfd; Err bitreich.org 70 i+int cfd; Err bitreich.org 70 i int verbose; Err bitreich.org 70 i char *argv0; Err bitreich.org 70 i Err bitreich.org 70 i@@ -90,7 +105,7 @@ xread(int fd, void *buf, size_t nbytes) Err bitreich.org 70 i ssize_t n; Err bitreich.org 70 i Err bitreich.org 70 i n = read(fd, buf, nbytes); Err bitreich.org 70 i- if (n < 0) Err bitreich.org 70 i+ if (n == -1) Err bitreich.org 70 i err(1, "read"); Err bitreich.org 70 i return n; Err bitreich.org 70 i } Err bitreich.org 70 i@@ -101,11 +116,43 @@ xwrite(int fd, const void *buf, size_t nbytes) Err bitreich.org 70 i ssize_t n; Err bitreich.org 70 i Err bitreich.org 70 i n = write(fd, buf, nbytes); Err bitreich.org 70 i- if (n < 0) Err bitreich.org 70 i+ if (n == -1) Err bitreich.org 70 i err(1, "write"); Err bitreich.org 70 i return n; Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i+int Err bitreich.org 70 i+hash_ent_cmp(struct hash_ent *e1, struct hash_ent *e2) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ int r; Err bitreich.org 70 i+ Err bitreich.org 70 i+ r = memcmp(e1->cent.md, e2->cent.md, sizeof(e1->cent.md)); Err bitreich.org 70 i+ if (r > 0) Err bitreich.org 70 i+ return 1; Err bitreich.org 70 i+ else if (r < 0) Err bitreich.org 70 i+ return -1; Err bitreich.org 70 i+ return 0; Err bitreich.org 70 i+} Err bitreich.org 70 i+RB_PROTOTYPE(hash_tree, hash_ent, e, hash_ent_cmp); Err bitreich.org 70 i+RB_GENERATE(hash_tree, hash_ent, e, hash_ent_cmp); Err bitreich.org 70 i+ Err bitreich.org 70 i+struct hash_ent * Err bitreich.org 70 i+hash_ent_add(unsigned char *md, uint64_t blkidx) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ struct hash_ent *hash_ent; Err bitreich.org 70 i+ Err bitreich.org 70 i+ hash_ent = malloc(sizeof(*hash_ent)); Err bitreich.org 70 i+ if (hash_ent == NULL) Err bitreich.org 70 i+ err(1, "malloc"); Err bitreich.org 70 i+ Err bitreich.org 70 i+ memcpy(&hash_ent->cent.md, md, sizeof(hash_ent->cent.md)); Err bitreich.org 70 i+ hash_ent->cent.blkidx = blkidx; Err bitreich.org 70 i+ RB_INSERT(hash_tree, &hash_tree_head, hash_ent); Err bitreich.org 70 i+ lseek(cfd, 0, SEEK_END); Err bitreich.org 70 i+ xwrite(cfd, &hash_ent->cent, sizeof(hash_ent->cent)); Err bitreich.org 70 i+ return hash_ent; Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i void Err bitreich.org 70 i append_ent(struct ent *ent) Err bitreich.org 70 i { Err bitreich.org 70 i@@ -146,6 +193,18 @@ grow_ent(struct ent *ent, uint64_t nblks) Err bitreich.org 70 i return ent; Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i+uint64_t Err bitreich.org 70 i+storefile_nblks(void) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ return lseek(sfd, 0, SEEK_END) / sizeof(struct blk); Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+uint64_t Err bitreich.org 70 i+cachefile_nblks(void) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ return lseek(cfd, 0, SEEK_END) / sizeof(struct cent); Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i void Err bitreich.org 70 i hash_blk(struct blk *blk) Err bitreich.org 70 i { Err bitreich.org 70 i@@ -172,31 +231,19 @@ append_blk(struct blk *blk) Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i int Err bitreich.org 70 i-lookup_blk(struct blk *b1, uint64_t *blkidx) Err bitreich.org 70 i+lookup_blk(struct blk *blk, uint64_t *blkidx) Err bitreich.org 70 i { Err bitreich.org 70 i- uint64_t nblks; Err bitreich.org 70 i- uint64_t i; Err bitreich.org 70 i- Err bitreich.org 70 i- nblks = lseek(sfd, 0, SEEK_END); Err bitreich.org 70 i- nblks /= sizeof(struct blk); Err bitreich.org 70 i- for (i = 0; i < nblks; i++) { Err bitreich.org 70 i- struct blk b2; Err bitreich.org 70 i+ struct hash_ent *hash_ent, key; Err bitreich.org 70 i Err bitreich.org 70 i- read_blk(&b2, i); Err bitreich.org 70 i- if (memcmp(b1->md, b2.md, sizeof(b1->md)) == 0) { Err bitreich.org 70 i- *blkidx = i; Err bitreich.org 70 i- return 0; Err bitreich.org 70 i- } Err bitreich.org 70 i+ memcpy(key.cent.md, blk->md, sizeof(key.cent.md)); Err bitreich.org 70 i+ hash_ent = RB_FIND(hash_tree, &hash_tree_head, &key); Err bitreich.org 70 i+ if (hash_ent != NULL) { Err bitreich.org 70 i+ *blkidx = hash_ent->cent.blkidx; Err bitreich.org 70 i+ return 0; Err bitreich.org 70 i } Err bitreich.org 70 i return -1; Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i-uint64_t Err bitreich.org 70 i-nblks(void) Err bitreich.org 70 i-{ Err bitreich.org 70 i- return lseek(sfd, 0, SEEK_END) / sizeof(struct blk); Err bitreich.org 70 i-} Err bitreich.org 70 i- Err bitreich.org 70 i void Err bitreich.org 70 i dedup(int fd) Err bitreich.org 70 i { Err bitreich.org 70 i@@ -212,8 +259,6 @@ dedup(int fd) Err bitreich.org 70 i Err bitreich.org 70 i blk.sz = n; Err bitreich.org 70 i hash_blk(&blk); Err bitreich.org 70 i- if (verbose) Err bitreich.org 70 i- dump_blk(&blk); Err bitreich.org 70 i Err bitreich.org 70 i /* Rolling hash of input stream */ Err bitreich.org 70 i SHA256_Update(&ctx, blk.data, blk.sz); Err bitreich.org 70 i@@ -221,8 +266,10 @@ dedup(int fd) Err bitreich.org 70 i ent = grow_ent(ent, ent->nblks + 1); Err bitreich.org 70 i Err bitreich.org 70 i if (lookup_blk(&blk, &blkidx) == -1) { Err bitreich.org 70 i- ent->blks[ent->nblks++] = nblks(); Err bitreich.org 70 i+ uint64_t nblks = storefile_nblks(); Err bitreich.org 70 i Err bitreich.org 70 i+ ent->blks[ent->nblks++] = nblks; Err bitreich.org 70 i+ hash_ent_add(blk.md, nblks); Err bitreich.org 70 i append_blk(&blk); Err bitreich.org 70 i } else { Err bitreich.org 70 i ent->blks[ent->nblks++] = blkidx; Err bitreich.org 70 i@@ -249,9 +296,11 @@ extract(unsigned char *id, int fd) Err bitreich.org 70 i { Err bitreich.org 70 i unsigned char md[SHA256_DIGEST_LENGTH]; Err bitreich.org 70 i struct ent *ent; Err bitreich.org 70 i+ uint64_t nblks; Err bitreich.org 70 i uint64_t i; Err bitreich.org 70 i Err bitreich.org 70 i str2bin(id, md); Err bitreich.org 70 i+ nblks = storefile_nblks(); Err bitreich.org 70 i lseek(ifd, sizeof(enthdr), SEEK_SET); Err bitreich.org 70 i for (i = 0; i < enthdr.nents; i++) { Err bitreich.org 70 i ent = alloc_ent(); Err bitreich.org 70 i@@ -267,7 +316,7 @@ extract(unsigned char *id, int fd) Err bitreich.org 70 i for (j = 0; j < ent->nblks; j++) { Err bitreich.org 70 i struct blk blk; Err bitreich.org 70 i Err bitreich.org 70 i- if (ent->blks[j] > nblks()) Err bitreich.org 70 i+ if (ent->blks[j] > nblks) Err bitreich.org 70 i errx(1, "index is corrupted"); Err bitreich.org 70 i read_blk(&blk, ent->blks[j]); Err bitreich.org 70 i xwrite(1, blk.data, blk.sz); Err bitreich.org 70 i@@ -279,6 +328,43 @@ extract(unsigned char *id, int fd) Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i void Err bitreich.org 70 i+rebuild_cache(void) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ uint64_t nblks; Err bitreich.org 70 i+ uint64_t i; Err bitreich.org 70 i+ Err bitreich.org 70 i+ if (verbose) Err bitreich.org 70 i+ fprintf(stderr, "rebuilding cache...\n"); Err bitreich.org 70 i+ nblks = storefile_nblks(); Err bitreich.org 70 i+ lseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i+ for (i = 0; i < nblks; i++) { Err bitreich.org 70 i+ struct blk blk; Err bitreich.org 70 i+ Err bitreich.org 70 i+ read_blk(&blk, i); Err bitreich.org 70 i+ hash_ent_add(blk.md, i); Err bitreich.org 70 i+ } Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+void Err bitreich.org 70 i+init_cache(void) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ uint64_t nblks; Err bitreich.org 70 i+ uint64_t i; Err bitreich.org 70 i+ Err bitreich.org 70 i+ if (verbose) Err bitreich.org 70 i+ fprintf(stderr, "initializing cache...\n"); Err bitreich.org 70 i+ nblks = cachefile_nblks(); Err bitreich.org 70 i+ lseek(cfd, 0, SEEK_SET); Err bitreich.org 70 i+ for (i = 0; i < nblks; i++) { Err bitreich.org 70 i+ struct cent cent; Err bitreich.org 70 i+ Err bitreich.org 70 i+ if (xread(cfd, ¢, sizeof(cent)) == 0) Err bitreich.org 70 i+ errx(1, "unexpected EOF"); Err bitreich.org 70 i+ hash_ent_add(cent.md, cent.blkidx); Err bitreich.org 70 i+ } Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+void Err bitreich.org 70 i init(void) Err bitreich.org 70 i { Err bitreich.org 70 i struct stat sb; Err bitreich.org 70 i@@ -291,10 +377,19 @@ init(void) Err bitreich.org 70 i if (sfd == -1) Err bitreich.org 70 i err(1, "open %s", STOREF); Err bitreich.org 70 i Err bitreich.org 70 i+ cfd = open(CACHEF, O_RDWR | O_CREAT, 0600); Err bitreich.org 70 i+ if (cfd == -1) Err bitreich.org 70 i+ err(1, "open %s", CACHEF); Err bitreich.org 70 i+ Err bitreich.org 70 i if (fstat(ifd, &sb) == -1) Err bitreich.org 70 i- err(1, "stat index"); Err bitreich.org 70 i+ err(1, "stat %s", INDEXF); Err bitreich.org 70 i if (sb.st_size != 0) Err bitreich.org 70 i xread(ifd, &enthdr, sizeof(enthdr)); Err bitreich.org 70 i+ Err bitreich.org 70 i+ if (cachefile_nblks() != storefile_nblks()) Err bitreich.org 70 i+ rebuild_cache(); Err bitreich.org 70 i+ else Err bitreich.org 70 i+ init_cache(); Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i void Err bitreich.org 70 i@@ -302,15 +397,19 @@ term(void) Err bitreich.org 70 i { Err bitreich.org 70 i fsync(ifd); Err bitreich.org 70 i fsync(sfd); Err bitreich.org 70 i+ fsync(cfd); Err bitreich.org 70 i close(ifd); Err bitreich.org 70 i close(sfd); Err bitreich.org 70 i+ close(cfd); Err bitreich.org 70 i } Err bitreich.org 70 i Err bitreich.org 70 i void Err bitreich.org 70 i check(void) Err bitreich.org 70 i { Err bitreich.org 70 i+ uint64_t nblks; Err bitreich.org 70 i uint64_t i, j; Err bitreich.org 70 i Err bitreich.org 70 i+ nblks = storefile_nblks(); Err bitreich.org 70 i lseek(ifd, sizeof(enthdr), SEEK_SET); Err bitreich.org 70 i for (i = 0; i < enthdr.nents; i++) { Err bitreich.org 70 i unsigned char md[SHA256_DIGEST_LENGTH]; Err bitreich.org 70 i@@ -329,7 +428,7 @@ check(void) Err bitreich.org 70 i for (j = 0; j < ent->nblks; j++) { Err bitreich.org 70 i struct blk blk; Err bitreich.org 70 i Err bitreich.org 70 i- if (ent->blks[j] > nblks()) Err bitreich.org 70 i+ if (ent->blks[j] > nblks) Err bitreich.org 70 i errx(1, "index is corrupted"); Err bitreich.org 70 i read_blk(&blk, ent->blks[j]); Err bitreich.org 70 i SHA256_Update(&ctx, blk.data, blk.sz); Err bitreich.org 70 1diff --git a/tree.h b/tree.h /scm/dedup/file/tree.h.gph bitreich.org 70 i@@ -0,0 +1,1016 @@ Err bitreich.org 70 i+/* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */ Err bitreich.org 70 i+/* Err bitreich.org 70 i+ * Copyright 2002 Niels Provos Err bitreich.org 70 i+ * All rights reserved. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * Redistribution and use in source and binary forms, with or without Err bitreich.org 70 i+ * modification, are permitted provided that the following conditions Err bitreich.org 70 i+ * are met: Err bitreich.org 70 i+ * 1. Redistributions of source code must retain the above copyright Err bitreich.org 70 i+ * notice, this list of conditions and the following disclaimer. Err bitreich.org 70 i+ * 2. Redistributions in binary form must reproduce the above copyright Err bitreich.org 70 i+ * notice, this list of conditions and the following disclaimer in the Err bitreich.org 70 i+ * documentation and/or other materials provided with the distribution. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR Err bitreich.org 70 i+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES Err bitreich.org 70 i+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. Err bitreich.org 70 i+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, Err bitreich.org 70 i+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT Err bitreich.org 70 i+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, Err bitreich.org 70 i+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY Err bitreich.org 70 i+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT Err bitreich.org 70 i+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF Err bitreich.org 70 i+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Err bitreich.org 70 i+ */ Err bitreich.org 70 i+ Err bitreich.org 70 i+#ifndef _SYS_TREE_H_ Err bitreich.org 70 i+#define _SYS_TREE_H_ Err bitreich.org 70 i+ Err bitreich.org 70 i+#ifndef NULL Err bitreich.org 70 i+#if !defined(__cplusplus) Err bitreich.org 70 i+#define NULL ((void *)0) Err bitreich.org 70 i+#elif __cplusplus >= 201103L Err bitreich.org 70 i+#define NULL nullptr Err bitreich.org 70 i+#elif defined(__GNUG__) Err bitreich.org 70 i+#define NULL __null Err bitreich.org 70 i+#else Err bitreich.org 70 i+#define NULL 0L Err bitreich.org 70 i+#endif Err bitreich.org 70 i+#endif Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Err bitreich.org 70 i+ * This file defines data structures for different types of trees: Err bitreich.org 70 i+ * splay trees and red-black trees. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * A splay tree is a self-organizing data structure. Every operation Err bitreich.org 70 i+ * on the tree causes a splay to happen. The splay moves the requested Err bitreich.org 70 i+ * node to the root of the tree and partly rebalances it. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * This has the benefit that request locality causes faster lookups as Err bitreich.org 70 i+ * the requested nodes move to the top of the tree. On the other hand, Err bitreich.org 70 i+ * every lookup causes memory writes. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * The Balance Theorem bounds the total access time for m operations Err bitreich.org 70 i+ * and n inserts on an initially empty tree as O((m + n)lg n). The Err bitreich.org 70 i+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n); Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * A red-black tree is a binary search tree with the node color as an Err bitreich.org 70 i+ * extra attribute. It fulfills a set of conditions: Err bitreich.org 70 i+ * - every search path from the root to a leaf consists of the Err bitreich.org 70 i+ * same number of black nodes, Err bitreich.org 70 i+ * - each red node (except for the root) has a black parent, Err bitreich.org 70 i+ * - each leaf node is black. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * Every operation on a red-black tree is bounded as O(lg n). Err bitreich.org 70 i+ * The maximum height of a red-black tree is 2lg (n+1). Err bitreich.org 70 i+ */ Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_HEAD(name, type) \ Err bitreich.org 70 i+struct name { \ Err bitreich.org 70 i+ struct type *sph_root; /* root of the tree */ \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_INITIALIZER(root) \ Err bitreich.org 70 i+ { NULL } Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_INIT(root) do { \ Err bitreich.org 70 i+ (root)->sph_root = NULL; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_ENTRY(type) \ Err bitreich.org 70 i+struct { \ Err bitreich.org 70 i+ struct type *spe_left; /* left element */ \ Err bitreich.org 70 i+ struct type *spe_right; /* right element */ \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left Err bitreich.org 70 i+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right Err bitreich.org 70 i+#define SPLAY_ROOT(head) (head)->sph_root Err bitreich.org 70 i+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) Err bitreich.org 70 i+ Err bitreich.org 70 i+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ Err bitreich.org 70 i+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ Err bitreich.org 70 i+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ Err bitreich.org 70 i+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i+ (head)->sph_root = tmp; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ Err bitreich.org 70 i+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ Err bitreich.org 70 i+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i+ (head)->sph_root = tmp; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_LINKLEFT(head, tmp, field) do { \ Err bitreich.org 70 i+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i+ tmp = (head)->sph_root; \ Err bitreich.org 70 i+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_LINKRIGHT(head, tmp, field) do { \ Err bitreich.org 70 i+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ Err bitreich.org 70 i+ tmp = (head)->sph_root; \ Err bitreich.org 70 i+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ Err bitreich.org 70 i+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ Err bitreich.org 70 i+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Generates prototypes and inline functions */ Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_PROTOTYPE(name, type, field, cmp) \ Err bitreich.org 70 i+void name##_SPLAY(struct name *, struct type *); \ Err bitreich.org 70 i+void name##_SPLAY_MINMAX(struct name *, int); \ Err bitreich.org 70 i+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ Err bitreich.org 70 i+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* Finds the node with the same key as elm */ \ Err bitreich.org 70 i+static __unused __inline struct type * \ Err bitreich.org 70 i+name##_SPLAY_FIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ if (SPLAY_EMPTY(head)) \ Err bitreich.org 70 i+ return(NULL); \ Err bitreich.org 70 i+ name##_SPLAY(head, elm); \ Err bitreich.org 70 i+ if ((cmp)(elm, (head)->sph_root) == 0) \ Err bitreich.org 70 i+ return (head->sph_root); \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+static __unused __inline struct type * \ Err bitreich.org 70 i+name##_SPLAY_NEXT(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ name##_SPLAY(head, elm); \ Err bitreich.org 70 i+ if (SPLAY_RIGHT(elm, field) != NULL) { \ Err bitreich.org 70 i+ elm = SPLAY_RIGHT(elm, field); \ Err bitreich.org 70 i+ while (SPLAY_LEFT(elm, field) != NULL) { \ Err bitreich.org 70 i+ elm = SPLAY_LEFT(elm, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ elm = NULL; \ Err bitreich.org 70 i+ return (elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+static __unused __inline struct type * \ Err bitreich.org 70 i+name##_SPLAY_MIN_MAX(struct name *head, int val) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ name##_SPLAY_MINMAX(head, val); \ Err bitreich.org 70 i+ return (SPLAY_ROOT(head)); \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Main splay operation. Err bitreich.org 70 i+ * Moves node close to the key of elm to top Err bitreich.org 70 i+ */ Err bitreich.org 70 i+#define SPLAY_GENERATE(name, type, field, cmp) \ Err bitreich.org 70 i+struct type * \ Err bitreich.org 70 i+name##_SPLAY_INSERT(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ if (SPLAY_EMPTY(head)) { \ Err bitreich.org 70 i+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ int __comp; \ Err bitreich.org 70 i+ name##_SPLAY(head, elm); \ Err bitreich.org 70 i+ __comp = (cmp)(elm, (head)->sph_root); \ Err bitreich.org 70 i+ if(__comp < 0) { \ Err bitreich.org 70 i+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ Err bitreich.org 70 i+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \ Err bitreich.org 70 i+ SPLAY_LEFT((head)->sph_root, field) = NULL; \ Err bitreich.org 70 i+ } else if (__comp > 0) { \ Err bitreich.org 70 i+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i+ SPLAY_LEFT(elm, field) = (head)->sph_root; \ Err bitreich.org 70 i+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ return ((head)->sph_root); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ (head)->sph_root = (elm); \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+struct type * \ Err bitreich.org 70 i+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *__tmp; \ Err bitreich.org 70 i+ if (SPLAY_EMPTY(head)) \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+ name##_SPLAY(head, elm); \ Err bitreich.org 70 i+ if ((cmp)(elm, (head)->sph_root) == 0) { \ Err bitreich.org 70 i+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ Err bitreich.org 70 i+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ Err bitreich.org 70 i+ name##_SPLAY(head, elm); \ Err bitreich.org 70 i+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (elm); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+void \ Err bitreich.org 70 i+name##_SPLAY(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type __node, *__left, *__right, *__tmp; \ Err bitreich.org 70 i+ int __comp; \ Err bitreich.org 70 i+\ Err bitreich.org 70 i+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ Err bitreich.org 70 i+ __left = __right = &__node; \ Err bitreich.org 70 i+\ Err bitreich.org 70 i+ while ((__comp = (cmp)(elm, (head)->sph_root))) { \ Err bitreich.org 70 i+ if (__comp < 0) { \ Err bitreich.org 70 i+ __tmp = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i+ if (__tmp == NULL) \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ if ((cmp)(elm, __tmp) < 0){ \ Err bitreich.org 70 i+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \ Err bitreich.org 70 i+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_LINKLEFT(head, __right, field); \ Err bitreich.org 70 i+ } else if (__comp > 0) { \ Err bitreich.org 70 i+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i+ if (__tmp == NULL) \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ if ((cmp)(elm, __tmp) > 0){ \ Err bitreich.org 70 i+ SPLAY_ROTATE_LEFT(head, __tmp, field); \ Err bitreich.org 70 i+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_LINKRIGHT(head, __left, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* Splay with either the minimum or the maximum element \ Err bitreich.org 70 i+ * Used to find minimum or maximum element in tree. \ Err bitreich.org 70 i+ */ \ Err bitreich.org 70 i+void name##_SPLAY_MINMAX(struct name *head, int __comp) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type __node, *__left, *__right, *__tmp; \ Err bitreich.org 70 i+\ Err bitreich.org 70 i+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ Err bitreich.org 70 i+ __left = __right = &__node; \ Err bitreich.org 70 i+\ Err bitreich.org 70 i+ while (1) { \ Err bitreich.org 70 i+ if (__comp < 0) { \ Err bitreich.org 70 i+ __tmp = SPLAY_LEFT((head)->sph_root, field); \ Err bitreich.org 70 i+ if (__tmp == NULL) \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ if (__comp < 0){ \ Err bitreich.org 70 i+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \ Err bitreich.org 70 i+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_LINKLEFT(head, __right, field); \ Err bitreich.org 70 i+ } else if (__comp > 0) { \ Err bitreich.org 70 i+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \ Err bitreich.org 70 i+ if (__tmp == NULL) \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ if (__comp > 0) { \ Err bitreich.org 70 i+ SPLAY_ROTATE_LEFT(head, __tmp, field); \ Err bitreich.org 70 i+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_LINKRIGHT(head, __left, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_NEGINF -1 Err bitreich.org 70 i+#define SPLAY_INF 1 Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) Err bitreich.org 70 i+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) Err bitreich.org 70 i+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) Err bitreich.org 70 i+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) Err bitreich.org 70 i+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ Err bitreich.org 70 i+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) Err bitreich.org 70 i+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ Err bitreich.org 70 i+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define SPLAY_FOREACH(x, name, head) \ Err bitreich.org 70 i+ for ((x) = SPLAY_MIN(name, head); \ Err bitreich.org 70 i+ (x) != NULL; \ Err bitreich.org 70 i+ (x) = SPLAY_NEXT(name, head, x)) Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Macros that define a red-black tree */ Err bitreich.org 70 i+#define RB_HEAD(name, type) \ Err bitreich.org 70 i+struct name { \ Err bitreich.org 70 i+ struct type *rbh_root; /* root of the tree */ \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_INITIALIZER(root) \ Err bitreich.org 70 i+ { NULL } Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_INIT(root) do { \ Err bitreich.org 70 i+ (root)->rbh_root = NULL; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_BLACK 0 Err bitreich.org 70 i+#define RB_RED 1 Err bitreich.org 70 i+#define RB_ENTRY(type) \ Err bitreich.org 70 i+struct { \ Err bitreich.org 70 i+ struct type *rbe_left; /* left element */ \ Err bitreich.org 70 i+ struct type *rbe_right; /* right element */ \ Err bitreich.org 70 i+ struct type *rbe_parent; /* parent element */ \ Err bitreich.org 70 i+ int rbe_color; /* node color */ \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_LEFT(elm, field) (elm)->field.rbe_left Err bitreich.org 70 i+#define RB_RIGHT(elm, field) (elm)->field.rbe_right Err bitreich.org 70 i+#define RB_PARENT(elm, field) (elm)->field.rbe_parent Err bitreich.org 70 i+#define RB_COLOR(elm, field) (elm)->field.rbe_color Err bitreich.org 70 i+#define RB_ROOT(head) (head)->rbh_root Err bitreich.org 70 i+#define RB_EMPTY(head) (RB_ROOT(head) == NULL) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_SET(elm, parent, field) do { \ Err bitreich.org 70 i+ RB_PARENT(elm, field) = parent; \ Err bitreich.org 70 i+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ Err bitreich.org 70 i+ RB_COLOR(elm, field) = RB_RED; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_SET_BLACKRED(black, red, field) do { \ Err bitreich.org 70 i+ RB_COLOR(black, field) = RB_BLACK; \ Err bitreich.org 70 i+ RB_COLOR(red, field) = RB_RED; \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#ifndef RB_AUGMENT Err bitreich.org 70 i+#define RB_AUGMENT(x) do {} while (0) Err bitreich.org 70 i+#endif Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ Err bitreich.org 70 i+ (tmp) = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ Err bitreich.org 70 i+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_AUGMENT(elm); \ Err bitreich.org 70 i+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ Err bitreich.org 70 i+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ Err bitreich.org 70 i+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ (head)->rbh_root = (tmp); \ Err bitreich.org 70 i+ RB_LEFT(tmp, field) = (elm); \ Err bitreich.org 70 i+ RB_PARENT(elm, field) = (tmp); \ Err bitreich.org 70 i+ RB_AUGMENT(tmp); \ Err bitreich.org 70 i+ if ((RB_PARENT(tmp, field))) \ Err bitreich.org 70 i+ RB_AUGMENT(RB_PARENT(tmp, field)); \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ Err bitreich.org 70 i+ (tmp) = RB_LEFT(elm, field); \ Err bitreich.org 70 i+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ Err bitreich.org 70 i+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_AUGMENT(elm); \ Err bitreich.org 70 i+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ Err bitreich.org 70 i+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ Err bitreich.org 70 i+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ (head)->rbh_root = (tmp); \ Err bitreich.org 70 i+ RB_RIGHT(tmp, field) = (elm); \ Err bitreich.org 70 i+ RB_PARENT(elm, field) = (tmp); \ Err bitreich.org 70 i+ RB_AUGMENT(tmp); \ Err bitreich.org 70 i+ if ((RB_PARENT(tmp, field))) \ Err bitreich.org 70 i+ RB_AUGMENT(RB_PARENT(tmp, field)); \ Err bitreich.org 70 i+} while (0) Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Generates prototypes and inline functions */ Err bitreich.org 70 i+#define RB_PROTOTYPE(name, type, field, cmp) \ Err bitreich.org 70 i+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) Err bitreich.org 70 i+#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ Err bitreich.org 70 i+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) Err bitreich.org 70 i+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ Err bitreich.org 70 i+attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ Err bitreich.org 70 i+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ Err bitreich.org 70 i+attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_INSERT(struct name *, struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_FIND(struct name *, struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_NFIND(struct name *, struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_NEXT(struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_PREV(struct type *); \ Err bitreich.org 70 i+attr struct type *name##_RB_MINMAX(struct name *, int); \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Main rb operation. Err bitreich.org 70 i+ * Moves node close to the key of elm to top Err bitreich.org 70 i+ */ Err bitreich.org 70 i+#define RB_GENERATE(name, type, field, cmp) \ Err bitreich.org 70 i+ RB_GENERATE_INTERNAL(name, type, field, cmp,) Err bitreich.org 70 i+#define RB_GENERATE_STATIC(name, type, field, cmp) \ Err bitreich.org 70 i+ RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) Err bitreich.org 70 i+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ Err bitreich.org 70 i+attr void \ Err bitreich.org 70 i+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *parent, *gparent, *tmp; \ Err bitreich.org 70 i+ while ((parent = RB_PARENT(elm, field)) && \ Err bitreich.org 70 i+ RB_COLOR(parent, field) == RB_RED) { \ Err bitreich.org 70 i+ gparent = RB_PARENT(parent, field); \ Err bitreich.org 70 i+ if (parent == RB_LEFT(gparent, field)) { \ Err bitreich.org 70 i+ tmp = RB_RIGHT(gparent, field); \ Err bitreich.org 70 i+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_BLACK; \ Err bitreich.org 70 i+ RB_SET_BLACKRED(parent, gparent, field);\ Err bitreich.org 70 i+ elm = gparent; \ Err bitreich.org 70 i+ continue; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ if (RB_RIGHT(parent, field) == elm) { \ Err bitreich.org 70 i+ RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i+ tmp = parent; \ Err bitreich.org 70 i+ parent = elm; \ Err bitreich.org 70 i+ elm = tmp; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_SET_BLACKRED(parent, gparent, field); \ Err bitreich.org 70 i+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ tmp = RB_LEFT(gparent, field); \ Err bitreich.org 70 i+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_BLACK; \ Err bitreich.org 70 i+ RB_SET_BLACKRED(parent, gparent, field);\ Err bitreich.org 70 i+ elm = gparent; \ Err bitreich.org 70 i+ continue; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ if (RB_LEFT(parent, field) == elm) { \ Err bitreich.org 70 i+ RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i+ tmp = parent; \ Err bitreich.org 70 i+ parent = elm; \ Err bitreich.org 70 i+ elm = tmp; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_SET_BLACKRED(parent, gparent, field); \ Err bitreich.org 70 i+ RB_ROTATE_LEFT(head, gparent, tmp, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+attr void \ Err bitreich.org 70 i+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *tmp; \ Err bitreich.org 70 i+ while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ Err bitreich.org 70 i+ elm != RB_ROOT(head)) { \ Err bitreich.org 70 i+ if (RB_LEFT(parent, field) == elm) { \ Err bitreich.org 70 i+ tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i+ if (RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i+ RB_SET_BLACKRED(tmp, parent, field); \ Err bitreich.org 70 i+ RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i+ tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ if ((RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ Err bitreich.org 70 i+ (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i+ elm = parent; \ Err bitreich.org 70 i+ parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ if (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ Err bitreich.org 70 i+ struct type *oleft; \ Err bitreich.org 70 i+ if ((oleft = RB_LEFT(tmp, field)))\ Err bitreich.org 70 i+ RB_COLOR(oleft, field) = RB_BLACK;\ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i+ RB_ROTATE_RIGHT(head, tmp, oleft, field);\ Err bitreich.org 70 i+ tmp = RB_RIGHT(parent, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ Err bitreich.org 70 i+ RB_COLOR(parent, field) = RB_BLACK; \ Err bitreich.org 70 i+ if (RB_RIGHT(tmp, field)) \ Err bitreich.org 70 i+ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ Err bitreich.org 70 i+ RB_ROTATE_LEFT(head, parent, tmp, field);\ Err bitreich.org 70 i+ elm = RB_ROOT(head); \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i+ if (RB_COLOR(tmp, field) == RB_RED) { \ Err bitreich.org 70 i+ RB_SET_BLACKRED(tmp, parent, field); \ Err bitreich.org 70 i+ RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i+ tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ if ((RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ Err bitreich.org 70 i+ (RB_RIGHT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i+ elm = parent; \ Err bitreich.org 70 i+ parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ if (RB_LEFT(tmp, field) == NULL || \ Err bitreich.org 70 i+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ Err bitreich.org 70 i+ struct type *oright; \ Err bitreich.org 70 i+ if ((oright = RB_RIGHT(tmp, field)))\ Err bitreich.org 70 i+ RB_COLOR(oright, field) = RB_BLACK;\ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_RED; \ Err bitreich.org 70 i+ RB_ROTATE_LEFT(head, tmp, oright, field);\ Err bitreich.org 70 i+ tmp = RB_LEFT(parent, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ Err bitreich.org 70 i+ RB_COLOR(parent, field) = RB_BLACK; \ Err bitreich.org 70 i+ if (RB_LEFT(tmp, field)) \ Err bitreich.org 70 i+ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ Err bitreich.org 70 i+ RB_ROTATE_RIGHT(head, parent, tmp, field);\ Err bitreich.org 70 i+ elm = RB_ROOT(head); \ Err bitreich.org 70 i+ break; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ if (elm) \ Err bitreich.org 70 i+ RB_COLOR(elm, field) = RB_BLACK; \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_REMOVE(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *child, *parent, *old = elm; \ Err bitreich.org 70 i+ int color; \ Err bitreich.org 70 i+ if (RB_LEFT(elm, field) == NULL) \ Err bitreich.org 70 i+ child = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ else if (RB_RIGHT(elm, field) == NULL) \ Err bitreich.org 70 i+ child = RB_LEFT(elm, field); \ Err bitreich.org 70 i+ else { \ Err bitreich.org 70 i+ struct type *left; \ Err bitreich.org 70 i+ elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ while ((left = RB_LEFT(elm, field))) \ Err bitreich.org 70 i+ elm = left; \ Err bitreich.org 70 i+ child = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ color = RB_COLOR(elm, field); \ Err bitreich.org 70 i+ if (child) \ Err bitreich.org 70 i+ RB_PARENT(child, field) = parent; \ Err bitreich.org 70 i+ if (parent) { \ Err bitreich.org 70 i+ if (RB_LEFT(parent, field) == elm) \ Err bitreich.org 70 i+ RB_LEFT(parent, field) = child; \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(parent, field) = child; \ Err bitreich.org 70 i+ RB_AUGMENT(parent); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ RB_ROOT(head) = child; \ Err bitreich.org 70 i+ if (RB_PARENT(elm, field) == old) \ Err bitreich.org 70 i+ parent = elm; \ Err bitreich.org 70 i+ (elm)->field = (old)->field; \ Err bitreich.org 70 i+ if (RB_PARENT(old, field)) { \ Err bitreich.org 70 i+ if (RB_LEFT(RB_PARENT(old, field), field) == old)\ Err bitreich.org 70 i+ RB_LEFT(RB_PARENT(old, field), field) = elm;\ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(RB_PARENT(old, field), field) = elm;\ Err bitreich.org 70 i+ RB_AUGMENT(RB_PARENT(old, field)); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ RB_ROOT(head) = elm; \ Err bitreich.org 70 i+ RB_PARENT(RB_LEFT(old, field), field) = elm; \ Err bitreich.org 70 i+ if (RB_RIGHT(old, field)) \ Err bitreich.org 70 i+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \ Err bitreich.org 70 i+ if (parent) { \ Err bitreich.org 70 i+ left = parent; \ Err bitreich.org 70 i+ do { \ Err bitreich.org 70 i+ RB_AUGMENT(left); \ Err bitreich.org 70 i+ } while ((left = RB_PARENT(left, field))); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ goto color; \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ parent = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ color = RB_COLOR(elm, field); \ Err bitreich.org 70 i+ if (child) \ Err bitreich.org 70 i+ RB_PARENT(child, field) = parent; \ Err bitreich.org 70 i+ if (parent) { \ Err bitreich.org 70 i+ if (RB_LEFT(parent, field) == elm) \ Err bitreich.org 70 i+ RB_LEFT(parent, field) = child; \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(parent, field) = child; \ Err bitreich.org 70 i+ RB_AUGMENT(parent); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ RB_ROOT(head) = child; \ Err bitreich.org 70 i+color: \ Err bitreich.org 70 i+ if (color == RB_BLACK) \ Err bitreich.org 70 i+ name##_RB_REMOVE_COLOR(head, parent, child); \ Err bitreich.org 70 i+ return (old); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* Inserts a node into the RB tree */ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_INSERT(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *tmp; \ Err bitreich.org 70 i+ struct type *parent = NULL; \ Err bitreich.org 70 i+ int comp = 0; \ Err bitreich.org 70 i+ tmp = RB_ROOT(head); \ Err bitreich.org 70 i+ while (tmp) { \ Err bitreich.org 70 i+ parent = tmp; \ Err bitreich.org 70 i+ comp = (cmp)(elm, parent); \ Err bitreich.org 70 i+ if (comp < 0) \ Err bitreich.org 70 i+ tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i+ else if (comp > 0) \ Err bitreich.org 70 i+ tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ return (tmp); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ RB_SET(elm, parent, field); \ Err bitreich.org 70 i+ if (parent != NULL) { \ Err bitreich.org 70 i+ if (comp < 0) \ Err bitreich.org 70 i+ RB_LEFT(parent, field) = elm; \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ RB_RIGHT(parent, field) = elm; \ Err bitreich.org 70 i+ RB_AUGMENT(parent); \ Err bitreich.org 70 i+ } else \ Err bitreich.org 70 i+ RB_ROOT(head) = elm; \ Err bitreich.org 70 i+ name##_RB_INSERT_COLOR(head, elm); \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* Finds the node with the same key as elm */ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_FIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i+ int comp; \ Err bitreich.org 70 i+ while (tmp) { \ Err bitreich.org 70 i+ comp = cmp(elm, tmp); \ Err bitreich.org 70 i+ if (comp < 0) \ Err bitreich.org 70 i+ tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i+ else if (comp > 0) \ Err bitreich.org 70 i+ tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ return (tmp); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (NULL); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* Finds the first node greater than or equal to the search key */ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_NFIND(struct name *head, struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i+ struct type *res = NULL; \ Err bitreich.org 70 i+ int comp; \ Err bitreich.org 70 i+ while (tmp) { \ Err bitreich.org 70 i+ comp = cmp(elm, tmp); \ Err bitreich.org 70 i+ if (comp < 0) { \ Err bitreich.org 70 i+ res = tmp; \ Err bitreich.org 70 i+ tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ else if (comp > 0) \ Err bitreich.org 70 i+ tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ return (tmp); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (res); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* ARGSUSED */ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_NEXT(struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ if (RB_RIGHT(elm, field)) { \ Err bitreich.org 70 i+ elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ while (RB_LEFT(elm, field)) \ Err bitreich.org 70 i+ elm = RB_LEFT(elm, field); \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ if (RB_PARENT(elm, field) && \ Err bitreich.org 70 i+ (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ else { \ Err bitreich.org 70 i+ while (RB_PARENT(elm, field) && \ Err bitreich.org 70 i+ (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+/* ARGSUSED */ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_PREV(struct type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ if (RB_LEFT(elm, field)) { \ Err bitreich.org 70 i+ elm = RB_LEFT(elm, field); \ Err bitreich.org 70 i+ while (RB_RIGHT(elm, field)) \ Err bitreich.org 70 i+ elm = RB_RIGHT(elm, field); \ Err bitreich.org 70 i+ } else { \ Err bitreich.org 70 i+ if (RB_PARENT(elm, field) && \ Err bitreich.org 70 i+ (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ else { \ Err bitreich.org 70 i+ while (RB_PARENT(elm, field) && \ Err bitreich.org 70 i+ (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ elm = RB_PARENT(elm, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+attr struct type * \ Err bitreich.org 70 i+name##_RB_MINMAX(struct name *head, int val) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct type *tmp = RB_ROOT(head); \ Err bitreich.org 70 i+ struct type *parent = NULL; \ Err bitreich.org 70 i+ while (tmp) { \ Err bitreich.org 70 i+ parent = tmp; \ Err bitreich.org 70 i+ if (val < 0) \ Err bitreich.org 70 i+ tmp = RB_LEFT(tmp, field); \ Err bitreich.org 70 i+ else \ Err bitreich.org 70 i+ tmp = RB_RIGHT(tmp, field); \ Err bitreich.org 70 i+ } \ Err bitreich.org 70 i+ return (parent); \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_NEGINF -1 Err bitreich.org 70 i+#define RB_INF 1 Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) Err bitreich.org 70 i+#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) Err bitreich.org 70 i+#define RB_FIND(name, x, y) name##_RB_FIND(x, y) Err bitreich.org 70 i+#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) Err bitreich.org 70 i+#define RB_NEXT(name, x, y) name##_RB_NEXT(y) Err bitreich.org 70 i+#define RB_PREV(name, x, y) name##_RB_PREV(y) Err bitreich.org 70 i+#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) Err bitreich.org 70 i+#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_FOREACH(x, name, head) \ Err bitreich.org 70 i+ for ((x) = RB_MIN(name, head); \ Err bitreich.org 70 i+ (x) != NULL; \ Err bitreich.org 70 i+ (x) = name##_RB_NEXT(x)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_FOREACH_SAFE(x, name, head, y) \ Err bitreich.org 70 i+ for ((x) = RB_MIN(name, head); \ Err bitreich.org 70 i+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ Err bitreich.org 70 i+ (x) = (y)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_FOREACH_REVERSE(x, name, head) \ Err bitreich.org 70 i+ for ((x) = RB_MAX(name, head); \ Err bitreich.org 70 i+ (x) != NULL; \ Err bitreich.org 70 i+ (x) = name##_RB_PREV(x)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ Err bitreich.org 70 i+ for ((x) = RB_MAX(name, head); \ Err bitreich.org 70 i+ ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ Err bitreich.org 70 i+ (x) = (y)) Err bitreich.org 70 i+ Err bitreich.org 70 i+ Err bitreich.org 70 i+/* Err bitreich.org 70 i+ * Copyright (c) 2016 David Gwynne Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * Permission to use, copy, modify, and distribute this software for any Err bitreich.org 70 i+ * purpose with or without fee is hereby granted, provided that the above Err bitreich.org 70 i+ * copyright notice and this permission notice appear in all copies. Err bitreich.org 70 i+ * Err bitreich.org 70 i+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES Err bitreich.org 70 i+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF Err bitreich.org 70 i+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR Err bitreich.org 70 i+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES Err bitreich.org 70 i+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN Err bitreich.org 70 i+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF Err bitreich.org 70 i+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. Err bitreich.org 70 i+ */ Err bitreich.org 70 i+ Err bitreich.org 70 i+struct rb_type { Err bitreich.org 70 i+ int (*t_compare)(const void *, const void *); Err bitreich.org 70 i+ void (*t_augment)(void *); Err bitreich.org 70 i+ unsigned int t_offset; /* offset of rb_entry in type */ Err bitreich.org 70 i+}; Err bitreich.org 70 i+ Err bitreich.org 70 i+struct rb_tree { Err bitreich.org 70 i+ struct rb_entry *rbt_root; Err bitreich.org 70 i+}; Err bitreich.org 70 i+ Err bitreich.org 70 i+struct rb_entry { Err bitreich.org 70 i+ struct rb_entry *rbt_parent; Err bitreich.org 70 i+ struct rb_entry *rbt_left; Err bitreich.org 70 i+ struct rb_entry *rbt_right; Err bitreich.org 70 i+ unsigned int rbt_color; Err bitreich.org 70 i+}; Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_HEAD(_name, _type) \ Err bitreich.org 70 i+struct _name { \ Err bitreich.org 70 i+ struct rb_tree rbh_root; \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_ENTRY(_type) struct rb_entry Err bitreich.org 70 i+ Err bitreich.org 70 i+static inline void Err bitreich.org 70 i+_rb_init(struct rb_tree *rbt) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ rbt->rbt_root = NULL; Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+static inline int Err bitreich.org 70 i+_rb_empty(struct rb_tree *rbt) Err bitreich.org 70 i+{ Err bitreich.org 70 i+ return (rbt->rbt_root == NULL); Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); Err bitreich.org 70 i+void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); Err bitreich.org 70 i+void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); Err bitreich.org 70 i+void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); Err bitreich.org 70 i+void *_rb_root(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i+void *_rb_min(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i+void *_rb_max(const struct rb_type *, struct rb_tree *); Err bitreich.org 70 i+void *_rb_next(const struct rb_type *, void *); Err bitreich.org 70 i+void *_rb_prev(const struct rb_type *, void *); Err bitreich.org 70 i+void *_rb_left(const struct rb_type *, void *); Err bitreich.org 70 i+void *_rb_right(const struct rb_type *, void *); Err bitreich.org 70 i+void *_rb_parent(const struct rb_type *, void *); Err bitreich.org 70 i+void _rb_set_left(const struct rb_type *, void *, void *); Err bitreich.org 70 i+void _rb_set_right(const struct rb_type *, void *, void *); Err bitreich.org 70 i+void _rb_set_parent(const struct rb_type *, void *, void *); Err bitreich.org 70 i+void _rb_poison(const struct rb_type *, void *, unsigned long); Err bitreich.org 70 i+int _rb_check(const struct rb_type *, void *, unsigned long); Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_INITIALIZER(_head) { { NULL } } Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ Err bitreich.org 70 i+extern const struct rb_type *const _name##_RBT_TYPE; \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline void \ Err bitreich.org 70 i+_name##_RBT_INIT(struct _name *head) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ _rb_init(&head->rbh_root); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_FIND(struct _name *head, const struct _type *key) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_ROOT(struct _name *head) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline int \ Err bitreich.org 70 i+_name##_RBT_EMPTY(struct _name *head) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_empty(&head->rbh_root); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_MIN(struct _name *head) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_MAX(struct _name *head) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_NEXT(struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_next(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_PREV(struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_prev(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_LEFT(struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_left(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_RIGHT(struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_right(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline struct _type * \ Err bitreich.org 70 i+_name##_RBT_PARENT(struct _type *elm) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_parent(_name##_RBT_TYPE, elm); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline void \ Err bitreich.org 70 i+_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_set_left(_name##_RBT_TYPE, elm, left); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline void \ Err bitreich.org 70 i+_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_set_right(_name##_RBT_TYPE, elm, right); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline void \ Err bitreich.org 70 i+_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline void \ Err bitreich.org 70 i+_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_poison(_name##_RBT_TYPE, elm, poison); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+ \ Err bitreich.org 70 i+__unused static inline int \ Err bitreich.org 70 i+_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ return _rb_check(_name##_RBT_TYPE, elm, poison); \ Err bitreich.org 70 i+} Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ Err bitreich.org 70 i+static int \ Err bitreich.org 70 i+_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ const struct _type *l = lptr, *r = rptr; \ Err bitreich.org 70 i+ return _cmp(l, r); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+static const struct rb_type _name##_RBT_INFO = { \ Err bitreich.org 70 i+ _name##_RBT_COMPARE, \ Err bitreich.org 70 i+ _aug, \ Err bitreich.org 70 i+ offsetof(struct _type, _field), \ Err bitreich.org 70 i+}; \ Err bitreich.org 70 i+const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ Err bitreich.org 70 i+static void \ Err bitreich.org 70 i+_name##_RBT_AUGMENT(void *ptr) \ Err bitreich.org 70 i+{ \ Err bitreich.org 70 i+ struct _type *p = ptr; \ Err bitreich.org 70 i+ return _aug(p); \ Err bitreich.org 70 i+} \ Err bitreich.org 70 i+RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_GENERATE(_name, _type, _field, _cmp) \ Err bitreich.org 70 i+ RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) Err bitreich.org 70 i+#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) Err bitreich.org 70 i+#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) Err bitreich.org 70 i+#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) Err bitreich.org 70 i+#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) Err bitreich.org 70 i+#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) Err bitreich.org 70 i+#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) Err bitreich.org 70 i+#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) Err bitreich.org 70 i+#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) Err bitreich.org 70 i+#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) Err bitreich.org 70 i+#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) Err bitreich.org 70 i+#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) Err bitreich.org 70 i+#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) Err bitreich.org 70 i+#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) Err bitreich.org 70 i+#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) Err bitreich.org 70 i+#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) Err bitreich.org 70 i+#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) Err bitreich.org 70 i+#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) Err bitreich.org 70 i+#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_FOREACH(_e, _name, _head) \ Err bitreich.org 70 i+ for ((_e) = RBT_MIN(_name, (_head)); \ Err bitreich.org 70 i+ (_e) != NULL; \ Err bitreich.org 70 i+ (_e) = RBT_NEXT(_name, (_e))) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ Err bitreich.org 70 i+ for ((_e) = RBT_MIN(_name, (_head)); \ Err bitreich.org 70 i+ (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ Err bitreich.org 70 i+ (_e) = (_n)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_FOREACH_REVERSE(_e, _name, _head) \ Err bitreich.org 70 i+ for ((_e) = RBT_MAX(_name, (_head)); \ Err bitreich.org 70 i+ (_e) != NULL; \ Err bitreich.org 70 i+ (_e) = RBT_PREV(_name, (_e))) Err bitreich.org 70 i+ Err bitreich.org 70 i+#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ Err bitreich.org 70 i+ for ((_e) = RBT_MAX(_name, (_head)); \ Err bitreich.org 70 i+ (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ Err bitreich.org 70 i+ (_e) = (_n)) Err bitreich.org 70 i+ Err bitreich.org 70 i+#endif /* _SYS_TREE_H_ */ Err bitreich.org 70 .