branches: 1.4.34;
Mark linted

branches: 1.3.2;
ANSIfy

For all files under src/common, as well as related man pages under
src/lib/libc, or related headers under src/sys/sys: change u_intNN_t to
uintNN_t.

branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.

branches: 1.3.44;
ANSIfy

For all files under src/common, as well as related man pages under
src/lib/libc, or related headers under src/sys/sys: change u_intNN_t to
uintNN_t.

branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.

branches: 1.3.48;
ansify function definitions

branches: 1.2.12;
For all files under src/common, as well as related man pages under
src/lib/libc, or related headers under src/sys/sys: change u_intNN_t to
uintNN_t.

branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.

s/abadoned/abandoned/ and s/fobidden/forbidden/ in comments.

s/identiy/identity/ and s/chang /change/ in comments.

branches: 1.13.2;
move local decls to headers

libc/ptree: remove CONSTCOND comments

Since 2021-01-31, lint does not need them anymore.

fix various typos in comment, documentation and log messages.

branches: 1.10.32;
Add a ptree_mask_node_p to determine if an item is a mask node, and what
its non-mask length is.

branches: 1.9.2;
ptree_find_filtered_node: make key argument const.

Add code to protect the ptree from multiple insertions of the same node.

Don't bother testing 0 length keys since they can only have one possible value.

ptree: add context argument. OK matt@

branches: 1.5.6; 1.5.8;
fix comment typos.

branches: 1.4.2;
fix -Wsign-compare issues

fix build in _STANDALONE case

Make lint happy (stupid lint).

Add new ptree (Patricia / RADIX tree) implementation to NetBSD.

radixtree: allocate memory with KM_NOSLEEP to prevent pagedaemon hangs

