aboutsummaryrefslogtreecommitdiffstats
path: root/epan/wmem/wmem.h
AgeCommit message (Collapse)AuthorFilesLines
2014-04-23Hash map implementation for wmem.Evan Huus1-0/+1
This has two expected uses: - Many current users of wmem_tree don't actually need the predecessor lookup it provides (the lookup_le function family). A hash map provides straight insertion and lookup much more efficiently than a wmem_tree when predecessor lookup isn't needed. - Many current users of glib's hash table and hash functions use untrusted data for keys, making them vulnerable to algorithmic complexity attacks. Care has been taken to make this implementation secure against such attacks, so it should be used whenever data is untrusted. In my benchmarks it is measurably slower than GHashTable, but not excessively so. Given the additional security it provides this seems like a reasonable trade-off (and it is still faster than a wmem_tree). Change-Id: I2d67a0d06029f14c153eaa42d5cfc774aefd9918 Reviewed-on: https://code.wireshark.org/review/1272 Reviewed-by: Evan Huus <eapache@gmail.com>
2014-04-02Scrap wmem splay trees for now.Evan Huus1-1/+0
There is confusion about API usage, and problems on my part concerning whether keys should be compared signed or unsigned, and how to do that efficiently. Unsigned keys in particular were behaving oddly. Change-Id: I075693bbd04c15f79f24f9a24006003a914cc572 Reviewed-on: https://code.wireshark.org/review/924 Reviewed-by: Evan Huus <eapache@gmail.com>
2014-03-29Splay tree implementation for wmemEvan Huus1-0/+1
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@gmail.com>
2014-03-04Remove all $Id$ from top of fileAlexis La Goutte1-2/+0
(Using sed : sed -i '/^ \* \$Id\$/,+1 d') Fix manually some typo (in export_object_dicom.c and crc16-plain.c) Change-Id: I4c1ae68d1c4afeace8cb195b53c715cf9e1227a8 Reviewed-on: https://code.wireshark.org/review/497 Reviewed-by: Anders Broman <a.broman58@gmail.com>
2013-07-21Add wmem queue 'implementation' by wrapping wmem_list and wmem_stack.Evan Huus1-0/+1
Also a bit of misc. refactoring of the stack while I was there, and doc tweaks. svn path=/trunk/; revision=50769
2013-07-20Replace wmem slist (singly-linked) with wmem list (doubly-linked).Evan Huus1-1/+1
The overhead is not large, and it makes append much faster (O(1) vs O(n)). It also will make a queue easy to add, which I need for a dissector I'm writing... svn path=/trunk/; revision=50744
2013-07-06Simple growable array implementation for wmem.Evan Huus1-0/+1
svn path=/trunk/; revision=50400
2013-06-18Resurrect wmem_memdup in its own misc. utilities group. Emem provides it, so weEvan Huus1-0/+1
need to provide an analogue at least for now. svn path=/trunk/; revision=50018
2013-06-15Most of a red-black tree implementation for wmem, based heavily on the ememEvan Huus1-0/+1
version. One plane trip's worth of work. svn path=/trunk/; revision=49945
2013-05-08Round two of wmem cleanup callbacks. While the emem tree behaviour will requireEvan Huus1-0/+1
recurring callbacks, I suspect most other potential uses will be once-only, so make that possible, and improve the documentation on the remaining issues. Also separate out the code into its own files and the testing into its own test case. svn path=/trunk/; revision=49209
2013-03-09Remove the wmem slab. It was an optimization mimicking the emem slabEvan Huus1-1/+0
(removed in r48218) which did nothing particularly useful. Also lets us remove another debugging environment variable. svn path=/trunk/; revision=48219
2013-01-15Add missing header #include as the slab is part of the API even if nobodyEvan Huus1-0/+1
outside wmem itself uses it yet. svn path=/trunk/; revision=47094
2012-12-19Implement a basic singly-linked for wmem.Evan Huus1-0/+1
Re-implement the stack as a wrapper for that. svn path=/trunk/; revision=46607
2012-12-15Basic wmem string-buffer. Not yet feature-equivalent to the emem version.Evan Huus1-0/+1
svn path=/trunk/; revision=46540
2012-11-03Wmem stack implementation using the wmem slab implementation to allocate frames.Evan Huus1-0/+1
svn path=/trunk/; revision=45881
2012-11-03Add wmem scopes for packet and file lifetimes. The file lifetime scope isn'tEvan Huus1-0/+1
yet initialized because I can't figure out where the enter() and leave() calls should go - the obvious place in packet.c causes a lot of assertion errors. svn path=/trunk/; revision=45879
2012-10-24Basic skeleton for wmem.Evan Huus1-0/+45
https://www.wireshark.org/lists/wireshark-dev/201210/msg00178.html svn path=/trunk/; revision=45746
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 16:42:11 +0000