The NetBSD Project

CVS log for src/common/lib/libc/gen/radixtree.c

[BACK] Up to [cvs.NetBSD.org] / src / common / lib / libc / gen

Request diff between arbitrary revisions


Default branch: MAIN


Revision 1.33 / (download) - annotate - [select for diffs], Sat Sep 23 19:17:38 2023 UTC (6 months, 3 weeks ago) by ad
Branch: MAIN
CVS Tags: thorpej-ifq-base, thorpej-ifq, thorpej-altq-separation-base, thorpej-altq-separation, HEAD
Changes since 1.32: +4 -4 lines
Diff to previous 1.32 (colored)

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

Revision 1.32 / (download) - annotate - [select for diffs], Sat Sep 23 18:21:11 2023 UTC (6 months, 3 weeks ago) by ad
Branch: MAIN
Changes since 1.31: +13 -29 lines
Diff to previous 1.31 (colored)

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.

Revision 1.31 / (download) - annotate - [select for diffs], Tue Sep 12 16:17:21 2023 UTC (7 months ago) by ad
Branch: MAIN
Changes since 1.30: +29 -12 lines
Diff to previous 1.30 (colored)

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

Revision 1.30 / (download) - annotate - [select for diffs], Sun Sep 10 14:45:52 2023 UTC (7 months ago) by ad
Branch: MAIN
Changes since 1.29: +12 -29 lines
Diff to previous 1.29 (colored)

- 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.

Revision 1.29 / (download) - annotate - [select for diffs], Mon Mar 6 21:39:06 2023 UTC (13 months, 1 week ago) by andvar
Branch: MAIN
Changes since 1.28: +6 -6 lines
Diff to previous 1.28 (colored)

fix few typos in comments and log messages.

Revision 1.28 / (download) - annotate - [select for diffs], Tue May 24 20:50:17 2022 UTC (22 months, 3 weeks ago) by andvar
Branch: MAIN
CVS Tags: netbsd-10-base, netbsd-10-0-RELEASE, netbsd-10-0-RC6, netbsd-10-0-RC5, netbsd-10-0-RC4, netbsd-10-0-RC3, netbsd-10-0-RC2, netbsd-10-0-RC1, netbsd-10
Changes since 1.27: +4 -4 lines
Diff to previous 1.27 (colored)

fix various typos in comment, documentation and log messages.

Revision 1.27 / (download) - annotate - [select for diffs], Thu May 14 08:34:19 2020 UTC (3 years, 11 months ago) by msaitoh
Branch: MAIN
CVS Tags: cjep_sun2x-base1, cjep_sun2x-base, cjep_sun2x, cjep_staticlib_x-base1, cjep_staticlib_x-base, cjep_staticlib_x
Changes since 1.26: +5 -5 lines
Diff to previous 1.26 (colored)

Remove extra semicolon.

Revision 1.17.44.4 / (download) - annotate - [select for diffs], Tue Apr 21 19:37:49 2020 UTC (3 years, 11 months ago) by martin
Branch: phil-wifi
Changes since 1.17.44.3: +3 -3 lines
Diff to previous 1.17.44.3 (colored) to branchpoint 1.17 (colored) next main 1.18 (colored)

Ooops, restore accidently removed files from merge mishap

Revision 1.17.44.3, Tue Apr 21 18:41:22 2020 UTC (3 years, 11 months ago) by martin
Branch: phil-wifi
Changes since 1.17.44.2: +3 -3 lines
FILE REMOVED

Sync with HEAD

Revision 1.17.44.2 / (download) - annotate - [select for diffs], Mon Apr 13 07:45:07 2020 UTC (4 years ago) by martin
Branch: phil-wifi
Changes since 1.17.44.1: +103 -54 lines
Diff to previous 1.17.44.1 (colored) to branchpoint 1.17 (colored)

Mostly merge changes from HEAD upto 20200411

Revision 1.26 / (download) - annotate - [select for diffs], Sat Apr 11 01:46:47 2020 UTC (4 years ago) by ad
Branch: MAIN
CVS Tags: phil-wifi-20200421, phil-wifi-20200411, bouyer-xenpvh-base2, bouyer-xenpvh-base1, bouyer-xenpvh-base, bouyer-xenpvh
Changes since 1.25: +13 -13 lines
Diff to previous 1.25 (colored)

Match the naming convention in the file.

Revision 1.25 / (download) - annotate - [select for diffs], Fri Apr 10 23:43:05 2020 UTC (4 years ago) by ad
Branch: MAIN
Changes since 1.24: +85 -24 lines
Diff to previous 1.24 (colored)

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.

Revision 1.24 / (download) - annotate - [select for diffs], Fri Apr 10 21:56:41 2020 UTC (4 years ago) by ad
Branch: MAIN
Changes since 1.23: +26 -38 lines
Diff to previous 1.23 (colored)

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.

