Home | History | Annotate | only in /src/common/lib/libc/gen
History log of /src/common/lib/libc/gen
RevisionDateAuthorComments
 1.4 17-Mar-2012  martin branches: 1.4.34;
Mark linted
 1.3 04-Jul-2011  joerg branches: 1.3.2;
ANSIfy
 1.2 16-Feb-2008  apb 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.
 1.1 20-Dec-2005  christos branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.
 1.1.18.1 23-Mar-2008  matt sync with HEAD
 1.1.6.1 18-Nov-2008  snj Pull up following revision(s) (requested by tsutsui in ticket #1224):
common/lib/libc/gen/bswap64.c: revision 1.2
common/lib/libprop/prop_data.c: revision 1.10
common/lib/libc/inet/inet_addr.c: revision 1.2
common/lib/libc/hash/rmd160/rmd160.c: revision 1.4
common/lib/libc/gen/bswap32.c: revision 1.2
common/lib/libc/gen/bswap16.c: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_4.S: revision 1.3
common/lib/libc/arch/sh3/string/memset.S: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_2.S: revision 1.3
common/lib/libc/md/md5c.c: revision 1.3
common/lib/libc/hash/sha1/sha1.c: revision 1.3
common/lib/libc/md/md4c.c: revision 1.3
sys/sys/rmd160.h: revision 1.2
sys/sys/sha2.h: revision 1.2
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.
 1.3.2.1 17-Apr-2012  yamt sync with head
 1.4.34.2 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.4.34.1 21-Apr-2020  martin Sync with HEAD
 1.3 04-Jul-2011  joerg branches: 1.3.44;
ANSIfy
 1.2 16-Feb-2008  apb 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.
 1.1 20-Dec-2005  christos branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.
 1.1.18.1 23-Mar-2008  matt sync with HEAD
 1.1.6.1 18-Nov-2008  snj Pull up following revision(s) (requested by tsutsui in ticket #1224):
common/lib/libc/gen/bswap64.c: revision 1.2
common/lib/libprop/prop_data.c: revision 1.10
common/lib/libc/inet/inet_addr.c: revision 1.2
common/lib/libc/hash/rmd160/rmd160.c: revision 1.4
common/lib/libc/gen/bswap32.c: revision 1.2
common/lib/libc/gen/bswap16.c: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_4.S: revision 1.3
common/lib/libc/arch/sh3/string/memset.S: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_2.S: revision 1.3
common/lib/libc/md/md5c.c: revision 1.3
common/lib/libc/hash/sha1/sha1.c: revision 1.3
common/lib/libc/md/md4c.c: revision 1.3
sys/sys/rmd160.h: revision 1.2
sys/sys/sha2.h: revision 1.2
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.
 1.3.44.2 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.3.44.1 21-Apr-2020  martin Sync with HEAD
 1.3 16-Mar-2009  cegger branches: 1.3.48;
ansify function definitions
 1.2 16-Feb-2008  apb 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.
 1.1 20-Dec-2005  christos branches: 1.1.6; 1.1.18;
Merge libkern + libc common files. As requested by core.
 1.1.18.1 23-Mar-2008  matt sync with HEAD
 1.1.6.1 18-Nov-2008  snj Pull up following revision(s) (requested by tsutsui in ticket #1224):
common/lib/libc/gen/bswap64.c: revision 1.2
common/lib/libprop/prop_data.c: revision 1.10
common/lib/libc/inet/inet_addr.c: revision 1.2
common/lib/libc/hash/rmd160/rmd160.c: revision 1.4
common/lib/libc/gen/bswap32.c: revision 1.2
common/lib/libc/gen/bswap16.c: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_4.S: revision 1.3
common/lib/libc/arch/sh3/string/memset.S: revision 1.2
common/lib/libc/arch/alpha/gen/byte_swap_2.S: revision 1.3
common/lib/libc/md/md5c.c: revision 1.3
common/lib/libc/hash/sha1/sha1.c: revision 1.3
common/lib/libc/md/md4c.c: revision 1.3
sys/sys/rmd160.h: revision 1.2
sys/sys/sha2.h: revision 1.2
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.
 1.2.12.1 13-May-2009  jym Sync with HEAD.

Commit is split, to avoid a "too many arguments" protocol error.
 1.3.48.2 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.3.48.1 21-Apr-2020  martin Sync with HEAD
 1.15 25-Apr-2025  andvar s/abadoned/abandoned/ and s/fobidden/forbidden/ in comments.
 1.14 25-Apr-2025  andvar s/identiy/identity/ and s/chang /change/ in comments.
 1.13 20-Jan-2024  christos branches: 1.13.2;
move local decls to headers
 1.12 26-May-2022  rillig libc/ptree: remove CONSTCOND comments

Since 2021-01-31, lint does not need them anymore.
 1.11 24-May-2022  andvar fix various typos in comment, documentation and log messages.
 1.10 06-Oct-2012  matt 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.
 1.9 15-Jul-2012  rmind branches: 1.9.2;
ptree_find_filtered_node: make key argument const.
 1.8 14-Jul-2012  matt Add code to protect the ptree from multiple insertions of the same node.
 1.7 13-Jul-2012  matt Don't bother testing 0 length keys since they can only have one possible value.
 1.6 11-Jul-2012  rmind ptree: add context argument. OK matt@
 1.5 07-Jun-2009  yamt branches: 1.5.6; 1.5.8;
fix comment typos.
 1.4 18-Jan-2009  lukem branches: 1.4.2;
fix -Wsign-compare issues
 1.3 21-Nov-2008  jnemeth fix build in _STANDALONE case
 1.2 21-Nov-2008  matt Make lint happy (stupid lint).
 1.1 20-Nov-2008  matt Add new ptree (Patricia / RADIX tree) implementation to NetBSD.
 1.4.2.1 23-Jul-2009  jym Sync with HEAD.
 1.5.8.3 24-Nov-2012  jdc Pull up revisions:
src/common/lib/libc/gen/ptree.c revision 1.10
src/sys/sys/ptree.h revision 1.8
(requested by rmind in ticket #717).

Add a ptree_mask_node_p to determine if an item is a mask node, and what
its non-mask length is.
 1.5.8.2 16-Jul-2012  riz Pull up following revision(s) (requested by rmind in ticket #420):
common/lib/libc/gen/ptree.c: revision 1.7
common/lib/libc/gen/ptree.c: revision 1.8
common/lib/libc/gen/ptree.c: revision 1.9
sys/sys/ptree.h: revision 1.7
Don't bother testing 0 length keys since they can only have one possible value.
Add code to protect the ptree from multiple insertions of the same node.
ptree_find_filtered_node: make key argument const.
 1.5.8.1 12-Jul-2012  riz Pull up following revision(s) (requested by rmind in ticket #413):
common/lib/libc/gen/ptree.c: revision 1.6
sys/sys/ptree.h: revision 1.6
ptree: add context argument. OK matt@
 1.5.6.1 30-Oct-2012  yamt sync with head
 1.9.2.1 20-Nov-2012  tls Resync to 2012-11-19 00:00:00 UTC
 1.10.32.2 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.10.32.1 21-Apr-2020  martin Sync with HEAD
 1.13.2.1 02-Aug-2025  perseant Sync with HEAD
 1.34 04-May-2024  chs 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.
 1.33 23-Sep-2023  ad kmem_free() -> kmem_intr_free(). Spotted by rin@.
 1.32 23-Sep-2023  ad 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.
 1.31 12-Sep-2023  ad Back out recent change to replace pool_cache with then general allocator.
Will return to this when I have time again.
 1.30 10-Sep-2023  ad - 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.
 1.29 06-Mar-2023  andvar fix few typos in comments and log messages.
 1.28 24-May-2022  andvar fix various typos in comment, documentation and log messages.
 1.27 14-May-2020  msaitoh Remove extra semicolon.
 1.26 11-Apr-2020  ad Match the naming convention in the file.
 1.25 10-Apr-2020  ad 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.
 1.24 10-Apr-2020  ad 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.
 1.23 28-Jan-2020  ad gang_lookup_scan(): if a dense scan and the first sibling doesn't match,
the scan is finished.
 1.22 28-Jan-2020  ad Add a radix_tree_await_memory(), for kernel use.
 1.21 12-Jan-2020  para 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
 1.20 05-Dec-2019  ad branches: 1.20.2;
Fix warning that appears when compiling in kernel.
 1.19 05-Dec-2019  ad 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.
 1.18 05-Dec-2019  ad Merge radixtree changes from yamt-pagecache.
 1.17 02-Nov-2011  yamt branches: 1.17.2; 1.17.44;
comments
 1.16 25-Oct-2011  yamt add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.
 1.15 14-Oct-2011  yamt - 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
 1.14 14-Oct-2011  yamt unwarp a short line
 1.13 14-Oct-2011  yamt constify
 1.12 14-Oct-2011  yamt fix "get_tag" result of unittest
 1.11 14-Oct-2011  yamt make the output of unittest a little machine-readable
 1.10 14-Oct-2011  yamt int -> unsigned int where appropriate
 1.9 14-Oct-2011  yamt add a function to check if a tree is empty.
 1.8 14-Oct-2011  yamt include string.h for memset
 1.7 19-May-2011  yamt radix_tree_clear_tag:
- fix a bug which errornously clears tags on intermediate nodes.
- add comments.
 1.6 19-May-2011  yamt radixtree: assertions
 1.5 19-May-2011  yamt radixtree: comments
 1.4 19-May-2011  yamt radixtree: comments
 1.3 26-Apr-2011  yamt fix _STANDALONE build
 1.2 14-Apr-2011  yamt - fix _STANDALONE build.
- use __CTASSERT instead of CTASSERT. enable it for userland.
- __read_mostly.
 1.1 22-Feb-2011  yamt branches: 1.1.2;
an implementation of radix tree. the idea from linux.
 1.1.2.2 05-Mar-2011  bouyer Sync with HEAD
 1.1.2.1 22-Feb-2011  bouyer file radixtree.c was added on branch bouyer-quota2 on 2011-03-05 15:08:32 +0000
 1.17.44.4 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.17.44.3 21-Apr-2020  martin Sync with HEAD
 1.17.44.2 13-Apr-2020  martin Mostly merge changes from HEAD upto 20200411
 1.17.44.1 08-Apr-2020  martin Merge changes from current as of 20200406
 1.17.2.6 22-May-2014  yamt suppress gcc warnings
 1.17.2.5 25-Mar-2014  yamt comments. some ascii arts to explain memory consumption.
 1.17.2.4 01-Aug-2012  yamt make tag-variants of radix tree functions take and return a mask of tags
rather than tag ids so that they can deal with multiple tags at once.
 1.17.2.3 13-Jun-2012  yamt comment
 1.17.2.2 17-Feb-2012  yamt comments
 1.17.2.1 25-Nov-2011  yamt radix_tree_gang_lookup_node and its variants: add a option to stop on a hole.
 1.20.2.1 29-Feb-2020  ad Sync with head.
 1.17 22-Oct-2025  roy 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.
 1.16 16-Sep-2021  andvar fix typos in word "successfully", mainly s/succesfully/successfully/.
 1.15 09-May-2019  skrll toolify

PR/54182: Cross-building on Linux fails in rb.c
 1.14 08-Mar-2019  roy 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.
 1.13 22-Aug-2014  matt branches: 1.13.16;
Remove enclosing parens on return.
 1.12 22-Aug-2014  riastradh Fix failure case in rb_tree_find_node_leq/geq.

Return NULL, not `NULL - offset'.

XXX pullup to netbsd-5, netbsd-6, netbsd-7
 1.11 20-Jun-2011  mrg 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.
 1.10 12-Apr-2011  matt branches: 1.10.2;
Add RCSIDs
 1.9 17-Nov-2010  tron Provide proper namespace protection for rbtree(3) because it is now
used by "libc" internally.
 1.8 25-Sep-2010  matt 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.
 1.7 24-Sep-2010  rmind 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@
 1.6 30-Apr-2010  joerg Fix rb_tree_iterate to get the min/max element of the tree for the
RBSMALL case.
 1.5 28-Apr-2010  joerg Fix warnings for -DRBSMALL
 1.4 19-May-2009  yamt don't include sys/cdefs.h twice.
 1.3 30-Jun-2008  matt branches: 1.3.2; 1.3.8;
Changes to make lint STFU.
 1.2 30-Jun-2008  matt Change tree op members/typedefs to rbto_compare_* from rb_compare_*
 1.1 30-Jun-2008  matt Move rb.c from sys/lib/libkern to common so it can be in both libc and libkern.
 1.3.8.1 23-Jul-2009  jym Sync with HEAD.
 1.3.2.2 18-Sep-2008  wrstuden Sync with wrstuden-revivesa-base-2.
 1.3.2.1 30-Jun-2008  wrstuden file rb.c was added on branch wrstuden-revivesa on 2008-09-18 04:54:18 +0000
 1.10.2.1 23-Jun-2011  cherry Catchup with rmind-uvmplock merge.
 1.11.22.1 29-Aug-2014  martin Pull up following revision(s) (requested by riastradh):
common/lib/libc/gen/rb.c: revision 1.12
common/lib/libc/gen/rb.c: revision 1.13
Fix failure case in rb_tree_find_node_leq/geq.
Return NULL, not `NULL - offset'.
XXX pullup to netbsd-5, netbsd-6, netbsd-7
Remove enclosing parens on return.
 1.11.4.1 27-Oct-2014  msaitoh Pull up following revision(s) (requested by riastradh in ticket #1142):
common/lib/libc/gen/rb.c: revision 1.12
common/lib/libc/gen/rb.c: revision 1.13
Fix failure case in rb_tree_find_node_leq/geq.
Return NULL, not `NULL - offset'.
XXX pullup to netbsd-5, netbsd-6, netbsd-7
Remove enclosing parens on return.
 1.13.16.3 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.13.16.2 21-Apr-2020  martin Sync with HEAD
 1.13.16.1 10-Jun-2019  christos Sync with HEAD
 1.2 29-Oct-2025  roy rbtree: tweak headers a little for portability
 1.1 22-Oct-2025  roy 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.
 1.12 14-Nov-2021  andvar fix few typos in comments and log message.
 1.11 26-Apr-2011  yamt branches: 1.11.46;
fix _STANDALONE build
 1.10 14-Apr-2011  yamt fix _STANDALONE build
 1.9 26-May-2009  yamt branches: 1.9.2;
fix a comment
 1.8 26-May-2009  yamt rpst_iterate_next: remove an unnecessary assignment.
 1.7 26-May-2009  yamt rpst_iterate_first: fix a bug which causes unnecessary scan.
 1.6 26-May-2009  yamt sprinkle some inline
 1.5 25-May-2009  yamt maintain parent node pointers to speed up search and node removal.
 1.4 25-May-2009  yamt add comments.
 1.3 22-May-2009  yamt rpst_insert_node1: fix an inverted condition.
 1.2 20-May-2009  yamt - fix various bugs in the iteration code.
- add assertions.
- unittest: more tests. verify query results by comparing with linear search.
 1.1 19-May-2009  yamt radix priority search tree.
 1.9.2.2 23-Jul-2009  jym Sync with HEAD.
 1.9.2.1 26-May-2009  jym file rpst.c was added on branch jym-xensuspend on 2009-07-23 23:31:34 +0000
 1.11.46.2 21-Apr-2020  martin Ooops, restore accidently removed files from merge mishap
 1.11.46.1 21-Apr-2020  martin Sync with HEAD

RSS XML Feed