Revert the part of rev 1.32 (reapplying "Do away with separate pool_cache
for some kernel objects") that changed the memory allocation for radixtree
nodes from PR_NOWAIT to KM_SLEEP as part of changing from a pool to kmem.
uvm_pageinsert_tree() calls into the radixtree code while holding
the object's vmobjlock, but that same lock is taken by the pagedaemon
in the process of reclaiming pages, and if the pagedaemon happens to
choose the same object to reclaim from that uvm_pageinsert_tree()
is being called on, then these two threads will deadlock.
The previous code already handled memory allocation failures
in uvm_pageinsert_tree() so we can simply change it back to nosleep.

Fixes a hang reported by simonb@, and the fix was also tested by him.

kmem_free() -> kmem_intr_free(). Spotted by rin@.

Repply this change with a couple of bugs fixed:

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one of my
test systems this makes for a small (~1%) but repeatable reduction in system
time during builds presumably because it decreases the kernel's cache /
memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

Back out recent change to replace pool_cache with then general allocator.
Will return to this when I have time again.

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one of my
test systems this makes for a small (~1%) but repeatable reduction in system
time during builds presumably because it decreases the kernel's cache /
memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

fix few typos in comments and log messages.

fix various typos in comment, documentation and log messages.

Remove extra semicolon.

Match the naming convention in the file.

PR kern/54979 (radixtree might misbehave if ENOMEM)

- radix_tree_insert_node(): if the insert failed due to ENOMEM, roll back
any updates made to the tree.

- radix_tree_grow(): either succeed or fail, never make partial adjustments
to the tree.

- radix_tree_await_memory(): allocate & free the maximum possible number of
nodes required by any insertion.

Rename radix_tree_node_clean_p() to radix_tree_node_sum() and have it return
the computed sum. Use to replace any_children_tagmask(). Simpler & faster.

gang_lookup_scan(): if a dense scan and the first sibling doesn't match,
the scan is finished.

Add a radix_tree_await_memory(), for kernel use.

initialize radix_tree_node_cache with PR_LARGECACHE

this increases the cache groups from 15 to 63 items in order
to reduce traffic between pool cache layers
this is the same as for other highly frequented pool caches as the pvpool and anonpool

branches: 1.20.2;
Fix warning that appears when compiling in kernel.

Delete the counter from "struct radix_tree_node", and in the one place we
need a non-zero check, substitute with a deterministic bitwise OR of all
values in the node. The structure then becomes cache line aligned.

For each node we now need only touch 2 cache lines instead of 3, which makes
all the operations faster (measured), amortises the cost of not having a
counter, and will avoid intra-pool-page false sharing on MP.

Merge radixtree changes from yamt-pagecache.

branches: 1.17.2; 1.17.44;
comments

add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.

- add functions to scan the tree in the reverse order
(i wonder if it's the longest function name in the tree)
- assertions
- comments
- fix and update unittest

unwarp a short line

constify

fix "get_tag" result of unittest

make the output of unittest a little machine-readable

int -> unsigned int where appropriate

add a function to check if a tree is empty.

include string.h for memset

radix_tree_clear_tag:
- fix a bug which errornously clears tags on intermediate nodes.
- add comments.

radixtree: assertions

radixtree: comments

radixtree: comments

fix _STANDALONE build

- fix _STANDALONE build.
- use __CTASSERT instead of CTASSERT. enable it for userland.
- __read_mostly.

branches: 1.1.2;
an implementation of radix tree. the idea from linux.

rbtree: Rename rb.c to rbtree.c to match it's header rbtree.h

While here rename RBTEST to RBLOCAL to give a better meaning as we
want to include the local rbtest.h rather than the system one.

Also allow to compile outside of NetBSD source tree by guarding some
things we would otherwise expect to be defined.

fix typos in word "successfully", mainly s/succesfully/successfully/.

toolify

PR/54182: Cross-building on Linux fails in rb.c

rbtree: Add a define to mark function arguments as unused for non debug

This allows rbtree to be used outside of NetBSD without any compile
warnings and removes the need for the lint comment.

branches: 1.13.16;
Remove enclosing parens on return.

Fix failure case in rb_tree_find_node_leq/geq.

Return NULL, not `NULL - offset'.

XXX pullup to netbsd-5, netbsd-6, netbsd-7

branches: 1.11.4; 1.11.22;
various build fixes for gcc 4.5. from chuq. XXX i'm not sure all of
these work properly wtf pointer aliasing, but there are no casts at
least...

the lib/libpuffs/puffs_priv.h is definately a real bug fix.

from chuq.

branches: 1.10.2;
Add RCSIDs

Provide proper namespace protection for rbtree(3) because it is now
used by "libc" internally.

Rename rb.h to rbtree.h, as it is more appropriate (c.f. ptree.h). Also
helps find code that hasn't been updated to use the new rbtree API.

Fixes/improvements to RB-tree implementation:
1. Fix inverted node order, so that negative value from comparison operator
would represent lower (left) node, and positive - higher (right) node.
2. Add an argument (i.e. "context"), passed to comparison operators.
3. Change rb_tree_insert_node() to return a node - either inserted one or
already existing one.
4. Amend the interface to manipulate the actual object, instead of the
rb_node (in a similar way as Patricia-tree interface does).
5. Update all RB-tree users accordingly.

XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up..

1-3 address the PR/43488 by Jeremy Huddleston.

Passes RB-tree regression tests.
Reviewed by: matt@, christos@

Fix rb_tree_iterate to get the min/max element of the tree for the
RBSMALL case.

Fix warnings for -DRBSMALL

don't include sys/cdefs.h twice.

branches: 1.3.2; 1.3.8;
Changes to make lint STFU.

Change tree op members/typedefs to rbto_compare_* from rb_compare_*

Move rb.c from sys/lib/libkern to common so it can be in both libc and libkern.

rbtree: tweak headers a little for portability

rbtree: Rename rb.c to rbtree.c to match it's header rbtree.h

While here rename RBTEST to RBLOCAL to give a better meaning as we
want to include the local rbtest.h rather than the system one.

Also allow to compile outside of NetBSD source tree by guarding some
things we would otherwise expect to be defined.

fix few typos in comments and log message.

branches: 1.11.46;
fix _STANDALONE build

fix _STANDALONE build

branches: 1.9.2;
fix a comment

rpst_iterate_next: remove an unnecessary assignment.

rpst_iterate_first: fix a bug which causes unnecessary scan.

sprinkle some inline

maintain parent node pointers to speed up search and node removal.

add comments.

rpst_insert_node1: fix an inverted condition.

- fix various bugs in the iteration code.
- add assertions.
- unittest: more tests. verify query results by comparing with linear search.

radix priority search tree.