Revision 1.17.44.1 / (download) - annotate - [select for diffs], Wed Apr 8 14:03:05 2020 UTC (4 years ago) by martin
Branch: phil-wifi
Changes since 1.17: +477 -226 lines
Diff to previous 1.17 (colored)

Merge changes from current as of 20200406

Revision 1.20.2.1 / (download) - annotate - [select for diffs], Sat Feb 29 20:17:43 2020 UTC (4 years, 1 month ago) by ad
Branch: ad-namecache
Changes since 1.20: +23 -24 lines
Diff to previous 1.20 (colored) next main 1.21 (colored)

Sync with head.

Revision 1.23 / (download) - annotate - [select for diffs], Tue Jan 28 22:20:45 2020 UTC (4 years, 2 months ago) by ad
Branch: MAIN
CVS Tags: phil-wifi-20200406, is-mlppp-base, is-mlppp, ad-namecache-base3
Changes since 1.22: +5 -23 lines
Diff to previous 1.22 (colored)

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

Revision 1.22 / (download) - annotate - [select for diffs], Tue Jan 28 16:33:34 2020 UTC (4 years, 2 months ago) by ad
Branch: MAIN
Changes since 1.21: +20 -3 lines
Diff to previous 1.21 (colored)

Add a radix_tree_await_memory(), for kernel use.

Revision 1.21 / (download) - annotate - [select for diffs], Sun Jan 12 20:00:41 2020 UTC (4 years, 3 months ago) by para
Branch: MAIN
Changes since 1.20: +4 -4 lines
Diff to previous 1.20 (colored)

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

Revision 1.20 / (download) - annotate - [select for diffs], Thu Dec 5 19:03:39 2019 UTC (4 years, 4 months ago) by ad
Branch: MAIN
CVS Tags: ad-namecache-base
Branch point for: ad-namecache
Changes since 1.19: +5 -3 lines
Diff to previous 1.19 (colored)

Fix warning that appears when compiling in kernel.

Revision 1.19 / (download) - annotate - [select for diffs], Thu Dec 5 18:50:41 2019 UTC (4 years, 4 months ago) by ad
Branch: MAIN
Changes since 1.18: +66 -29 lines
Diff to previous 1.18 (colored)

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.

Revision 1.18 / (download) - annotate - [select for diffs], Thu Dec 5 18:32:25 2019 UTC (4 years, 4 months ago) by ad
Branch: MAIN
Changes since 1.17: +412 -199 lines
Diff to previous 1.17 (colored)

Merge radixtree changes from yamt-pagecache.

Revision 1.17.2.6 / (download) - annotate - [select for diffs], Thu May 22 19:09:50 2014 UTC (9 years, 10 months ago) by yamt
Branch: yamt-pagecache
Changes since 1.17.2.5: +13 -7 lines
Diff to previous 1.17.2.5 (colored) to branchpoint 1.17 (colored) next main 1.18 (colored)

suppress gcc warnings

Revision 1.17.2.5 / (download) - annotate - [select for diffs], Tue Mar 25 16:21:08 2014 UTC (10 years ago) by yamt
Branch: yamt-pagecache
CVS Tags: yamt-pagecache-tag8
Changes since 1.17.2.4: +37 -10 lines
Diff to previous 1.17.2.4 (colored) to branchpoint 1.17 (colored)

comments.  some ascii arts to explain memory consumption.

Revision 1.17.2.4 / (download) - annotate - [select for diffs], Wed Aug 1 21:09:27 2012 UTC (11 years, 8 months ago) by yamt
Branch: yamt-pagecache
Changes since 1.17.2.3: +136 -104 lines
Diff to previous 1.17.2.3 (colored) to branchpoint 1.17 (colored)

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.

Revision 1.17.2.3 / (download) - annotate - [select for diffs], Wed Jun 13 14:18:49 2012 UTC (11 years, 10 months ago) by yamt
Branch: yamt-pagecache
Changes since 1.17.2.2: +8 -3 lines
Diff to previous 1.17.2.2 (colored) to branchpoint 1.17 (colored)

comment

Revision 1.17.2.2 / (download) - annotate - [select for diffs], Fri Feb 17 08:16:55 2012 UTC (12 years, 2 months ago) by yamt
Branch: yamt-pagecache
Changes since 1.17.2.1: +102 -72 lines
Diff to previous 1.17.2.1 (colored) to branchpoint 1.17 (colored)

comments

Revision 1.17.2.1 / (download) - annotate - [select for diffs], Fri Nov 25 13:58:11 2011 UTC (12 years, 4 months ago) by yamt
Branch: yamt-pagecache
Changes since 1.17: +168 -55 lines
Diff to previous 1.17 (colored)

