| Commit message (Collapse) | Author | Age | Files | Lines | |
|---|---|---|---|---|---|
| * | [RBTREE] Fixed an edge case (#2562) | rajdakin | 2025-04-22 | 1 | -1/+3 |
| | | |||||
| * | [RBTREE] Cache boundary nodes and remove `add_range()` (#2557) | Chi-Kuan Chiu | 2025-04-22 | 1 | -31/+54 |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Cache leftmost and rightmost node Add two fields to `rbtree`: `lefter` and `righter`, to cache the leftmost and rightmost nodes respectively. This eliminates the need for O(log N) traversals in `rb_get_lefter()` and `rb_get_righter()`. Motivated by the Linux kernel's use of cached pointers for `rb_first()` and `rb_last()`, this change improves efficiency of boundary queries by replacing repeated tree walks with direct pointer dereference. Experiment: running `chess.exe` with Box64 + Wine (#2511) - ~3,500 insertions into the tree - 607 lightweight cache updates (single assignment) - 397 full tree traversals avoided This results in reduced runtime overhead for boundary checks, with memory cost (+2 pointer per tree). Expected benefits increase in larger or more dynamic workloads. Ref: https://docs.kernel.org/core-api/rbtree.html * Remove redundant add_range() wrapper The function `add_range()` was only called when `tree->root == NULL`. In such cases, the while-loop inside `add_range()` never runs, resulting in a call to `add_range_next_to()` with `prev == NULL`. Replaced it with direct calls to `add_range_next_to(tree, NULL, ...)`. | ||||
| * | [DEBUG] Exposed a debug function to print an rbtree | ptitSeb | 2025-04-20 | 1 | -20/+24 |
| | | |||||
| * | Eliminated many compilation warnings (#2535) | Yang Liu | 2025-04-15 | 1 | -1/+2 |
| | | |||||
| * | [DYNAREC] Improved handling of db_size rbtree | ptitSeb | 2025-04-09 | 1 | -0/+310 |
| | | |||||
| * | Improved file map tracking, and use file map info in dynarec for bigblock ↵ | ptitSeb | 2025-01-27 | 1 | -0/+14 |
| | | | | | setting | ||||
| * | Added more rbtrees in dynarec managment, to speedup ↵ | ptitSeb | 2024-12-23 | 1 | -5/+39 |
| | | | | | FindDynablockFromNativeAddress function | ||||
| * | [TRACE] Use lower case hex on rbtree | ptitSeb | 2024-11-17 | 1 | -6/+6 |
| | | |||||
| * | [RBTREE] Unify naming and prevent unintended symbol exposure (#2005) | Jim Huang | 2024-11-06 | 1 | -71/+70 |
| | | | | | | Red-black tree operations now consistently use the 'rbtree_' prefix, and internal functions remain unexposed. Tested on RV64GC, resulting in a 498-byte reduction in the .text section size. | ||||
| * | [rebree]The name of rbtree is set error. (#1984) | zymayunyan | 2024-10-31 | 1 | -1/+1 |
| | | |||||
| * | Improve debugging trace of rb_tree | ptitSeb | 2024-10-08 | 1 | -5/+7 |
| | | |||||
| * | [DYNAREC] Improved trace a bit | ptitSeb | 2024-02-01 | 1 | -1/+1 |
| | | |||||
| * | [DYNAREC] use an rbtree for dynablock size and max_db_size update | ptitSeb | 2024-01-23 | 1 | -0/+14 |
| | | |||||
| * | Ficxed an issue with rbtree rb_get_end utility function | ptitSeb | 2024-01-16 | 1 | -3/+4 |
| | | |||||
| * | [RBTREE] Reverted memory tracking to 32 bits (#1201) | rajdakin | 2024-01-13 | 1 | -9/+9 |
| | | |||||
| * | Fixed issue on rbtree on rb_get_end when end is another block | ptitSeb | 2023-12-31 | 1 | -13/+19 |
| | | |||||
| * | [MEMORY] Switched from a sparse array to a red-black tree (#1180) | rajdakin | 2023-12-31 | 1 | -0/+894 |
| * [MEMORY] Switched from a sparse array to an RB tree * [RBTREE] Fixed the Android build | |||||