From 76c2e7178afccd65834c94694ac447ee4c5d7d6f Mon Sep 17 00:00:00 2001 From: ToMe25 Date: Sun, 18 Apr 2021 23:36:43 +0200 Subject: Fix remaining compile errors Finalize(hopefully) procmap.c fix copy stub procio.c to fix compile errors undo rb workaround --- sysdeps/openbsd/Makefile.am | 2 +- sysdeps/openbsd/glibtop_server.h | 2 + sysdeps/openbsd/procio.c | 43 ++++ sysdeps/openbsd/procmap.c | 69 +++--- sysdeps/openbsd/rb_workaround.h | 441 --------------------------------------- 5 files changed, 79 insertions(+), 478 deletions(-) create mode 100644 sysdeps/openbsd/procio.c delete mode 100644 sysdeps/openbsd/rb_workaround.h diff --git a/sysdeps/openbsd/Makefile.am b/sysdeps/openbsd/Makefile.am index 8f62eae8..41b4b6b0 100644 --- a/sysdeps/openbsd/Makefile.am +++ b/sysdeps/openbsd/Makefile.am @@ -15,7 +15,7 @@ libgtop_sysdeps_suid_2_0_la_SOURCES = suid_open.c close.c swap.c \ proclist.c procstate.c procuid.c \ proctime.c procmem.c procsignal.c \ prockernel.c procsegment.c procargs.c \ - procmap.c netload.c ppp.c + procmap.c netload.c ppp.c procio.c # TODO should be made nosuid like FreeBSD libgtop_sysdeps_suid_2_0_la_SOURCES += shm_limits.c msg_limits.c sem_limits.c diff --git a/sysdeps/openbsd/glibtop_server.h b/sysdeps/openbsd/glibtop_server.h index fc9bb303..54ca8cbb 100644 --- a/sysdeps/openbsd/glibtop_server.h +++ b/sysdeps/openbsd/glibtop_server.h @@ -47,6 +47,8 @@ G_BEGIN_DECLS #define GLIBTOP_SUID_NETLIST 0 #define GLIBTOP_SUID_PROC_WD 0 #define GLIBTOP_SUID_PROC_AFFINITY 0 +#define GLIBTOP_SUID_PROC_IO 0 +#define GLIBTOP_SUID_PROC_OPEN_FILES 0 G_END_DECLS diff --git a/sysdeps/openbsd/procio.c b/sysdeps/openbsd/procio.c new file mode 100644 index 00000000..a4846aee --- /dev/null +++ b/sysdeps/openbsd/procio.c @@ -0,0 +1,43 @@ +/* Copyright (C) 2017 Robert Roth + This file is part of LibGTop. + + Contributed by Robert Roth , February 2017. + + LibGTop is free software; you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, + or (at your option) any later version. + + LibGTop is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with LibGTop; see the file COPYING. If not, write to the + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. +*/ + +#include +#include +#include + +static const unsigned long _glibtop_sysdeps_proc_io = 0; + +/* Init function. */ + +void +_glibtop_init_proc_io_s (glibtop *server) +{ + server->sysdeps.proc_io = _glibtop_sysdeps_proc_io; +} + +/* Provides detailed information about a process. */ + +void +glibtop_get_proc_io_s (glibtop *server, glibtop_proc_io *buf, + pid_t pid) +{ + memset (buf, 0, sizeof (glibtop_proc_io)); +} diff --git a/sysdeps/openbsd/procmap.c b/sysdeps/openbsd/procmap.c index 8e8aa3ad..ba0db2cf 100644 --- a/sysdeps/openbsd/procmap.c +++ b/sysdeps/openbsd/procmap.c @@ -26,8 +26,6 @@ #include -#include - #include #include #include @@ -47,7 +45,6 @@ #include typedef int boolean_t; -#undef _KERNEL #define _UVM_UVM_AMAP_I_H_ 1 #define _UVM_UVM_MAP_I_H_ 1 #include @@ -61,14 +58,26 @@ static const unsigned long _glibtop_sysdeps_map_entry = (1L << GLIBTOP_MAP_ENTRY_OFFSET) + (1L << GLIBTOP_MAP_ENTRY_PERM) + (1L << GLIBTOP_MAP_ENTRY_INODE) + (1L << GLIBTOP_MAP_ENTRY_DEVICE); +/* + * Don't implement address comparison. + */ +static int __inline +no_impl(const void *p, const void *q) +{ + abort(); /* Should not be called. */ + return 0; +} + +RBT_PROTOTYPE(uvm_map_addr, vm_map_entry, daddrs.addr_entry, no_impl); +RBT_GENERATE(uvm_map_addr, vm_map_entry, daddrs.addr_entry, no_impl); + /* Local helper functions. */ -ssize_t load_vmmap_entries(glibtop*, unsigned long, struct vm_map_entry**, +ssize_t load_vmmap_entries(glibtop*, unsigned long, struct vm_map_entry*, struct vm_map_entry*); void unload_vmmap_entries(struct vm_map_entry *); /* Init function. */ - void _glibtop_init_proc_map_p (glibtop *server) { @@ -85,7 +94,7 @@ _glibtop_init_proc_map_p (glibtop *server) */ ssize_t load_vmmap_entries(glibtop *server, unsigned long kptr, - struct vm_map_entry **rptr, struct vm_map_entry *parent) + struct vm_map_entry *rptr, struct vm_map_entry *parent) { struct vm_map_entry *entry; unsigned long left_kptr, right_kptr; @@ -112,17 +121,17 @@ load_vmmap_entries(glibtop *server, unsigned long kptr, * We save the kernel pointers in {left,right}_kptr, so we have them * available to download children. */ - left_kptr = (unsigned long) RBE_LEFT(entry, daddrs.addr_entry); - right_kptr = (unsigned long) RBE_RIGHT(entry, daddrs.addr_entry); - RBE_LEFT(entry, daddrs.addr_entry) = - RBE_RIGHT(entry, daddrs.addr_entry) = NULL; + left_kptr = (unsigned long) RBT_LEFT(uvm_map_addr, entry); + right_kptr = (unsigned long) RBT_RIGHT(uvm_map_addr, entry); + entry->daddrs.addr_entry.rbt_left = + entry->daddrs.addr_entry.rbt_right = NULL; /* Fill in parent pointer. */ - RBE_PARENT(entry, daddrs.addr_entry) = parent; + entry->daddrs.addr_entry.rbt_parent = &parent->daddrs.addr_entry; /* * Consistent state reached, fill in *rptr. */ - *rptr = entry; + rptr = entry; /* * Download left, right. @@ -130,11 +139,11 @@ load_vmmap_entries(glibtop *server, unsigned long kptr, * unload_vmmap_entries. */ left_sz = load_vmmap_entries(server, left_kptr, - &RBE_LEFT(entry, daddrs.addr_entry), entry); + RBT_LEFT(uvm_map_addr, entry), entry); if (left_sz == -1) return -1; right_sz = load_vmmap_entries(server, right_kptr, - &RBE_RIGHT(entry, daddrs.addr_entry), entry); + RBT_RIGHT(uvm_map_addr, entry), entry); if (right_sz == -1) return -1; @@ -150,8 +159,8 @@ unload_vmmap_entries(struct vm_map_entry *entry) if (entry == NULL) return; - unload_vmmap_entries(RBE_LEFT(entry, daddrs.addr_entry)); - unload_vmmap_entries(RBE_RIGHT(entry, daddrs.addr_entry)); + unload_vmmap_entries(RBT_LEFT(uvm_map_addr, entry)); + unload_vmmap_entries(RBT_RIGHT(uvm_map_addr, entry)); free(entry); } @@ -203,12 +212,12 @@ glibtop_get_proc_map_p (glibtop *server, glibtop_proc_map *buf, return NULL; } - RB_INIT(&root); + RBT_INIT(uvm_map_addr, &root); nentries = load_vmmap_entries(server, - (unsigned long) &RB_ROOT(&vmspace.vm_map.addr), - &RB_ROOT(&root), NULL); + (unsigned long) RBT_ROOT(uvm_map_addr, &vmspace.vm_map.addr), + RBT_ROOT(uvm_map_addr, &root), NULL); if (nentries == -1) { - unload_vmmap_entries(&RB_ROOT(&root)); + unload_vmmap_entries(RBT_ROOT(uvm_map_addr, &root)); glibtop_error_io_r (server, "kvm_read (entry)"); } @@ -228,7 +237,7 @@ glibtop_get_proc_map_p (glibtop *server, glibtop_proc_map *buf, * to OBJT_DEFAULT so it seems this really works. */ - RBE_FOREACH(entry, uvm_map_addr, &root) { + RBT_FOREACH(entry, uvm_map_addr, &root) { glibtop_map_entry *mentry; unsigned long inum, dev; guint len; @@ -244,7 +253,7 @@ glibtop_get_proc_map_p (glibtop *server, glibtop_proc_map *buf, (unsigned long) entry->object.uvm_obj, &vnode, sizeof (vnode)) != sizeof (vnode)) { glibtop_warn_io_r (server, "kvm_read (vnode)"); - unload_vmmap_entries(&RB_ROOT(&root)); + unload_vmmap_entries(RBT_ROOT(uvm_map_addr, &root)); glibtop_suid_leave (server); return (glibtop_map_entry*) g_array_free(maps, TRUE); } @@ -260,7 +269,7 @@ glibtop_get_proc_map_p (glibtop *server, glibtop_proc_map *buf, (unsigned long) vnode.v_data, &inode, sizeof (inode)) != sizeof (inode)) { glibtop_warn_io_r (server, "kvm_read (inode)"); - unload_vmmap_entries(&RB_ROOT(&root)); + unload_vmmap_entries(RBT_ROOT(uvm_map_addr, &root)); glibtop_suid_leave (server); return (glibtop_map_entry*) g_array_free(maps, TRUE); } @@ -298,18 +307,6 @@ glibtop_get_proc_map_p (glibtop *server, glibtop_proc_map *buf, buf->size = sizeof (glibtop_map_entry); buf->total = buf->number * buf->size; - unload_vmmap_entries(&RB_ROOT(&root)); + unload_vmmap_entries(RBT_ROOT(uvm_map_addr, &root)); return (glibtop_map_entry*) g_array_free(maps, FALSE); } - -/* - * Don't implement address comparison. - */ -static __inline int -no_impl(void *p, void *q) -{ - abort(); /* Should not be called. */ - return 0; -} - -RBE_GENERATE(uvm_map_addr, vm_map_entry, daddrs.addr_entry, no_impl); diff --git a/sysdeps/openbsd/rb_workaround.h b/sysdeps/openbsd/rb_workaround.h deleted file mode 100644 index 653eb4ed..00000000 --- a/sysdeps/openbsd/rb_workaround.h +++ /dev/null @@ -1,441 +0,0 @@ -/* - * This entire header file is a horrible workaround that probably shouldn't be used, - * but exists until a better solution is found. - */ -#ifndef _RB_WORKAROUND_H_ -#define _RB_WORKAOURND_H_ - -#define RBE_LEFT(elm, field) (elm)->field.rbt_left -#define RBE_RIGHT(elm, field) (elm)->field.rbt_right -#define RBE_PARENT(elm, field) (elm)->field.rbt_parent -#define RBE_COLOR(elm, field) (elm)->field.rbt_color - -#define RBE_SET(elm, parent, field) do { \ - RBE_PARENT(elm, field) = parent; \ - RBE_LEFT(elm, field) = RBE_RIGHT(elm, field) = NULL; \ - RBE_COLOR(elm, field) = RB_RED; \ -} while (0) - -#define RBE_SET_BLACKRED(black, red, field) do { \ - RBE_COLOR(black, field) = RB_BLACK; \ - RBE_COLOR(red, field) = RB_RED; \ -} while (0) - -#ifndef RBE_AUGMENT -#define RBE_AUGMENT(x) do {} while (0) -#endif - -#define RBE_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RBE_RIGHT(elm, field); \ - if ((RBE_RIGHT(elm, field) = RBE_LEFT(tmp, field))) { \ - RBE_PARENT(RBE_LEFT(tmp, field), field) = (elm); \ - } \ - RBE_AUGMENT(elm); \ - if ((RBE_PARENT(tmp, field) = RBE_PARENT(elm, field))) { \ - if ((elm) == RBE_LEFT(RBE_PARENT(elm, field), field)) \ - RBE_LEFT(RBE_PARENT(elm, field), field) = (tmp);\ - else \ - RBE_RIGHT(RBE_PARENT(elm, field), field) = (tmp);\ - } else \ - (head)->rbh_root = (tmp); \ - RBE_LEFT(tmp, field) = (elm); \ - RBE_PARENT(elm, field) = (tmp); \ - RBE_AUGMENT(tmp); \ - if ((RBE_PARENT(tmp, field))) \ - RBE_AUGMENT(RBE_PARENT(tmp, field)); \ -} while (0) - -#define RBE_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RBE_LEFT(elm, field); \ - if ((RBE_LEFT(elm, field) = RBE_RIGHT(tmp, field))) { \ - RBE_PARENT(RBE_RIGHT(tmp, field), field) = (elm); \ - } \ - RBE_AUGMENT(elm); \ - if ((RBE_PARENT(tmp, field) = RBE_PARENT(elm, field))) { \ - if ((elm) == RBE_LEFT(RBE_PARENT(elm, field), field)) \ - RBE_LEFT(RBE_PARENT(elm, field), field) = (tmp);\ - else \ - RBE_RIGHT(RBE_PARENT(elm, field), field) = (tmp);\ - } else \ - (head)->rbh_root = (tmp); \ - RBE_RIGHT(tmp, field) = (elm); \ - RBE_PARENT(elm, field) = (tmp); \ - RBE_AUGMENT(tmp); \ - if ((RBE_PARENT(tmp, field))) \ - RBE_AUGMENT(RBE_PARENT(tmp, field)); \ -} while (0) - -/* Generates prototypes and inline functions */ -#define RBE_PROTOTYPE(name, type, field, cmp) \ - RBE_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RBE_PROTOTYPE_STATIC(name, type, field, cmp) \ - RBE_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RBE_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RBE_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RBE_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RBE_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RBE_INSERT(struct name *, struct type *); \ -attr struct type *name##_RBE_FIND(struct name *, struct type *); \ -attr struct type *name##_RBE_NFIND(struct name *, struct type *); \ -attr struct type *name##_RBE_NEXT(struct type *); \ -attr struct type *name##_RBE_PREV(struct type *); \ -attr struct type *name##_RBE_MINMAX(struct name *, int); \ - \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RBE_GENERATE(name, type, field, cmp) \ - RBE_GENERATE_INTERNAL(name, type, field, cmp,) -#define RBE_GENERATE_STATIC(name, type, field, cmp) \ - RBE_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RBE_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RBE_INSERT_COLOR(struct name *head, struct type *elm) \ -{ \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RBE_PARENT(elm, field)) && \ - RBE_COLOR(parent, field) == RB_RED) { \ - gparent = RBE_PARENT(parent, field); \ - if (parent == RBE_LEFT(gparent, field)) { \ - tmp = RBE_RIGHT(gparent, field); \ - if (tmp && RBE_COLOR(tmp, field) == RB_RED) { \ - RBE_COLOR(tmp, field) = RB_BLACK; \ - RBE_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RBE_RIGHT(parent, field) == elm) { \ - RBE_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RBE_SET_BLACKRED(parent, gparent, field); \ - RBE_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RBE_LEFT(gparent, field); \ - if (tmp && RBE_COLOR(tmp, field) == RB_RED) { \ - RBE_COLOR(tmp, field) = RB_BLACK; \ - RBE_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RBE_LEFT(parent, field) == elm) { \ - RBE_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RBE_SET_BLACKRED(parent, gparent, field); \ - RBE_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RBE_COLOR(head->rbh_root, field) = RB_BLACK; \ -} \ - \ -attr void \ -name##_RBE_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ -{ \ - struct type *tmp; \ - while ((elm == NULL || RBE_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RBE_LEFT(parent, field) == elm) { \ - tmp = RBE_RIGHT(parent, field); \ - if (RBE_COLOR(tmp, field) == RB_RED) { \ - RBE_SET_BLACKRED(tmp, parent, field); \ - RBE_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RBE_RIGHT(parent, field); \ - } \ - if ((RBE_LEFT(tmp, field) == NULL || \ - RBE_COLOR(RBE_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RBE_RIGHT(tmp, field) == NULL || \ - RBE_COLOR(RBE_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RBE_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RBE_PARENT(elm, field); \ - } else { \ - if (RBE_RIGHT(tmp, field) == NULL || \ - RBE_COLOR(RBE_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RBE_LEFT(tmp, field)))\ - RBE_COLOR(oleft, field) = RB_BLACK;\ - RBE_COLOR(tmp, field) = RB_RED;\ - RBE_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RBE_RIGHT(parent, field); \ - } \ - RBE_COLOR(tmp, field) = RBE_COLOR(parent, field);\ - RBE_COLOR(parent, field) = RB_BLACK; \ - if (RBE_RIGHT(tmp, field)) \ - RBE_COLOR(RBE_RIGHT(tmp, field), field) = RB_BLACK;\ - RBE_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RBE_LEFT(parent, field); \ - if (RBE_COLOR(tmp, field) == RB_RED) { \ - RBE_SET_BLACKRED(tmp, parent, field); \ - RBE_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RBE_LEFT(parent, field); \ - } \ - if ((RBE_LEFT(tmp, field) == NULL || \ - RBE_COLOR(RBE_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RBE_RIGHT(tmp, field) == NULL || \ - RBE_COLOR(RBE_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RBE_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RBE_PARENT(elm, field); \ - } else { \ - if (RBE_LEFT(tmp, field) == NULL || \ - RBE_COLOR(RBE_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RBE_RIGHT(tmp, field)))\ - RBE_COLOR(oright, field) = RB_BLACK;\ - RBE_COLOR(tmp, field) = RB_RED; \ - RBE_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RBE_LEFT(parent, field); \ - } \ - RBE_COLOR(tmp, field) = RBE_COLOR(parent, field);\ - RBE_COLOR(parent, field) = RB_BLACK; \ - if (RBE_LEFT(tmp, field)) \ - RBE_COLOR(RBE_LEFT(tmp, field), field) = RB_BLACK;\ - RBE_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RBE_COLOR(elm, field) = RB_BLACK; \ -} \ - \ -attr struct type * \ -name##_RBE_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RBE_LEFT(elm, field) == NULL) \ - child = RBE_RIGHT(elm, field); \ - else if (RBE_RIGHT(elm, field) == NULL) \ - child = RBE_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RBE_RIGHT(elm, field); \ - while ((left = RBE_LEFT(elm, field))) \ - elm = left; \ - child = RBE_RIGHT(elm, field); \ - parent = RBE_PARENT(elm, field); \ - color = RBE_COLOR(elm, field); \ - if (child) \ - RBE_PARENT(child, field) = parent; \ - if (parent) { \ - if (RBE_LEFT(parent, field) == elm) \ - RBE_LEFT(parent, field) = child; \ - else \ - RBE_RIGHT(parent, field) = child; \ - RBE_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RBE_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RBE_PARENT(old, field)) { \ - if (RBE_LEFT(RBE_PARENT(old, field), field) == old)\ - RBE_LEFT(RBE_PARENT(old, field), field) = elm;\ - else \ - RBE_RIGHT(RBE_PARENT(old, field), field) = elm;\ - RBE_AUGMENT(RBE_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RBE_PARENT(RBE_LEFT(old, field), field) = elm; \ - if (RBE_RIGHT(old, field)) \ - RBE_PARENT(RBE_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RBE_AUGMENT(left); \ - } while ((left = RBE_PARENT(left, field))); \ - } \ - goto color; \ - } \ - parent = RBE_PARENT(elm, field); \ - color = RBE_COLOR(elm, field); \ - if (child) \ - RBE_PARENT(child, field) = parent; \ - if (parent) { \ - if (RBE_LEFT(parent, field) == elm) \ - RBE_LEFT(parent, field) = child; \ - else \ - RBE_RIGHT(parent, field) = child; \ - RBE_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RBE_REMOVE_COLOR(head, parent, child); \ - return (old); \ -} \ - \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RBE_INSERT(struct name *head, struct type *elm) \ -{ \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RBE_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RBE_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RBE_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RBE_LEFT(parent, field) = elm; \ - else \ - RBE_RIGHT(parent, field) = elm; \ - RBE_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RBE_INSERT_COLOR(head, elm); \ - return (NULL); \ -} \ - \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RBE_FIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RBE_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RBE_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ -} \ - \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RBE_NFIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RBE_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RBE_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RBE_NEXT(struct type *elm) \ -{ \ - if (RBE_RIGHT(elm, field)) { \ - elm = RBE_RIGHT(elm, field); \ - while (RBE_LEFT(elm, field)) \ - elm = RBE_LEFT(elm, field); \ - } else { \ - if (RBE_PARENT(elm, field) && \ - (elm == RBE_LEFT(RBE_PARENT(elm, field), field))) \ - elm = RBE_PARENT(elm, field); \ - else { \ - while (RBE_PARENT(elm, field) && \ - (elm == RBE_RIGHT(RBE_PARENT(elm, field), field)))\ - elm = RBE_PARENT(elm, field); \ - elm = RBE_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RBE_PREV(struct type *elm) \ -{ \ - if (RBE_LEFT(elm, field)) { \ - elm = RBE_LEFT(elm, field); \ - while (RBE_RIGHT(elm, field)) \ - elm = RBE_RIGHT(elm, field); \ - } else { \ - if (RBE_PARENT(elm, field) && \ - (elm == RBE_RIGHT(RBE_PARENT(elm, field), field))) \ - elm = RBE_PARENT(elm, field); \ - else { \ - while (RBE_PARENT(elm, field) && \ - (elm == RBE_LEFT(RBE_PARENT(elm, field), field)))\ - elm = RBE_PARENT(elm, field); \ - elm = RBE_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -attr struct type * \ -name##_RBE_MINMAX(struct name *head, int val) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RBE_LEFT(tmp, field); \ - else \ - tmp = RBE_RIGHT(tmp, field); \ - } \ - return (parent); \ -} - -#define RBE_NEGINF -1 -#define RBE_INF 1 - -#define RBE_INSERT(name, x, y) name##_RBE_INSERT(x, y) -#define RBE_REMOVE(name, x, y) name##_RBE_REMOVE(x, y) -#define RBE_FIND(name, x, y) name##_RBE_FIND(x, y) -#define RBE_NFIND(name, x, y) name##_RBE_NFIND(x, y) -#define RBE_NEXT(name, x, y) name##_RBE_NEXT(y) -#define RBE_PREV(name, x, y) name##_RBE_PREV(y) -#define RBE_MIN(name, x) name##_RBE_MINMAX(x, RBE_NEGINF) -#define RBE_MAX(name, x) name##_RBE_MINMAX(x, RBE_INF) - -#define RBE_FOREACH(x, name, head) \ - for ((x) = RBE_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RBE_NEXT(x)) - -#define RBE_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RBE_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RBE_NEXT(x), 1); \ - (x) = (y)) - -#define RBE_FOREACH_REVERSE(x, name, head) \ - for ((x) = RBE_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RBE_PREV(x)) - -#define RBE_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RBE_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RBE_PREV(x), 1); \ - (x) = (y)) - -#endif /* _RB_WORKAROUND_H_ */ -- cgit v1.2.1