radix_tree_gang_lookup_node and its variants: add a option to stop on a hole.

Revision 1.17 / (download) - annotate - [select for diffs], Wed Nov 2 13:49:43 2011 UTC (12 years, 5 months ago) by yamt
Branch: MAIN
CVS Tags: yamt-pagecache-base9, yamt-pagecache-base8, yamt-pagecache-base7, yamt-pagecache-base6, yamt-pagecache-base5, yamt-pagecache-base4, yamt-pagecache-base3, yamt-pagecache-base2, yamt-pagecache-base, tls-maxphys-base, tls-maxphys-20171202, tls-maxphys, tls-earlyentropy-base, tls-earlyentropy, rmind-smpnet-nbase, rmind-smpnet-base, riastradh-xf86-video-intel-2-7-1-pre-2-21-15, riastradh-drm2-base3, riastradh-drm2-base2, riastradh-drm2-base1, riastradh-drm2-base, riastradh-drm2, prg-localcount2-base3, prg-localcount2-base2, prg-localcount2-base1, prg-localcount2-base, prg-localcount2, phil-wifi-base, phil-wifi-20191119, phil-wifi-20190609, pgoyette-localcount-base, pgoyette-localcount-20170426, pgoyette-localcount-20170320, pgoyette-localcount-20170107, pgoyette-localcount-20161104, pgoyette-localcount-20160806, pgoyette-localcount-20160726, pgoyette-localcount, pgoyette-compat-merge-20190127, pgoyette-compat-base, pgoyette-compat-20190127, pgoyette-compat-20190118, pgoyette-compat-1226, pgoyette-compat-1126, pgoyette-compat-1020, pgoyette-compat-0930, pgoyette-compat-0906, pgoyette-compat-0728, pgoyette-compat-0625, pgoyette-compat-0521, pgoyette-compat-0502, pgoyette-compat-0422, pgoyette-compat-0415, pgoyette-compat-0407, pgoyette-compat-0330, pgoyette-compat-0322, pgoyette-compat-0315, pgoyette-compat, perseant-stdc-iso10646-base, perseant-stdc-iso10646, netbsd-9-base, netbsd-9-3-RELEASE, netbsd-9-2-RELEASE, netbsd-9-1-RELEASE, netbsd-9-0-RELEASE, netbsd-9-0-RC2, netbsd-9-0-RC1, netbsd-9, netbsd-8-base, netbsd-8-2-RELEASE, netbsd-8-1-RELEASE, netbsd-8-1-RC1, netbsd-8-0-RELEASE, netbsd-8-0-RC2, netbsd-8-0-RC1, netbsd-8, netbsd-7-nhusb-base-20170116, netbsd-7-nhusb-base, netbsd-7-nhusb, netbsd-7-base, netbsd-7-2-RELEASE, netbsd-7-1-RELEASE, netbsd-7-1-RC2, netbsd-7-1-RC1, netbsd-7-1-2-RELEASE, netbsd-7-1-1-RELEASE, netbsd-7-1, netbsd-7-0-RELEASE, netbsd-7-0-RC3, netbsd-7-0-RC2, netbsd-7-0-RC1, netbsd-7-0-2-RELEASE, netbsd-7-0-1-RELEASE, netbsd-7-0, netbsd-7, netbsd-6-base, netbsd-6-1-RELEASE, netbsd-6-1-RC4, netbsd-6-1-RC3, netbsd-6-1-RC2, netbsd-6-1-RC1, netbsd-6-1-5-RELEASE, netbsd-6-1-4-RELEASE, netbsd-6-1-3-RELEASE, netbsd-6-1-2-RELEASE, netbsd-6-1-1-RELEASE, netbsd-6-1, netbsd-6-0-RELEASE, netbsd-6-0-RC2, netbsd-6-0-RC1, netbsd-6-0-6-RELEASE, netbsd-6-0-5-RELEASE, netbsd-6-0-4-RELEASE, netbsd-6-0-3-RELEASE, netbsd-6-0-2-RELEASE, netbsd-6-0-1-RELEASE, netbsd-6-0, netbsd-6, matt-nb8-mediatek-base, matt-nb8-mediatek, matt-nb6-plus-nbase, matt-nb6-plus-base, matt-nb6-plus, localcount-20160914, khorben-n900, bouyer-socketcan-base1, bouyer-socketcan-base, bouyer-socketcan, agc-symver-base, agc-symver
Branch point for: yamt-pagecache, phil-wifi
Changes since 1.16: +34 -7 lines
Diff to previous 1.16 (colored)

comments

Revision 1.16 / (download) - annotate - [select for diffs], Tue Oct 25 14:11:27 2011 UTC (12 years, 5 months ago) by yamt
Branch: MAIN
Changes since 1.15: +22 -3 lines
Diff to previous 1.15 (colored)

