Wireshark-commits: [Wireshark-commits] master 7df8839: Splay tree implementation for wmem
URL: https://code.wireshark.org/review/gitweb?p=wireshark.git;a=commit;h=7df883954effe0b86a6d49ed33b888665afc0054
Submitter: Evan Huus (eapache@xxxxxxxxx)
Changed: branch: master
Repository: wireshark
Commits:
7df8839 by Evan Huus (eapache@xxxxxxxxx):
Splay tree implementation for wmem
This is a tree implementation intended to replace the current red-black tree in
wmem_tree (which was inherited from emem), assuming there are no regressions.
Splay trees bubble recently accessed keys to the top, and as such have a number
of very nice properties: https://en.wikipedia.org/wiki/Splay_tree
This implementation is a variant known as "independent semi-splaying", which has
better practical performance. It should do about as well as the red-black tree
for random insertions and accesses, but somewhat better for patterned accesses
(such as accessing each key in order, or accessing certain keys very
frequently).
There are a few other changes relative to the red-black tree implementation that
are worth mentioning:
- Instead of requiring complex keys to be split into guint32 chunks and doing
this weird trick with sub-trees, I let the keys be arbitrary pointers and
allowed the user to specify an arbitrary comparison function. If the function
is NULL then the pointers are compared directly for the simple integer-key
case.
- Splay trees do not need to store a red-black colour flag for each node. It is
also much easier to do without the parent pointer in each node. And due to
the simpler system for complex keys, I was able to remove the "is_subtree"
boolean. As such, splay nodes are 12 bytes smaller on 32-bit platforms, and
16 bytes smaller on a 64-bit platform.
All done in about half the lines of code.
Change-Id: I89fb57e07d2bb7e3197190c7c2597b0c5adcc03b
Reviewed-on: https://code.wireshark.org/review/758
Reviewed-by: Evan Huus <eapache@xxxxxxxxx>
Actions performed:
from a1d4189 Upgrade Windows builds to Lua 5.2.1
adds 7df8839 Splay tree implementation for wmem
Summary of changes:
epan/CMakeLists.txt | 1 +
epan/wmem/Makefile.common | 2 +
epan/wmem/wmem.h | 1 +
epan/wmem/wmem_splay.c | 368 +++++++++++++++++++++++++++++++++++++++++++++
epan/wmem/wmem_splay.h | 150 ++++++++++++++++++
epan/wmem/wmem_test.c | 190 ++++++++++++++++++++++-
6 files changed, 711 insertions(+), 1 deletion(-)
create mode 100644 epan/wmem/wmem_splay.c
create mode 100644 epan/wmem/wmem_splay.h
