diff options
| -rw-r--r-- | lib/imsg-buffer.c | 105 | ||||
| -rw-r--r-- | lib/imsg.c | 117 | ||||
| -rw-r--r-- | lib/imsg.h | 110 | ||||
| -rw-r--r-- | lib/openbsd-tree.c | 146 | ||||
| -rw-r--r-- | lib/openbsd-tree.h | 809 |
5 files changed, 662 insertions, 625 deletions
diff --git a/lib/imsg-buffer.c b/lib/imsg-buffer.c index 4068e31c51..a486fc17c1 100644 --- a/lib/imsg-buffer.c +++ b/lib/imsg-buffer.c @@ -21,13 +21,14 @@ #include "openbsd-queue.h" #include "imsg.h" -int ibuf_realloc(struct ibuf *, size_t); -void ibuf_enqueue(struct msgbuf *, struct ibuf *); -void ibuf_dequeue(struct msgbuf *, struct ibuf *); +int ibuf_realloc(struct ibuf *, size_t); +void ibuf_enqueue(struct msgbuf *, struct ibuf *); +void ibuf_dequeue(struct msgbuf *, struct ibuf *); -struct ibuf *ibuf_open(size_t len) +struct ibuf * +ibuf_open(size_t len) { - struct ibuf *buf; + struct ibuf *buf; if ((buf = calloc(1, sizeof(struct ibuf))) == NULL) return (NULL); @@ -41,9 +42,10 @@ struct ibuf *ibuf_open(size_t len) return (buf); } -struct ibuf *ibuf_dynamic(size_t len, size_t max) +struct ibuf * +ibuf_dynamic(size_t len, size_t max) { - struct ibuf *buf; + struct ibuf *buf; if (max < len) return (NULL); @@ -57,9 +59,10 @@ struct ibuf *ibuf_dynamic(size_t len, size_t max) return (buf); } -int ibuf_realloc(struct ibuf *buf, size_t len) +int +ibuf_realloc(struct ibuf *buf, size_t len) { - u_char *b; + u_char *b; /* on static buffers max is eq size and so the following fails */ if (buf->wpos + len > buf->max) { @@ -76,7 +79,8 @@ int ibuf_realloc(struct ibuf *buf, size_t len) return (0); } -int ibuf_add(struct ibuf *buf, const void *data, size_t len) +int +ibuf_add(struct ibuf *buf, const void *data, size_t len) { if (buf->wpos + len > buf->size) if (ibuf_realloc(buf, len) == -1) @@ -87,9 +91,10 @@ int ibuf_add(struct ibuf *buf, const void *data, size_t len) return (0); } -void *ibuf_reserve(struct ibuf *buf, size_t len) +void * +ibuf_reserve(struct ibuf *buf, size_t len) { - void *b; + void *b; if (buf->wpos + len > buf->size) if (ibuf_realloc(buf, len) == -1) @@ -100,7 +105,8 @@ void *ibuf_reserve(struct ibuf *buf, size_t len) return (b); } -void *ibuf_seek(struct ibuf *buf, size_t pos, size_t len) +void * +ibuf_seek(struct ibuf *buf, size_t pos, size_t len) { /* only allowed to seek in already written parts */ if (pos + len > buf->wpos) @@ -109,31 +115,34 @@ void *ibuf_seek(struct ibuf *buf, size_t pos, size_t len) return (buf->buf + pos); } -size_t ibuf_size(struct ibuf *buf) +size_t +ibuf_size(struct ibuf *buf) { return (buf->wpos); } -size_t ibuf_left(struct ibuf *buf) +size_t +ibuf_left(struct ibuf *buf) { return (buf->max - buf->wpos); } -void ibuf_close(struct msgbuf *msgbuf, struct ibuf *buf) +void +ibuf_close(struct msgbuf *msgbuf, struct ibuf *buf) { ibuf_enqueue(msgbuf, buf); } -int ibuf_write(struct msgbuf *msgbuf) +int +ibuf_write(struct msgbuf *msgbuf) { - struct iovec iov[IOV_MAX]; - struct ibuf *buf; - unsigned int i = 0; - ssize_t n; + struct iovec iov[IOV_MAX]; + struct ibuf *buf; + unsigned int i = 0; + ssize_t n; memset(&iov, 0, sizeof(iov)); - TAILQ_FOREACH(buf, &msgbuf->bufs, entry) - { + TAILQ_FOREACH(buf, &msgbuf->bufs, entry) { if (i >= IOV_MAX) break; iov[i].iov_base = buf->buf + buf->rpos; @@ -150,7 +159,7 @@ again: return (-1); } - if (n == 0) { /* connection closed */ + if (n == 0) { /* connection closed */ errno = 0; return (0); } @@ -160,7 +169,8 @@ again: return (1); } -void ibuf_free(struct ibuf *buf) +void +ibuf_free(struct ibuf *buf) { if (buf == NULL) return; @@ -168,19 +178,21 @@ void ibuf_free(struct ibuf *buf) free(buf); } -void msgbuf_init(struct msgbuf *msgbuf) +void +msgbuf_init(struct msgbuf *msgbuf) { msgbuf->queued = 0; msgbuf->fd = -1; TAILQ_INIT(&msgbuf->bufs); } -void msgbuf_drain(struct msgbuf *msgbuf, size_t n) +void +msgbuf_drain(struct msgbuf *msgbuf, size_t n) { - struct ibuf *buf, *next; + struct ibuf *buf, *next; for (buf = TAILQ_FIRST(&msgbuf->bufs); buf != NULL && n > 0; - buf = next) { + buf = next) { next = TAILQ_NEXT(buf, entry); if (buf->rpos + n >= buf->wpos) { n -= buf->wpos - buf->rpos; @@ -192,32 +204,33 @@ void msgbuf_drain(struct msgbuf *msgbuf, size_t n) } } -void msgbuf_clear(struct msgbuf *msgbuf) +void +msgbuf_clear(struct msgbuf *msgbuf) { - struct ibuf *buf; + struct ibuf *buf; while ((buf = TAILQ_FIRST(&msgbuf->bufs)) != NULL) ibuf_dequeue(msgbuf, buf); } -int msgbuf_write(struct msgbuf *msgbuf) +int +msgbuf_write(struct msgbuf *msgbuf) { - struct iovec iov[IOV_MAX]; - struct ibuf *buf; - unsigned int i = 0; - ssize_t n; - struct msghdr msg; - struct cmsghdr *cmsg; + struct iovec iov[IOV_MAX]; + struct ibuf *buf; + unsigned int i = 0; + ssize_t n; + struct msghdr msg; + struct cmsghdr *cmsg; union { - struct cmsghdr hdr; - char buf[CMSG_SPACE(sizeof(int))]; + struct cmsghdr hdr; + char buf[CMSG_SPACE(sizeof(int))]; } cmsgbuf; memset(&iov, 0, sizeof(iov)); memset(&msg, 0, sizeof(msg)); memset(&cmsgbuf, 0, sizeof(cmsgbuf)); - TAILQ_FOREACH(buf, &msgbuf->bufs, entry) - { + TAILQ_FOREACH(buf, &msgbuf->bufs, entry) { if (i >= IOV_MAX) break; iov[i].iov_base = buf->buf + buf->rpos; @@ -249,7 +262,7 @@ again: return (-1); } - if (n == 0) { /* connection closed */ + if (n == 0) { /* connection closed */ errno = 0; return (0); } @@ -268,13 +281,15 @@ again: return (1); } -void ibuf_enqueue(struct msgbuf *msgbuf, struct ibuf *buf) +void +ibuf_enqueue(struct msgbuf *msgbuf, struct ibuf *buf) { TAILQ_INSERT_TAIL(&msgbuf->bufs, buf, entry); msgbuf->queued++; } -void ibuf_dequeue(struct msgbuf *msgbuf, struct ibuf *buf) +void +ibuf_dequeue(struct msgbuf *msgbuf, struct ibuf *buf) { TAILQ_REMOVE(&msgbuf->bufs, buf, entry); diff --git a/lib/imsg.c b/lib/imsg.c index 10650f648a..fc62c13734 100644 --- a/lib/imsg.c +++ b/lib/imsg.c @@ -21,21 +21,22 @@ #include "openbsd-queue.h" #include "imsg.h" -int imsg_fd_overhead = 0; +int imsg_fd_overhead = 0; -int imsg_get_fd(struct imsgbuf *); +int imsg_get_fd(struct imsgbuf *); #ifndef __OpenBSD__ /* * The original code calls getdtablecount() which is OpenBSD specific. Use * available_fds() from OpenSMTPD instead. */ -static int available_fds(unsigned int n) +static int +available_fds(unsigned int n) { - unsigned int i; - int ret, fds[256]; + unsigned int i; + int ret, fds[256]; - if (n > (sizeof(fds) / sizeof(fds[0]))) + if (n > (sizeof(fds)/sizeof(fds[0]))) return (1); ret = 0; @@ -58,7 +59,8 @@ static int available_fds(unsigned int n) } #endif -void imsg_init(struct imsgbuf *ibuf, int fd) +void +imsg_init(struct imsgbuf *ibuf, int fd) { msgbuf_init(&ibuf->w); memset(&ibuf->r, 0, sizeof(ibuf->r)); @@ -68,18 +70,19 @@ void imsg_init(struct imsgbuf *ibuf, int fd) TAILQ_INIT(&ibuf->fds); } -ssize_t imsg_read(struct imsgbuf *ibuf) +ssize_t +imsg_read(struct imsgbuf *ibuf) { - struct msghdr msg; - struct cmsghdr *cmsg; + struct msghdr msg; + struct cmsghdr *cmsg; union { struct cmsghdr hdr; - char buf[CMSG_SPACE(sizeof(int) * 1)]; + char buf[CMSG_SPACE(sizeof(int) * 1)]; } cmsgbuf; - struct iovec iov; - ssize_t n = -1; - int fd; - struct imsg_fd *ifd; + struct iovec iov; + ssize_t n = -1; + int fd; + struct imsg_fd *ifd; memset(&msg, 0, sizeof(msg)); memset(&cmsgbuf, 0, sizeof(cmsgbuf)); @@ -96,14 +99,12 @@ ssize_t imsg_read(struct imsgbuf *ibuf) again: #ifdef __OpenBSD__ - if (getdtablecount() + imsg_fd_overhead - + (int)((CMSG_SPACE(sizeof(int)) - CMSG_SPACE(0)) - / sizeof(int)) + if (getdtablecount() + imsg_fd_overhead + + (int)((CMSG_SPACE(sizeof(int))-CMSG_SPACE(0))/sizeof(int)) >= getdtablesize()) { #else - if (available_fds(imsg_fd_overhead - + (CMSG_SPACE(sizeof(int)) - CMSG_SPACE(0)) - / sizeof(int))) { + if (available_fds(imsg_fd_overhead + + (CMSG_SPACE(sizeof(int))-CMSG_SPACE(0))/sizeof(int))) { #endif errno = EAGAIN; free(ifd); @@ -119,9 +120,9 @@ again: ibuf->r.wpos += n; for (cmsg = CMSG_FIRSTHDR(&msg); cmsg != NULL; - cmsg = CMSG_NXTHDR(&msg, cmsg)) { - if (cmsg->cmsg_level == SOL_SOCKET - && cmsg->cmsg_type == SCM_RIGHTS) { + cmsg = CMSG_NXTHDR(&msg, cmsg)) { + if (cmsg->cmsg_level == SOL_SOCKET && + cmsg->cmsg_type == SCM_RIGHTS) { int i; int j; @@ -130,15 +131,14 @@ again: * padding rules, our control buffer might contain * more than one fd, and we must close them. */ - j = ((char *)cmsg + cmsg->cmsg_len - - (char *)CMSG_DATA(cmsg)) - / sizeof(int); + j = ((char *)cmsg + cmsg->cmsg_len - + (char *)CMSG_DATA(cmsg)) / sizeof(int); for (i = 0; i < j; i++) { fd = ((int *)CMSG_DATA(cmsg))[i]; if (ifd != NULL) { ifd->fd = fd; TAILQ_INSERT_TAIL(&ibuf->fds, ifd, - entry); + entry); ifd = NULL; } else close(fd); @@ -152,9 +152,10 @@ fail: return (n); } -ssize_t imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) +ssize_t +imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) { - size_t av, left, datalen; + size_t av, left, datalen; av = ibuf->r.wpos; @@ -162,7 +163,8 @@ ssize_t imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) return (0); memcpy(&imsg->hdr, ibuf->r.buf, sizeof(imsg->hdr)); - if (imsg->hdr.len < IMSG_HEADER_SIZE || imsg->hdr.len > MAX_IMSGSIZE) { + if (imsg->hdr.len < IMSG_HEADER_SIZE || + imsg->hdr.len > MAX_IMSGSIZE) { errno = ERANGE; return (-1); } @@ -181,7 +183,7 @@ ssize_t imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) imsg->fd = -1; if (imsg->data) - memcpy(imsg->data, ibuf->r.rptr, datalen); + memcpy(imsg->data, ibuf->r.rptr, datalen); if (imsg->hdr.len < av) { left = av - imsg->hdr.len; @@ -193,10 +195,11 @@ ssize_t imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) return (datalen + IMSG_HEADER_SIZE); } -int imsg_compose(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, - pid_t pid, int fd, const void *data, u_int16_t datalen) +int +imsg_compose(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, + pid_t pid, int fd, const void *data, u_int16_t datalen) { - struct ibuf *wbuf; + struct ibuf *wbuf; if ((wbuf = imsg_create(ibuf, type, peerid, pid, datalen)) == NULL) return (-1); @@ -211,11 +214,12 @@ int imsg_compose(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, return (1); } -int imsg_composev(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, - pid_t pid, int fd, const struct iovec *iov, int iovcnt) +int +imsg_composev(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, + pid_t pid, int fd, const struct iovec *iov, int iovcnt) { - struct ibuf *wbuf; - int i, datalen = 0; + struct ibuf *wbuf; + int i, datalen = 0; for (i = 0; i < iovcnt; i++) datalen += iov[i].iov_len; @@ -235,11 +239,12 @@ int imsg_composev(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, } /* ARGSUSED */ -struct ibuf *imsg_create(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, - pid_t pid, u_int16_t datalen) +struct ibuf * +imsg_create(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, + pid_t pid, u_int16_t datalen) { - struct ibuf *wbuf; - struct imsg_hdr hdr; + struct ibuf *wbuf; + struct imsg_hdr hdr; datalen += IMSG_HEADER_SIZE; if (datalen > MAX_IMSGSIZE) { @@ -261,7 +266,8 @@ struct ibuf *imsg_create(struct imsgbuf *ibuf, u_int32_t type, u_int32_t peerid, return (wbuf); } -int imsg_add(struct ibuf *msg, const void *data, u_int16_t datalen) +int +imsg_add(struct ibuf *msg, const void *data, u_int16_t datalen) { if (datalen) if (ibuf_add(msg, data, datalen) == -1) { @@ -271,9 +277,10 @@ int imsg_add(struct ibuf *msg, const void *data, u_int16_t datalen) return (datalen); } -void imsg_close(struct imsgbuf *ibuf, struct ibuf *msg) +void +imsg_close(struct imsgbuf *ibuf, struct ibuf *msg) { - struct imsg_hdr *hdr; + struct imsg_hdr *hdr; hdr = (struct imsg_hdr *)msg->buf; @@ -286,15 +293,17 @@ void imsg_close(struct imsgbuf *ibuf, struct ibuf *msg) ibuf_close(&ibuf->w, msg); } -void imsg_free(struct imsg *imsg) +void +imsg_free(struct imsg *imsg) { free(imsg->data); } -int imsg_get_fd(struct imsgbuf *ibuf) +int +imsg_get_fd(struct imsgbuf *ibuf) { - int fd; - struct imsg_fd *ifd; + int fd; + struct imsg_fd *ifd; if ((ifd = TAILQ_FIRST(&ibuf->fds)) == NULL) return (-1); @@ -306,7 +315,8 @@ int imsg_get_fd(struct imsgbuf *ibuf) return (fd); } -int imsg_flush(struct imsgbuf *ibuf) +int +imsg_flush(struct imsgbuf *ibuf) { while (ibuf->w.queued) if (msgbuf_write(&ibuf->w) <= 0) @@ -314,9 +324,10 @@ int imsg_flush(struct imsgbuf *ibuf) return (0); } -void imsg_clear(struct imsgbuf *ibuf) +void +imsg_clear(struct imsgbuf *ibuf) { - int fd; + int fd; msgbuf_clear(&ibuf->w); while ((fd = imsg_get_fd(ibuf)) != -1) diff --git a/lib/imsg.h b/lib/imsg.h index ddaf71344e..d053d01956 100644 --- a/lib/imsg.h +++ b/lib/imsg.h @@ -26,87 +26,87 @@ #define MAX_IMSGSIZE 16384 struct ibuf { - TAILQ_ENTRY(ibuf) entry; - u_char *buf; - size_t size; - size_t max; - size_t wpos; - size_t rpos; - int fd; + TAILQ_ENTRY(ibuf) entry; + u_char *buf; + size_t size; + size_t max; + size_t wpos; + size_t rpos; + int fd; }; struct msgbuf { - TAILQ_HEAD(, ibuf) bufs; - u_int32_t queued; - int fd; + TAILQ_HEAD(, ibuf) bufs; + u_int32_t queued; + int fd; }; struct ibuf_read { - u_char buf[IBUF_READ_SIZE]; - u_char *rptr; - size_t wpos; + u_char buf[IBUF_READ_SIZE]; + u_char *rptr; + size_t wpos; }; struct imsg_fd { - TAILQ_ENTRY(imsg_fd) entry; - int fd; + TAILQ_ENTRY(imsg_fd) entry; + int fd; }; struct imsgbuf { - TAILQ_HEAD(, imsg_fd) fds; - struct ibuf_read r; - struct msgbuf w; - int fd; - pid_t pid; + TAILQ_HEAD(, imsg_fd) fds; + struct ibuf_read r; + struct msgbuf w; + int fd; + pid_t pid; }; #define IMSGF_HASFD 1 struct imsg_hdr { - u_int32_t type; - u_int16_t len; - u_int16_t flags; - u_int32_t peerid; - u_int32_t pid; + u_int32_t type; + u_int16_t len; + u_int16_t flags; + u_int32_t peerid; + u_int32_t pid; }; struct imsg { - struct imsg_hdr hdr; - int fd; - void *data; + struct imsg_hdr hdr; + int fd; + void *data; }; /* buffer.c */ -struct ibuf *ibuf_open(size_t); -struct ibuf *ibuf_dynamic(size_t, size_t); -int ibuf_add(struct ibuf *, const void *, size_t); -void *ibuf_reserve(struct ibuf *, size_t); -void *ibuf_seek(struct ibuf *, size_t, size_t); -size_t ibuf_size(struct ibuf *); -size_t ibuf_left(struct ibuf *); -void ibuf_close(struct msgbuf *, struct ibuf *); -int ibuf_write(struct msgbuf *); -void ibuf_free(struct ibuf *); -void msgbuf_init(struct msgbuf *); -void msgbuf_clear(struct msgbuf *); -int msgbuf_write(struct msgbuf *); -void msgbuf_drain(struct msgbuf *, size_t); +struct ibuf *ibuf_open(size_t); +struct ibuf *ibuf_dynamic(size_t, size_t); +int ibuf_add(struct ibuf *, const void *, size_t); +void *ibuf_reserve(struct ibuf *, size_t); +void *ibuf_seek(struct ibuf *, size_t, size_t); +size_t ibuf_size(struct ibuf *); +size_t ibuf_left(struct ibuf *); +void ibuf_close(struct msgbuf *, struct ibuf *); +int ibuf_write(struct msgbuf *); +void ibuf_free(struct ibuf *); +void msgbuf_init(struct msgbuf *); +void msgbuf_clear(struct msgbuf *); +int msgbuf_write(struct msgbuf *); +void msgbuf_drain(struct msgbuf *, size_t); /* imsg.c */ -void imsg_init(struct imsgbuf *, int); -ssize_t imsg_read(struct imsgbuf *); -ssize_t imsg_get(struct imsgbuf *, struct imsg *); -int imsg_compose(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, int, - const void *, u_int16_t); -int imsg_composev(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, int, - const struct iovec *, int); +void imsg_init(struct imsgbuf *, int); +ssize_t imsg_read(struct imsgbuf *); +ssize_t imsg_get(struct imsgbuf *, struct imsg *); +int imsg_compose(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, + int, const void *, u_int16_t); +int imsg_composev(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, + int, const struct iovec *, int); struct ibuf *imsg_create(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, - u_int16_t); -int imsg_add(struct ibuf *, const void *, u_int16_t); -void imsg_close(struct imsgbuf *, struct ibuf *); -void imsg_free(struct imsg *); -int imsg_flush(struct imsgbuf *); -void imsg_clear(struct imsgbuf *); + u_int16_t); +int imsg_add(struct ibuf *, const void *, u_int16_t); +void imsg_close(struct imsgbuf *, struct ibuf *); +void imsg_free(struct imsg *); +int imsg_flush(struct imsgbuf *); +void imsg_clear(struct imsgbuf *); #endif diff --git a/lib/openbsd-tree.c b/lib/openbsd-tree.c index 5d77ac2a47..7e753554c9 100644 --- a/lib/openbsd-tree.c +++ b/lib/openbsd-tree.c @@ -45,14 +45,16 @@ #include <lib/openbsd-tree.h> -static inline struct rb_entry *rb_n2e(const struct rb_type *t, void *node) +static inline struct rb_entry * +rb_n2e(const struct rb_type *t, void *node) { unsigned long addr = (unsigned long)node; return ((struct rb_entry *)(addr + t->t_offset)); } -static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe) +static inline void * +rb_e2n(const struct rb_type *t, struct rb_entry *rbe) { unsigned long addr = (unsigned long)rbe; @@ -66,33 +68,37 @@ static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe) #define RBH_ROOT(_rbt) (_rbt)->rbt_root -static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) { RBE_PARENT(rbe) = parent; RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; RBE_COLOR(rbe) = RB_RED; } -static inline void rbe_set_blackred(struct rb_entry *black, - struct rb_entry *red) +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) { RBE_COLOR(black) = RB_BLACK; RBE_COLOR(red) = RB_RED; } -static inline void rbe_augment(const struct rb_type *t, struct rb_entry *rbe) +static inline void +rbe_augment(const struct rb_type *t, struct rb_entry *rbe) { (*t->t_augment)(rb_e2n(t, rbe)); } -static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) +static inline void +rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) { if (t->t_augment != NULL) rbe_augment(t, rbe); } -static inline void rbe_rotate_left(const struct rb_type *t, - struct rbt_tree *rbt, struct rb_entry *rbe) +static inline void +rbe_rotate_left(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) { struct rb_entry *parent; struct rb_entry *tmp; @@ -124,8 +130,9 @@ static inline void rbe_rotate_left(const struct rb_type *t, } } -static inline void rbe_rotate_right(const struct rb_type *t, - struct rbt_tree *rbt, struct rb_entry *rbe) +static inline void +rbe_rotate_right(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) { struct rb_entry *parent; struct rb_entry *tmp; @@ -157,13 +164,14 @@ static inline void rbe_rotate_right(const struct rb_type *t, } } -static inline void rbe_insert_color(const struct rb_type *t, - struct rbt_tree *rbt, struct rb_entry *rbe) +static inline void +rbe_insert_color(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) { struct rb_entry *parent, *gparent, *tmp; - while ((parent = RBE_PARENT(rbe)) != NULL - && RBE_COLOR(parent) == RB_RED) { + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RB_RED) { gparent = RBE_PARENT(parent); if (parent == RBE_LEFT(gparent)) { @@ -208,10 +216,9 @@ static inline void rbe_insert_color(const struct rb_type *t, RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK; } -static inline void rbe_remove_color(const struct rb_type *t, - struct rbt_tree *rbt, - struct rb_entry *parent, - struct rb_entry *rbe) +static inline void +rbe_remove_color(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *parent, struct rb_entry *rbe) { struct rb_entry *tmp; @@ -219,8 +226,8 @@ static inline void rbe_remove_color(const struct rb_type *t, if (parent == NULL) return; - while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) - && rbe != RBH_ROOT(rbt)) { + while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + rbe != RBH_ROOT(rbt)) { if (RBE_LEFT(parent) == rbe) { tmp = RBE_RIGHT(parent); if (RBE_COLOR(tmp) == RB_RED) { @@ -228,16 +235,16 @@ static inline void rbe_remove_color(const struct rb_type *t, rbe_rotate_left(t, rbt, parent); tmp = RBE_RIGHT(parent); } - if ((RBE_LEFT(tmp) == NULL - || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) - && (RBE_RIGHT(tmp) == NULL - || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { RBE_COLOR(tmp) = RB_RED; rbe = parent; parent = RBE_PARENT(rbe); } else { - if (RBE_RIGHT(tmp) == NULL - || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { struct rb_entry *oleft; oleft = RBE_LEFT(tmp); @@ -266,16 +273,16 @@ static inline void rbe_remove_color(const struct rb_type *t, tmp = RBE_LEFT(parent); } - if ((RBE_LEFT(tmp) == NULL - || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) - && (RBE_RIGHT(tmp) == NULL - || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { RBE_COLOR(tmp) = RB_RED; rbe = parent; parent = RBE_PARENT(rbe); } else { - if (RBE_LEFT(tmp) == NULL - || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { struct rb_entry *oright; oright = RBE_RIGHT(tmp); @@ -385,7 +392,8 @@ color: return (old); } -void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm) +void * +_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm) { struct rb_entry *rbe = rb_n2e(t, elm); struct rb_entry *old; @@ -395,7 +403,8 @@ void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm) return (old == NULL ? NULL : rb_e2n(t, old)); } -void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm) +void * +_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm) { struct rb_entry *rbe = rb_n2e(t, elm); struct rb_entry *tmp; @@ -435,7 +444,8 @@ void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm) } /* Finds the node with the same key as elm */ -void *_rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key) +void * +_rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key) { struct rb_entry *tmp = RBH_ROOT(rbt); void *node; @@ -456,7 +466,8 @@ void *_rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key) } /* Finds the first node greater than or equal to the search key */ -void *_rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key) +void * +_rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key) { struct rb_entry *tmp = RBH_ROOT(rbt); void *node; @@ -478,7 +489,8 @@ void *_rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key) return (res); } -void *_rb_next(const struct rb_type *t, void *elm) +void * +_rb_next(const struct rb_type *t, void *elm) { struct rb_entry *rbe = rb_n2e(t, elm); @@ -487,11 +499,12 @@ void *_rb_next(const struct rb_type *t, void *elm) while (RBE_LEFT(rbe) != NULL) rbe = RBE_LEFT(rbe); } else { - if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) rbe = RBE_PARENT(rbe); else { - while (RBE_PARENT(rbe) - && (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) rbe = RBE_PARENT(rbe); rbe = RBE_PARENT(rbe); } @@ -500,7 +513,8 @@ void *_rb_next(const struct rb_type *t, void *elm) return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } -void *_rb_prev(const struct rb_type *t, void *elm) +void * +_rb_prev(const struct rb_type *t, void *elm) { struct rb_entry *rbe = rb_n2e(t, elm); @@ -509,11 +523,12 @@ void *_rb_prev(const struct rb_type *t, void *elm) while (RBE_RIGHT(rbe)) rbe = RBE_RIGHT(rbe); } else { - if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) rbe = RBE_PARENT(rbe); else { - while (RBE_PARENT(rbe) - && (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) rbe = RBE_PARENT(rbe); rbe = RBE_PARENT(rbe); } @@ -522,14 +537,16 @@ void *_rb_prev(const struct rb_type *t, void *elm) return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } -void *_rb_root(const struct rb_type *t, struct rbt_tree *rbt) +void * +_rb_root(const struct rb_type *t, struct rbt_tree *rbt) { struct rb_entry *rbe = RBH_ROOT(rbt); return (rbe == NULL ? rbe : rb_e2n(t, rbe)); } -void *_rb_min(const struct rb_type *t, struct rbt_tree *rbt) +void * +_rb_min(const struct rb_type *t, struct rbt_tree *rbt) { struct rb_entry *rbe = RBH_ROOT(rbt); struct rb_entry *parent = NULL; @@ -542,7 +559,8 @@ void *_rb_min(const struct rb_type *t, struct rbt_tree *rbt) return (parent == NULL ? NULL : rb_e2n(t, parent)); } -void *_rb_max(const struct rb_type *t, struct rbt_tree *rbt) +void * +_rb_max(const struct rb_type *t, struct rbt_tree *rbt) { struct rb_entry *rbe = RBH_ROOT(rbt); struct rb_entry *parent = NULL; @@ -555,28 +573,32 @@ void *_rb_max(const struct rb_type *t, struct rbt_tree *rbt) return (parent == NULL ? NULL : rb_e2n(t, parent)); } -void *_rb_left(const struct rb_type *t, void *node) +void * +_rb_left(const struct rb_type *t, void *node) { struct rb_entry *rbe = rb_n2e(t, node); rbe = RBE_LEFT(rbe); return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } -void *_rb_right(const struct rb_type *t, void *node) +void * +_rb_right(const struct rb_type *t, void *node) { struct rb_entry *rbe = rb_n2e(t, node); rbe = RBE_RIGHT(rbe); return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } -void *_rb_parent(const struct rb_type *t, void *node) +void * +_rb_parent(const struct rb_type *t, void *node) { struct rb_entry *rbe = rb_n2e(t, node); rbe = RBE_PARENT(rbe); return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } -void _rb_set_left(const struct rb_type *t, void *node, void *left) +void +_rb_set_left(const struct rb_type *t, void *node, void *left) { struct rb_entry *rbe = rb_n2e(t, node); struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left); @@ -584,7 +606,8 @@ void _rb_set_left(const struct rb_type *t, void *node, void *left) RBE_LEFT(rbe) = rbl; } -void _rb_set_right(const struct rb_type *t, void *node, void *right) +void +_rb_set_right(const struct rb_type *t, void *node, void *right) { struct rb_entry *rbe = rb_n2e(t, node); struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right); @@ -592,7 +615,8 @@ void _rb_set_right(const struct rb_type *t, void *node, void *right) RBE_RIGHT(rbe) = rbr; } -void _rb_set_parent(const struct rb_type *t, void *node, void *parent) +void +_rb_set_parent(const struct rb_type *t, void *node, void *parent) { struct rb_entry *rbe = rb_n2e(t, node); struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent); @@ -600,19 +624,21 @@ void _rb_set_parent(const struct rb_type *t, void *node, void *parent) RBE_PARENT(rbe) = rbp; } -void _rb_poison(const struct rb_type *t, void *node, unsigned long poison) +void +_rb_poison(const struct rb_type *t, void *node, unsigned long poison) { struct rb_entry *rbe = rb_n2e(t, node); RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) = - (struct rb_entry *)poison; + (struct rb_entry *)poison; } -int _rb_check(const struct rb_type *t, void *node, unsigned long poison) +int +_rb_check(const struct rb_type *t, void *node, unsigned long poison) { struct rb_entry *rbe = rb_n2e(t, node); - return ((unsigned long)RBE_PARENT(rbe) == poison - && (unsigned long)RBE_LEFT(rbe) == poison - && (unsigned long)RBE_RIGHT(rbe) == poison); + return ((unsigned long)RBE_PARENT(rbe) == poison && + (unsigned long)RBE_LEFT(rbe) == poison && + (unsigned long)RBE_RIGHT(rbe) == poison); } diff --git a/lib/openbsd-tree.h b/lib/openbsd-tree.h index 859f751678..22cb9252f5 100644 --- a/lib/openbsd-tree.h +++ b/lib/openbsd-tree.h @@ -24,7 +24,7 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef _SYS_TREE_H_ +#ifndef _SYS_TREE_H_ #define _SYS_TREE_H_ /* @@ -54,26 +54,23 @@ * The maximum height of a red-black tree is 2lg (n+1). */ -#define SPLAY_HEAD(name, type) \ - struct name { \ - struct type *sph_root; /* root of the tree */ \ - } +#define SPLAY_HEAD(name, type) \ +struct name { \ + struct type *sph_root; /* root of the tree */ \ +} -#define SPLAY_INITIALIZER(root) \ - { \ - NULL \ - } +#define SPLAY_INITIALIZER(root) \ + { NULL } -#define SPLAY_INIT(root) \ - do { \ - (root)->sph_root = NULL; \ - } while (0) +#define SPLAY_INIT(root) do { \ + (root)->sph_root = NULL; \ +} while (0) -#define SPLAY_ENTRY(type) \ - struct { \ - struct type *spe_left; /* left element */ \ - struct type *spe_right; /* right element */ \ - } +#define SPLAY_ENTRY(type) \ +struct { \ + struct type *spe_left; /* left element */ \ + struct type *spe_right; /* right element */ \ +} #define SPLAY_LEFT(elm, field) (elm)->field.spe_left #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right @@ -81,220 +78,197 @@ #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ - do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) \ - do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (0) - -#define SPLAY_LINKLEFT(head, tmp, field) \ - do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - } while (0) - -#define SPLAY_LINKRIGHT(head, tmp, field) \ - do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } while (0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) \ - do { \ - SPLAY_RIGHT(left, field) = \ - SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = \ - SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT((head)->sph_root, field) = \ - SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = \ - SPLAY_LEFT(node, field); \ - } while (0) +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_LINKLEFT(head, tmp, field) do { \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_LINKRIGHT(head, tmp, field) do { \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ +} while (0) /* Generates prototypes and inline functions */ -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ - void name##_SPLAY(struct name *, struct type *); \ - void name##_SPLAY_MINMAX(struct name *, int); \ - struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ - struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ - \ - /* Finds the node with the same key as elm */ \ - static __inline struct type *name##_SPLAY_FIND(struct name *head, \ - struct type *elm) \ - { \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ - } \ - \ - static __inline struct type *name##_SPLAY_NEXT(struct name *head, \ - struct type *elm) \ - { \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ - } \ - \ - static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head, \ - int val) \ - { \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ - } +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ +void name##_SPLAY(struct name *, struct type *); \ +void name##_SPLAY_MINMAX(struct name *, int); \ +struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ +struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ + \ +/* Finds the node with the same key as elm */ \ +static __inline struct type * \ +name##_SPLAY_FIND(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) \ + return(NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) \ + return (head->sph_root); \ + return (NULL); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_NEXT(struct name *head, struct type *elm) \ +{ \ + name##_SPLAY(head, elm); \ + if (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + while (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_MIN_MAX(struct name *head, int val) \ +{ \ + name##_SPLAY_MINMAX(head, val); \ + return (SPLAY_ROOT(head)); \ +} /* Main splay operation. * Moves node close to the key of elm to top */ -#define SPLAY_GENERATE(name, type, field, cmp) \ - struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) \ - { \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = \ - NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if (__comp < 0) { \ - SPLAY_LEFT(elm, field) = \ - SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = \ - SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ - } \ - \ - struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ - { \ - struct type *__tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = \ - SPLAY_RIGHT((head)->sph_root, field); \ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = \ - SPLAY_LEFT((head)->sph_root, field); \ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ - } \ - \ - void name##_SPLAY(struct name *head, struct type *elm) \ - { \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \ - NULL; \ - __left = __right = &__node; \ - \ - while ((__comp = (cmp)(elm, (head)->sph_root))) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, \ - field); \ - if (SPLAY_LEFT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } \ - \ - /* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ - void name##_SPLAY_MINMAX(struct name *head, int __comp) \ - { \ - struct type __node, *__left, *__right, *__tmp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \ - NULL; \ - __left = __right = &__node; \ - \ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, \ - field); \ - if (SPLAY_LEFT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, \ - field) \ - == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } +#define SPLAY_GENERATE(name, type, field, cmp) \ +struct type * \ +name##_SPLAY_INSERT(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) { \ + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ + } else { \ + int __comp; \ + name##_SPLAY(head, elm); \ + __comp = (cmp)(elm, (head)->sph_root); \ + if(__comp < 0) { \ + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ + SPLAY_RIGHT(elm, field) = (head)->sph_root; \ + SPLAY_LEFT((head)->sph_root, field) = NULL; \ + } else if (__comp > 0) { \ + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT(elm, field) = (head)->sph_root; \ + SPLAY_RIGHT((head)->sph_root, field) = NULL; \ + } else \ + return ((head)->sph_root); \ + } \ + (head)->sph_root = (elm); \ + return (NULL); \ +} \ + \ +struct type * \ +name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *__tmp; \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) { \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ + } else { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ + name##_SPLAY(head, elm); \ + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ + } \ + return (elm); \ + } \ + return (NULL); \ +} \ + \ +void \ +name##_SPLAY(struct name *head, struct type *elm) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ + int __comp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while ((__comp = (cmp)(elm, (head)->sph_root))) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) > 0){ \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} \ + \ +/* Splay with either the minimum or the maximum element \ + * Used to find minimum or maximum element in tree. \ + */ \ +void name##_SPLAY_MINMAX(struct name *head, int __comp) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while (1) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} #define SPLAY_NEGINF -1 #define SPLAY_INF 1 @@ -303,13 +277,14 @@ #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) \ - (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) \ - (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); (x) != NULL; \ +#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) +#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); \ + (x) != NULL; \ (x) = SPLAY_NEXT(name, head, x)) /* @@ -332,197 +307,203 @@ #define RB_RED 1 struct rb_type { - int (*t_compare)(const void *, const void *); - void (*t_augment)(void *); - unsigned int t_offset; /* offset of rb_entry in type */ + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + unsigned int t_offset; /* offset of rb_entry in type */ }; struct rbt_tree { - struct rb_entry *rbt_root; + 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; + struct rb_entry *rbt_parent; + struct rb_entry *rbt_left; + struct rb_entry *rbt_right; + unsigned int rbt_color; }; -#define RB_HEAD(_name, _type) \ - struct _name { \ - struct rbt_tree rbh_root; \ - } +#define RB_HEAD(_name, _type) \ +struct _name { \ + struct rbt_tree rbh_root; \ +} #define RB_ENTRY(_type) struct rb_entry -static inline void _rb_init(struct rbt_tree *rbt) +static inline void +_rb_init(struct rbt_tree *rbt) { rbt->rbt_root = NULL; } -static inline int _rb_empty(struct rbt_tree *rbt) +static inline int +_rb_empty(struct rbt_tree *rbt) { return (rbt->rbt_root == NULL); } -void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *); -void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *); -void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *); -void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *); -void *_rb_root(const struct rb_type *, struct rbt_tree *); -void *_rb_min(const struct rb_type *, struct rbt_tree *); -void *_rb_max(const struct rb_type *, struct rbt_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); +void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rbt_tree *); +void *_rb_min(const struct rb_type *, struct rbt_tree *); +void *_rb_max(const struct rb_type *, struct rbt_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 RB_INITIALIZER(_head) { { NULL } } -#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ - extern const struct rb_type *const _name##_RB_TYPE; \ - \ - __attribute__((__unused__)) static inline void _name##_RB_INIT( \ - struct _name *head) \ - { \ - _rb_init(&head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_INSERT(struct _name *head, struct _type *elm) \ - { \ - return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ - { \ - return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_FIND(struct _name *head, const struct _type *key) \ - { \ - return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_NFIND(struct _name *head, const struct _type *key) \ - { \ - return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_ROOT(struct _name *head) \ - { \ - return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline int _name##_RB_EMPTY( \ - struct _name *head) \ - { \ - return _rb_empty(&head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_MIN(struct _name *head) \ - { \ - return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_MAX(struct _name *head) \ - { \ - return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_NEXT(struct _type *elm) \ - { \ - return _rb_next(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_PREV(struct _type *elm) \ - { \ - return _rb_prev(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_LEFT(struct _type *elm) \ - { \ - return _rb_left(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_RIGHT(struct _type *elm) \ - { \ - return _rb_right(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline struct _type \ - *_name##_RB_PARENT(struct _type *elm) \ - { \ - return _rb_parent(_name##_RB_TYPE, elm); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_LEFT( \ - struct _type *elm, struct _type *left) \ - { \ - return _rb_set_left(_name##_RB_TYPE, elm, left); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT( \ - struct _type *elm, struct _type *right) \ - { \ - return _rb_set_right(_name##_RB_TYPE, elm, right); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_SET_PARENT( \ - struct _type *elm, struct _type *parent) \ - { \ - return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ - } \ - \ - __attribute__((__unused__)) static inline void _name##_RB_POISON( \ - struct _type *elm, unsigned long poison) \ - { \ - return _rb_poison(_name##_RB_TYPE, elm, poison); \ - } \ - \ - __attribute__((__unused__)) static inline int _name##_RB_CHECK( \ - struct _type *elm, unsigned long poison) \ - { \ - return _rb_check(_name##_RB_TYPE, elm, poison); \ - } - -#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ - static int _name##_RB_COMPARE(const void *lptr, const void *rptr) \ - { \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ - } \ - static const struct rb_type _name##_RB_INFO = { \ - _name##_RB_COMPARE, _aug, offsetof(struct _type, _field), \ - }; \ - const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; - -#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ - static void _name##_RB_AUGMENT(void *ptr) \ - { \ - struct _type *p = ptr; \ - return _aug(p); \ - } \ - RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) - -#define RB_GENERATE(_name, _type, _field, _cmp) \ - RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) +#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RB_TYPE; \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline int \ +_name##_RB_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + return _rb_set_left(_name##_RB_TYPE, elm, left); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + return _rb_set_right(_name##_RB_TYPE, elm, right); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RB_TYPE, elm, poison); \ +} \ + \ +__attribute__((__unused__)) static inline int \ +_name##_RB_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RB_TYPE, elm, poison); \ +} + +#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RB_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RB_INFO = { \ + _name##_RB_COMPARE, \ + _aug, \ + offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; + +#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RB_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) + +#define RB_GENERATE(_name, _type, _field, _cmp) \ + RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) #define RB_INIT(_name, _head) _name##_RB_INIT(_head) #define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm) @@ -544,20 +525,24 @@ int _rb_check(const struct rb_type *, void *, unsigned long); #define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p) #define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p) -#define RB_FOREACH(_e, _name, _head) \ - for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL; \ +#define RB_FOREACH(_e, _name, _head) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL; \ (_e) = RB_NEXT(_name, (_e))) -#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RB_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n)) +#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) -#define RB_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL; \ +#define RB_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL; \ (_e) = RB_PREV(_name, (_e))) -#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RB_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n)) +#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); \ + (_e) = (_n)) -#endif /* _SYS_TREE_H_ */ +#endif /* _SYS_TREE_H_ */ |