From nobody Mon Oct 3 03:29:28 2022 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MgmXm6Kzpz4fHr0; Mon, 3 Oct 2022 03:29:28 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4MgmXm63gWz3GSY; Mon, 3 Oct 2022 03:29:28 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664767768; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=6Zd29mwNOr0JLbnPxRVPET2qNKVH3o1SLfxy0/Z6aEg=; b=pDGqK2j7QfWklN2iRK+Wo5zTF7wtQLWQiaZWjC1yhtGWjMRB++baA+WeUfIDX8yHQIZMT2 jF5XyzCuNOiJ9vXdA2JjkkCgFfz6yKe0M5xehdat1SmYlYI3I+YaaQ1cJmP4+SYZFWRW7u qqB+r6SCpDphi8ikU55utmSWyvLbKXkt95BovWHZCAlDbFBXTKoNcXmnyrYezriWeZuuTR KTKtAN9hMBA5ocRuUroDSm6zST1yBrmUoZqZXI0duk2ql/+T9/7JzaWmMN7OYibPPzbuYS z51xi6WRJT4zMvz1UPd92fWFTVkZYt9c3TizFTaoMI8l9+RjvZM5Vy6/pxo5YA== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4MgmXm56cZz14RN; Mon, 3 Oct 2022 03:29:28 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 2933TSqO079158; Mon, 3 Oct 2022 03:29:28 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2933TSih079157; Mon, 3 Oct 2022 03:29:28 GMT (envelope-from git) Date: Mon, 3 Oct 2022 03:29:28 GMT Message-Id: <202210030329.2933TSih079157@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 368ee2f86a0f - main - rb_tree: let insert search start from next node List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 368ee2f86a0f4f60338472be4bfd3c09ab401f87 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664767768; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=6Zd29mwNOr0JLbnPxRVPET2qNKVH3o1SLfxy0/Z6aEg=; b=Pz1KPaKtOtCz/u6F90zvOnx77hvyB34sYn8YbNOikYGs43wFtJgKqEOFMbrWPTMZyPtnt+ 52FQoLqxXQaOu15nYxD+ikcwyOTD7cwv16YG/WqA0yzBEUYdw06lnHqm3BChT+dsLdFkgb L9vwCji/cH86QD0IA+4LMQ9Tu4ddDITAzPPl3DqKYfY5J4p9cd5Nf7Sk3flMJg5EOpfKlv 77rR8b97CIGAgvx2ws/TVhWnYO+5WevYP/zfKx3oWUcV3oT1jYFjejQSt9bAL7LZ4LX4qo Jon61D8jlbuaurRMfguI2oNBy0cGFO5S7qWazdwUvafKnd9zBpTF9WkMzcqU7Q== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1664767768; a=rsa-sha256; cv=none; b=H0Qcd4NdG9BYvvG9I+8+D/7F3C1vrp1UHqf+V3LVSJt76BWuUnLsRWfTJqe7ZvlJ+N87V1 XdoSbGgBTUuifJUwHGCg75elByL1H5JaJruhZrZJd9gqwk0Y5GTMhEztUmrdP6L8X7m2yW PpqC534gn+Jbwwgey1HDYpXrRT8oEqKdf7LoqGW2aJ0kK2srKaTkp5NOr47FXcZOj2f336 H8LT8R/3iymQxcFqfkT9GLQBgYqaF2AQiXNe/lcgesXDOvohYgveNd5qOCAxRZVW2Min08 xhE+p4G8ztj7987lc19zt6Bgu04Su7yJ70JJJEzNkl0tOzK2oHiojrc3ZkznXQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=368ee2f86a0f4f60338472be4bfd3c09ab401f87 commit 368ee2f86a0f4f60338472be4bfd3c09ab401f87 Author: Doug Moore AuthorDate: 2022-10-03 03:27:21 +0000 Commit: Doug Moore CommitDate: 2022-10-03 03:27:21 +0000 rb_tree: let insert search start from next node When the node to insert in the rb_tree is known to precede or follow a particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT, defined here, allow the search for where to insert the new node begin with that particular node, rather than at the root, to save a bit of time. Using those methods, instead of RB_INSERT, in managing a tree in iommu_gas.c, saves a little time. Reviewed by: kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D35516 --- share/man/man3/tree.3 | 18 ++++++++ sys/dev/iommu/iommu_gas.c | 60 +++++++++++++------------- sys/sys/tree.h | 104 +++++++++++++++++++++++++++++++++++++++------- 3 files changed, 136 insertions(+), 46 deletions(-) diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index 27bba268da62..0c329741848f 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -97,6 +97,8 @@ .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , +.Nm RB_INSERT_NEXT , +.Nm RB_INSERT_PREV , .Nm RB_REMOVE , .Nm RB_REINSERT , .Nm RB_AUGMENT @@ -193,6 +195,10 @@ .Ft "struct TYPE *" .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" +.Fn RB_INSERT_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *next" +.Ft "struct TYPE *" +.Fn RB_INSERT_PREV NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *prev" +.Ft "struct TYPE *" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" @@ -515,6 +521,18 @@ macro inserts the new element into the tree. .Pp The +.Fn RB_INSERT_NEXT +macro inserts the new element +.Fa elm +into the tree immediately after a given element. +.Pp +The +.Fn RB_INSERT_PREV +macro inserts the new element +.Fa elm +into the tree immediately before a given element. +.Pp +The .Fn RB_REMOVE macro removes the element .Fa elm diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index c04edb8451b4..8c8d0e49c378 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -206,15 +206,6 @@ iommu_gas_check_free(struct iommu_domain *domain) } #endif -static bool -iommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry) -{ - struct iommu_map_entry *found; - - found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry); - return (found == NULL); -} - static void iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry) { @@ -255,12 +246,12 @@ iommu_gas_init_domain(struct iommu_domain *domain) end->start = domain->end; end->end = domain->end; end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; - iommu_gas_rb_insert(domain, end); + RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end); begin->start = 0; begin->end = IOMMU_PAGE_SIZE; begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; - iommu_gas_rb_insert(domain, begin); + RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin); domain->first_place = begin; domain->last_place = end; @@ -283,7 +274,7 @@ iommu_gas_fini_domain(struct iommu_domain *domain) KASSERT(entry->flags == (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), ("start entry flags %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root); @@ -292,15 +283,14 @@ iommu_gas_fini_domain(struct iommu_domain *domain) KASSERT(entry->flags == (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), ("end entry flags %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root, entry1) { KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0, ("non-RMRR entry left %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, - entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); } } @@ -326,7 +316,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, { struct iommu_map_entry *entry; iommu_gaddr_t first, size, start; - bool found __diagused; int offset; /* @@ -380,9 +369,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, entry->start = start; entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE); entry->flags = IOMMU_MAP_ENTRY_MAP; - found = iommu_gas_rb_insert(a->domain, entry); - KASSERT(found, ("found dup %p start %jx size %jx", - a->domain, (uintmax_t)start, (uintmax_t)size)); return (true); } @@ -431,7 +417,8 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) * Find the first entry in the lower region that could abut a big-enough * range. */ - curr = RB_ROOT(&a->domain->rb_root); + domain = a->domain; + curr = RB_ROOT(&domain->rb_root); first = NULL; while (curr != NULL && curr->free_down >= min_free) { first = curr; @@ -447,16 +434,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) curr = iommu_gas_next(curr, min_free)) { if ((first = RB_LEFT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, first->last, curr->start, - 0, addr)) + 0, addr)) { + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } if (curr->end >= addr) { /* All remaining ranges >= addr */ break; } if ((first = RB_RIGHT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, curr->end, first->first, - 0, addr)) + 0, addr)) { + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } } /* @@ -481,17 +474,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) * Walk the remaining big-enough ranges until one satisfies alignment * requirements. */ - domain = a->domain; for (curr = first; curr != NULL; curr = iommu_gas_next(curr, min_free)) { if ((first = RB_LEFT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, first->last, curr->start, - addr + 1, domain->end)) + addr + 1, domain->end)) { + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } if ((first = RB_RIGHT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, curr->end, first->first, - addr + 1, domain->end)) + addr + 1, domain->end)) { + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } } return (ENOMEM); @@ -502,7 +500,6 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr u_int flags) { struct iommu_map_entry *next, *prev; - bool found __diagused; IOMMU_DOMAIN_ASSERT_LOCKED(domain); @@ -550,14 +547,13 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr iommu_gas_rb_remove(domain, prev); prev = NULL; } + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, next, entry); if (next->start < entry->end) { iommu_gas_rb_remove(domain, next); next = NULL; } - found = iommu_gas_rb_insert(domain, entry); - KASSERT(found, ("found RMRR dup %p start %jx end %jx", - domain, (uintmax_t)entry->start, (uintmax_t)entry->end)); if ((flags & IOMMU_MF_RMRR) != 0) entry->flags = IOMMU_MAP_ENTRY_RMRR; @@ -647,7 +643,8 @@ iommu_gas_remove_clip_left(struct iommu_domain *domain, iommu_gaddr_t start, *res = *entry; res->start = entry->end = start; RB_UPDATE_AUGMENT(entry, rb_entry); - iommu_gas_rb_insert(domain, res); + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, entry, res); return (res); } @@ -662,7 +659,8 @@ iommu_gas_remove_clip_right(struct iommu_domain *domain, *r = *entry; r->end = entry->start = end; RB_UPDATE_AUGMENT(entry, rb_entry); - iommu_gas_rb_insert(domain, r); + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, entry, r); return (true); } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 6743a8eb104c..1206e5280a85 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -414,12 +414,15 @@ struct { \ RB_PROTOTYPE_RANK(name, type, attr) \ RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ + RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \ RB_PROTOTYPE_INSERT(name, type, attr); \ RB_PROTOTYPE_REMOVE(name, type, attr); \ RB_PROTOTYPE_FIND(name, type, attr); \ RB_PROTOTYPE_NFIND(name, type, attr); \ RB_PROTOTYPE_NEXT(name, type, attr); \ + RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \ RB_PROTOTYPE_PREV(name, type, attr); \ + RB_PROTOTYPE_INSERT_PREV(name, type, attr); \ RB_PROTOTYPE_MINMAX(name, type, attr); \ RB_PROTOTYPE_REINSERT(name, type, attr); #ifdef _RB_DIAGNOSTIC @@ -436,6 +439,9 @@ struct { \ struct type *, struct type *) #define RB_PROTOTYPE_REMOVE(name, type, attr) \ attr struct type *name##_RB_REMOVE(struct name *, struct type *) +#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \ + attr struct type *name##_RB_INSERT_FINISH(struct name *, \ + struct type *, struct type **, struct type *) #define RB_PROTOTYPE_INSERT(name, type, attr) \ attr struct type *name##_RB_INSERT(struct name *, struct type *) #define RB_PROTOTYPE_FIND(name, type, attr) \ @@ -444,8 +450,14 @@ struct { \ attr struct type *name##_RB_NFIND(struct name *, struct type *) #define RB_PROTOTYPE_NEXT(name, type, attr) \ attr struct type *name##_RB_NEXT(struct type *) +#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \ + attr struct type *name##_RB_INSERT_NEXT(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_PREV(name, type, attr) \ attr struct type *name##_RB_PREV(struct type *) +#define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \ + attr struct type *name##_RB_INSERT_PREV(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_MINMAX(name, type, attr) \ attr struct type *name##_RB_MINMAX(struct name *, int) #define RB_PROTOTYPE_REINSERT(name, type, attr) \ @@ -462,12 +474,15 @@ struct { \ RB_GENERATE_RANK(name, type, field, attr) \ RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ + RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ RB_GENERATE_INSERT(name, type, field, cmp, attr) \ RB_GENERATE_REMOVE(name, type, field, attr) \ RB_GENERATE_FIND(name, type, field, cmp, attr) \ RB_GENERATE_NFIND(name, type, field, cmp, attr) \ RB_GENERATE_NEXT(name, type, field, attr) \ + RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ RB_GENERATE_PREV(name, type, field, attr) \ + RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ RB_GENERATE_MINMAX(name, type, field, attr) \ RB_GENERATE_REINSERT(name, type, field, cmp, attr) @@ -556,7 +571,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ * other edge lengths based on the downward \ * edges from 'child'. \ * \ - * par par \ + * par par \ * / \ / \ \ * elm z / z \ * / \ child \ @@ -587,7 +602,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ * 'parent' a child of 'child', then make both edges \ * of 'child' short to rebalance. \ * \ - * par child \ + * par child \ * / \ / \ \ * / z x par \ * child / \ \ @@ -800,6 +815,29 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ return (out); \ } +#define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ +/* Inserts a node into the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \ + struct type **pptr, struct type *elm) \ +{ \ + struct type *tmp = NULL; \ + \ + RB_SET(elm, parent, field); \ + *pptr = elm; \ + if (parent != NULL) \ + tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ + _RB_AUGMENT_WALK(elm, tmp, field); \ + if (tmp != NULL) \ + /* \ + * An element rotated into the search path has a \ + * changed subtree, so update augmentation for it if \ + * AUGMENT_WALK didn't. \ + */ \ + (void)RB_AUGMENT_CHECK(tmp); \ + return (NULL); \ +} + #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ /* Inserts a node into the RB tree */ \ attr struct type * \ @@ -819,19 +857,7 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ else \ return (parent); \ } \ - RB_SET(elm, parent, field); \ - *tmpp = elm; \ - if (parent != NULL) \ - tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ - _RB_AUGMENT_WALK(elm, tmp, field); \ - if (tmp != NULL) \ - /* \ - * An element rotated into the search path has a \ - * changed subtree, so update augmentation for it if \ - * AUGMENT_WALK didn't. \ - */ \ - (void)RB_AUGMENT_CHECK(tmp); \ - return (NULL); \ + return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \ } #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ @@ -893,6 +919,33 @@ name##_RB_NEXT(struct type *elm) \ return (elm); \ } +#if defined(_KERNEL) && defined(DIAGNOSTIC) +#define _RB_ORDER_CHECK(lo, hi) do { \ + KASSERT(cmp(lo, hi) < 0, "out of order insertion"); \ +} while (0) +#else +#define _RB_ORDER_CHECK(elm, next) do {} while (0) +#endif + +#define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ +/* Inserts a node into the next position in the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_NEXT(struct name *head, \ + struct type *elm, struct type *next) \ +{ \ + struct type *tmp; \ + struct type **tmpp = &RB_RIGHT(elm, field); \ + \ + _RB_ORDER_CHECK(elm, next); \ + if (name##_RB_NEXT(elm) != NULL) \ + _RB_ORDER_CHECK(next, name##_RB_NEXT(elm)); \ + while ((tmp = *tmpp) != NULL) { \ + elm = tmp; \ + tmpp = &RB_LEFT(elm, field); \ + } \ + return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \ +} + #define RB_GENERATE_PREV(name, type, field, attr) \ /* ARGSUSED */ \ attr struct type * \ @@ -911,6 +964,25 @@ name##_RB_PREV(struct type *elm) \ return (elm); \ } +#define RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ +/* Inserts a node into the prev position in the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_PREV(struct name *head, \ + struct type *elm, struct type *prev) \ +{ \ + struct type *tmp; \ + struct type **tmpp = &RB_LEFT(elm, field); \ + \ + _RB_ORDER_CHECK(prev, elm); \ + if (name##_RB_PREV(elm) != NULL) \ + _RB_ORDER_CHECK(name##_RB_PREV(elm), prev); \ + while ((tmp = *tmpp) != NULL) { \ + elm = tmp; \ + tmpp = &RB_RIGHT(elm, field); \ + } \ + return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \ +} + #define RB_GENERATE_MINMAX(name, type, field, attr) \ attr struct type * \ name##_RB_MINMAX(struct name *head, int val) \ @@ -947,6 +1019,8 @@ name##_RB_REINSERT(struct name *head, struct type *elm) \ #define RB_INF 1 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) +#define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z) +#define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z) #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) #define RB_FIND(name, x, y) name##_RB_FIND(x, y) #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)