add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.

Revision 1.15 / (download) - annotate - [select for diffs], Fri Oct 14 19:42:15 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.14: +223 -33 lines
Diff to previous 1.14 (colored)

- 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

Revision 1.14 / (download) - annotate - [select for diffs], Fri Oct 14 16:15:54 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.13: +4 -5 lines
Diff to previous 1.13 (colored)

unwarp a short line

Revision 1.13 / (download) - annotate - [select for diffs], Fri Oct 14 16:10:47 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.12: +9 -7 lines
Diff to previous 1.12 (colored)

constify

Revision 1.12 / (download) - annotate - [select for diffs], Fri Oct 14 16:06:05 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.11: +19 -9 lines
Diff to previous 1.11 (colored)

fix "get_tag" result of unittest

Revision 1.11 / (download) - annotate - [select for diffs], Fri Oct 14 15:31:35 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.10: +23 -22 lines
Diff to previous 1.10 (colored)

make the output of unittest a little machine-readable

Revision 1.10 / (download) - annotate - [select for diffs], Fri Oct 14 15:18:05 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.9: +6 -6 lines
Diff to previous 1.9 (colored)

int -> unsigned int where appropriate

Revision 1.9 / (download) - annotate - [select for diffs], Fri Oct 14 15:16:59 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.8: +10 -3 lines
Diff to previous 1.8 (colored)

add a function to check if a tree is empty.

Revision 1.8 / (download) - annotate - [select for diffs], Fri Oct 14 15:15:27 2011 UTC (12 years, 6 months ago) by yamt
Branch: MAIN
Changes since 1.7: +4 -3 lines
Diff to previous 1.7 (colored)

include string.h for memset

Revision 1.7 / (download) - annotate - [select for diffs], Thu May 19 10:06:56 2011 UTC (12 years, 11 months ago) by yamt
Branch: MAIN
CVS Tags: cherry-xenmp-base, cherry-xenmp
Changes since 1.6: +19 -4 lines
Diff to previous 1.6 (colored)

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

Revision 1.6 / (download) - annotate - [select for diffs], Thu May 19 10:01:21 2011 UTC (12 years, 11 months ago) by yamt
Branch: MAIN
Changes since 1.5: +5 -3 lines
Diff to previous 1.5 (colored)

radixtree: assertions

Revision 1.5 / (download) - annotate - [select for diffs], Thu May 19 10:00:30 2011 UTC (12 years, 11 months ago) by yamt
Branch: MAIN
Changes since 1.4: +25 -3 lines
Diff to previous 1.4 (colored)

radixtree: comments

Revision 1.4 / (download) - annotate - [select for diffs], Thu May 19 09:58:28 2011 UTC (12 years, 11 months ago) by yamt
Branch: MAIN
Changes since 1.3: +36 -3 lines
Diff to previous 1.3 (colored)

radixtree: comments

Revision 1.3 / (download) - annotate - [select for diffs], Tue Apr 26 20:53:53 2011 UTC (12 years, 11 months ago) by yamt
Branch: MAIN
Changes since 1.2: +28 -8 lines
Diff to previous 1.2 (colored)

fix _STANDALONE build

Revision 1.2 / (download) - annotate - [select for diffs], Thu Apr 14 15:42:02 2011 UTC (13 years ago) by yamt
Branch: MAIN
Changes since 1.1: +6 -10 lines
Diff to previous 1.1 (colored)

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

Revision 1.1.2.2 / (download) - annotate - [select for diffs], Sat Mar 5 15:08:32 2011 UTC (13 years, 1 month ago) by bouyer
Branch: bouyer-quota2
Changes since 1.1.2.1: +1122 -0 lines
Diff to previous 1.1.2.1 (colored) to branchpoint 1.1 (colored) next main 1.2 (colored)

Sync with HEAD

Revision 1.1.2.1, Tue Feb 22 21:31:15 2011 UTC (13 years, 1 month ago) by bouyer
Branch: bouyer-quota2
Changes since 1.1: +0 -1122 lines
FILE REMOVED

file radixtree.c was added on branch bouyer-quota2 on 2011-03-05 15:08:32 +0000

Revision 1.1 / (download) - annotate - [select for diffs], Tue Feb 22 21:31:15 2011 UTC (13 years, 1 month ago) by yamt
Branch: MAIN
CVS Tags: bouyer-quota2-nbase
Branch point for: bouyer-quota2

an implementation of radix tree.  the idea from linux.

This form allows you to request diff's between any two revisions of a file. You may select a symbolic revision name using the selection box or you may type in a numeric name using the type-in text box.




CVSweb <webmaster@jp.NetBSD.org>