summaryrefslogtreecommitdiff
path: root/epan/wmem/wmem_tree.c
AgeCommit message (Collapse)AuthorFilesLines
2017-05-31[WIP] RB tree removeinterval-tree-point-insertPeter Wu1-3/+59
Change-Id: Ie11f7a4bf4c0691b99ab386f8511db90ccfaf63f
2017-03-05wmem: Ensure callbacks are initialized and not accidentally unregisteredMichael Mann1-6/+3
Start the "callback register ID" at 1, so that zeroed out callback IDs are not found during unregister. Change-Id: I1d7d70f53d89c40e07d1637e1e195dd027855ed3 Reviewed-on: https://code.wireshark.org/review/20385 Reviewed-by: Michael Mann <mmann78@netscape.net> Petri-Dish: Michael Mann <mmann78@netscape.net> Reviewed-by: Evan Huus <eapache@gmail.com> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org>
2017-03-05Add wmem_tree_destroyMichael Mann1-0/+39
Allows the cleanup of NULL scoped wmem trees Change-Id: I7c49a224ca7e2f7ddfe0e38d3ea0e79aa2cb057c Reviewed-on: https://code.wireshark.org/review/20382 Reviewed-by: Michael Mann <mmann78@netscape.net> Petri-Dish: Michael Mann <mmann78@netscape.net> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Evan Huus <eapache@gmail.com>
2017-03-04Add wmem_tree_count.Michael Mann1-0/+21
There are cases where wmem_tree needs to know its number of nodes. Change-Id: I6411cf4275fd4d85a1d76382e1922d236be3b176 Reviewed-on: https://code.wireshark.org/review/20005 Petri-Dish: Michael Mann <mmann78@netscape.net> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Michael Mann <mmann78@netscape.net>
2017-02-09Add wmem_tree_remove32Michael Mann1-0/+11
Change-Id: Ic79fd0a2a13341dd7ba563cf3a056c51e9d16960 Reviewed-on: https://code.wireshark.org/review/20037 Reviewed-by: Michael Mann <mmann78@netscape.net>
2017-01-22wmem: fix rb-tree data printer feedJaap Keuter1-2/+2
When using a data printer for the red/black tree it is fed with the nodes of the tree. But nodes can be either subtree or data nodes. Don't feed the subtree nodes to the data printer. The data printer can't recognize it as such, can't handle it, or worse, could break stuff. Change-Id: Ibbc1311d901c0d0c52e710f951dd53620f2c3d0f Reviewed-on: https://code.wireshark.org/review/19652 Reviewed-by: Evan Huus <eapache@gmail.com> Reviewed-by: Michael Mann <mmann78@netscape.net> Petri-Dish: Michael Mann <mmann78@netscape.net> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Anders Broman <a.broman58@gmail.com>
2016-08-01Remove checkAPI warnings from wmem.Michael Mann1-6/+6
printf and g_warning are not allowed in epan or its subdirectories Change-Id: I4c07a7258f4c9566384bef93af35c350b5c88758 Reviewed-on: https://code.wireshark.org/review/16801 Petri-Dish: Michael Mann <mmann78@netscape.net> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Anders Broman <a.broman58@gmail.com>
2015-11-24Introduces augmented interval treesMatthieu Coudron1-57/+69
Interval trees (wmem_itree_t) are implemented as an extension of wmem_tree with a guint64-based range as the key. This is useful for instance in MPTCP analysis, to look for packets matching a range defined by a mapping across TCP subflows. Change-Id: Iea706d44fe975e390a4191ad0257ef37d5c71525 Reviewed-on: https://code.wireshark.org/review/11714 Reviewed-by: Evan Huus <eapache@gmail.com> Petri-Dish: Evan Huus <eapache@gmail.com> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Guy Harris <guy@alum.mit.edu>
2015-11-11Change prototype of callbacks passed to wmem_tree_foreach so that theyMatthieu Coudron1-1/+1
accept the node key as a first parameter. wmem_tree accepts all sort of keys (strings, integers, soon ranges), thus it is of interest for various purposes (testing, greedy search) to know the key of the node. Change-Id: Ie748b917bef91f0b1ba8cce15bd1b471922641dc Reviewed-on: https://code.wireshark.org/review/11683 Petri-Dish: Alexis La Goutte <alexis.lagoutte@gmail.com> Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org> Reviewed-by: Evan Huus <eapache@gmail.com> Reviewed-by: Michael Mann <mmann78@netscape.net>
2015-08-11wmem: Fix wmem_tree_remove_stringStig Bjørlykke1-3/+1
Always set is_removed when insert data in a node. Change-Id: I8fb50932a369e3f4fe8a1f743462683fff705cc2 Reviewed-on: https://code.wireshark.org/review/9978 Reviewed-by: Stig Bjørlykke <stig@bjorlykke.org>
2015-08-11wmem: Mark removed strings with is_removedStig Bjørlykke1-2/+7
This will allow integer value 0 again. Change-Id: Ibfa4249ea8b887971d3b3214ad9e4d095d20d155 Reviewed-on: https://code.wireshark.org/review/9973 Reviewed-by: Stig Bjørlykke <stig@bjorlykke.org>
2015-08-11Added Reload Lua plugins.Stig Bjørlykke1-2/+14
This is initial support for reloading Lua plugins without restarting the application. Still todo: - Deregister FileHandlers - Support deregister ProtoField with existing abbrev (same_name_hfinfo) - Add a progress dialog when reloading many plugins - Search for memory leakages in wslua functions Change-Id: I48870d8741251705ca15ffe1068613fcb0cb18c1 Reviewed-on: https://code.wireshark.org/review/5028 Reviewed-by: Stig Bjørlykke <stig@bjorlykke.org>
2015-06-26wmem: permit lookups in NULL trees (oops)Evan Huus1-1/+7
Change-Id: I222b95b48b7ac8debbd717b32dd471742222c16b Reviewed-on: https://code.wireshark.org/review/9177 Reviewed-by: Evan Huus <eapache@gmail.com>
2015-06-26wmem: convert string trees to single-layerEvan Huus1-78/+92
The whole radix tree thing is kind of neat (and may even be more performant for short strings?) but it's really confusing to reason about and is terribly inefficient for long strings. Ping-Bug: 9078 Change-Id: I1bd333918a6e557801e82f4553d386120138065e Reviewed-on: https://code.wireshark.org/review/9165 Reviewed-by: Evan Huus <eapache@gmail.com>
2015-06-25wmem: bubble up key type change another functionEvan Huus1-5/+5
Follow-up to gb679e2a. Change-Id: I6cc168c3f3a6e1c8ce7bfa9344255acd3c8a7d20 Reviewed-on: https://code.wireshark.org/review/9164 Reviewed-by: Evan Huus <eapache@gmail.com>
2015-06-25wmem: convert tree key to void*Evan Huus1-17/+16
Rather than forcing everything to live in guint32. We still use guints for now via the G_POINTER_TO_UINT and vice-versa, but this paves the way in future for custom comparison functions which will make e.g. string trees far more efficient for long strings. Change-Id: Ibb15400f74761ae295948507df8d2e022f2ebb05 Reviewed-on: https://code.wireshark.org/review/9138 Reviewed-by: Evan Huus <eapache@gmail.com>
2014-10-19Eliminate use of ctype.h routines.Guy Harris1-3/+2
That way, we don't do locale-sensitive case-insensitivity (yes, the locale can affect case-mapping - in a Turkish locale, "I" isn't the upper-case version of "i", for example). Change-Id: I5f7663e85160558ff3769617f924e45049c9c384 Reviewed-on: https://code.wireshark.org/review/4843 Reviewed-by: Guy Harris <guy@alum.mit.edu>
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-12-20Fix [-Wmissing-prototypes]Anders Broman1-1/+1
svn path=/trunk/; revision=54280
2013-09-28Don't assert that the key to a wmem tree operation is short. If XMPP wants toEvan Huus1-4/+0
use a 1500-byte string as a key, so be it. It will be slow, but at least it will work. Fixes https://bugs.wireshark.org/bugzilla/show_bug.cgi?id=9078 svn path=/trunk/; revision=52261
2013-09-01Send all alloc and free calls within wmem through wmem_alloc and wmem_free withEvan Huus1-3/+3
a NULL allocator. This gives us a single, central place to handle out-of-memory errors (by, for example, throwing an exception) for basically all of epan. The only remaining glib memory that is directly allocated is for the hash tables used by the simple and strict allocators. svn path=/trunk/; revision=51627
2013-08-14Include config.h first; it defines _FILE_OFFSET_BITS, and if some systemGuy Harris1-1/+2
header later causes it to be redefined - as happens on my Solaris 11 virtual machine - we get a redefinition warning, which gets treated as an error. svn path=/trunk/; revision=51344
2013-07-31Add wmem_tree_is_empty(). Also permit lookups on a NULL tree for compatibilityEvan Huus1-1/+9
with emem. svn path=/trunk/; revision=51045
2013-07-15Fix warnings: format '%blah' expects argument of type 'foo', but argument ↵Chris Maynard1-3/+5
'i' has type 'bar' [-Wformat]. svn path=/trunk/; revision=50639
2013-06-27Misc little cleanups to wmem tree (comments, whitespace, assertions)Evan Huus1-9/+4
svn path=/trunk/; revision=50182
2013-06-22Make assertions in tree lookup more useful and fix formatting.Evan Huus1-8/+7
Should help debugging https://bugs.wireshark.org/bugzilla/show_bug.cgi?id=8833 svn path=/trunk/; revision=50115
2013-06-18Refactor insert32 to use lookup_or_insert32 with the right flags.Evan Huus1-59/+17
svn path=/trunk/; revision=50013
2013-06-18Refactor lookup_or_insert32 to remove a bunch of continue and break statementsEvan Huus1-29/+24
as well as a confusing while(TRUE). svn path=/trunk/; revision=50012
2013-06-18Simplify node structure. Use a boolean for whether or not it's a subtree, and anEvan Huus1-34/+35
enum for the color (red/black). Don't use bitfields since they don't save us much (if anything) in terms of space and don't nest the fields in their own anonymous struct. svn path=/trunk/; revision=50011
2013-06-18Factor function for node creation out and use it in several places.Evan Huus1-55/+39
svn path=/trunk/; revision=50010
2013-06-18Factor common code for red-black tree array lookups into a helper function andEvan Huus1-38/+12
use it for both direct lookups and less-than-or-equal-to lookups. svn path=/trunk/; revision=50008
2013-06-18Remove wmem_tree_create_subtree, it does nothing we can't do withEvan Huus1-16/+1
wmem_tree_new. svn path=/trunk/; revision=50007
2013-06-18Factor string-packing code into a common function to use in both insert_stringEvan Huus1-48/+25
and lookup_string. svn path=/trunk/; revision=50006
2013-06-18Re-port a bunch of the red-black tree code from wmem with fewer modifications,Evan Huus1-123/+307
and enable the tests. Lesson: make it work, *then* refactor it into sanity. svn path=/trunk/; revision=50002
2013-06-17Extract some common code for array lookups, and replace some DISSECTOREvan Huus1-42/+18
assertions with regular glib assertions - there's no guarantee that wmem code will always be run from within a dissector. svn path=/trunk/; revision=49993
2013-06-17Much smarter handling of autoreset trees.Evan Huus1-2/+23
svn path=/trunk/; revision=49970
2013-06-16More callback tweaks, to permit unregistering a callback from the same placeEvan Huus1-1/+1
it was originally registered. svn path=/trunk/; revision=49969
2013-06-16Rework the user callback code a bit to make it saner to use with the auto-resetEvan Huus1-3/+5
trees. svn path=/trunk/; revision=49966
2013-06-16Simplify the tree code slightly - just don't call the transform functionEvan Huus1-14/+11
if it's NULL, meaning we don't need to define an identity callback. svn path=/trunk/; revision=49962
2013-06-15Most of a red-black tree implementation for wmem, based heavily on the ememEvan Huus1-0/+681
version. One plane trip's worth of work. svn path=/trunk/; revision=49945
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-26 02:48:00 +0000