History log of /external/valgrind/coregrind/m_oset.c
Revision Date Author Comments (<<< Hide modified files) (Show modified files >>>)
913b580c090c25766cafd77a19993f89fb1271e3 22-Aug-2015 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix warning signed unsigned comparison in m_oset.c :
../../coregrind/m_oset.c:413:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15582 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
b3a1e4bffbdbbf38304f216af405009868f43628 21-Aug-2015 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates, to include 2015. No functional change.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15577 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
47755db2a44e01f198324e7d0734566b43d04d30 05-Aug-2015 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> The number of elements in an OSet cannot be negative.
Let the return type of VG_(OSetGen_Size) reflect that.
Also fix a few casts.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15491 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
ee0d0e9cd0351721260f8b079495ed9d5ecf5faf 18-Oct-2014 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Constify m_oset, m_sparsewa, and m_wordfm.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14640 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
b49e4a5087d1927179baf1dea9dcc658fd778348 14-Sep-2014 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Tidy up m_oset.c
- Document that the allocation function must ot return NULL.
- As a conequence of the previous requirement the various Create and AllocNode
functions cannot return NULL. Remove pointless asserts at call sites.
- Remove documentation of undefined function CreateWithCmp.
- Names of library functions (such as 'free') are reserved as a are names
beginning with underscores. Don't use those.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14531 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
0f157ddb404bcde7815a1c5bf2d7e41c114f3d73 18-Oct-2013 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates (20XY-2012 ==> 20XY-2013)


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13658 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
d35da712f54fcf812066dbaa256a5c1555b49468 07-Oct-2013 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Remove unused variable (and associated compiler warning).


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13625 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
a388ee4c84b6c08eba5dbc9441587a492d74b8cf 06-Oct-2013 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> pub_tool_oset.h and m_oset.c cleanup

* Remove dead code in m_oset.c VG_(OSetGen_ResetIterAt)
The code at the end of VG_(OSetGen_ResetIterAt) was unreachable
(detected by BEAM checker).
Looking at SVN, the initial commit of VG_(OSetGen_ResetIterAt)
already contained this deadcode.

* pub_tool_oset.h was wrongly indicating that signed words could
be used for fast cmp oset.

* modified memcheck/tests/unit_oset.c to test VG_(OSetGen_ResetIterAt)

* modified memcheck/tests/unit_oset.c to not use signed words
(it was previously using signed words, but only with positive values)





git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13622 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
c91f58449e6fc2a4ce0851639a342c4277612fbb 15-Sep-2013 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix inclusion of header files in coregrind. No pub_tool_*.h should be
included here.
Added pub_core_poolalloc.h and renamed pub_tool_inner.h to pub_core_inner.h.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13548 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
3e7986312a0ffc7646b0552d4c4ea3744a870e73 24-Nov-2012 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix some casts that removed const-ness as pointed out by
GCC's -Wcast-qual.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13138 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
19f91bbaedb4caef8a60ce94b0f507193cc0bc10 10-Nov-2012 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix more Char/HChar mixups. Closing in...


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13119 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
54fe2021b87b9e5edb8ec8070f47b86d5cafb8aa 28-Oct-2012 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Char/HChar and constness fixes. Mostly cost center
on allocators which is always a const HChar *


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13089 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
6e07448898bce224dea3741093ba67f9b1d72a5b 18-Jan-2012 bart <bart@a5019735-40e9-0310-863c-91ae7b9d1cf9> Pool allocator: change the semantics of VG_(releasePA)() according to comment http://bugs.kde.org/show_bug.cgi?id=282230#c50.
This change also makes the semantics of releasePA match the semantics of
other release functions, e.g. those in XPCOM (see also http://developer.mozilla.org/en/XPCOM_Interface_Reference/nsISupports#Release%28%29).


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12343 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
6643e96a72e8530a7c8830c02ffb2fb4aee74c88 17-Jan-2012 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fixes 282230 group allocator for small fixed size, use it for MC_Chunk/SEc vbit

* new files include/pub_tool_groupalloc.h and coregrind/m_groupalloc.c
implementing a group allocator (based on helgrind group alloc).
* include/Makefile.am coregrind/Makefile.am : added pub_tool_groupalloc.h
and m_groupalloc.c
* helgrind/libhb_core.c : use pub_tool_groupalloc.h/m_groupalloc.c
instead of the local implementation.
* include/pub_tool_oset.h coregrind/m_oset.c : new function
allowing to create an oset that will use a pool allocator.
new function allowing to clone an oset (so as to share the pool alloc)
* memcheck/tests/unit_oset.c drd/tests/unit_bitmap.c : modified
so that it compiles with the new m_oset.c
* memcheck/mc_main.c : use group alloc for MC_Chunk
memcheck/mc_include.h : declare the MC_Chunk group alloc
* memcheck/mc_main.c : use group alloc for the nodes of the secVBitTable OSet
* include/pub_tool_hashtable.h coregrind/m_hashtable.c : pass the free node
function in the VG_(HT_destruct).
(needed as the hashtable user can allocate a node with its own alloc,
the hash table destroy must be able to free the nodes with the user
own free).
* coregrind/m_gdbserver/m_gdbserver.c : pass free function to VG_(HT_destruct)
* memcheck/mc_replace_strmem.c memcheck/mc_machine.c
memcheck/mc_malloc_wrappers.c memcheck/mc_leakcheck.c
memcheck/mc_errors.c memcheck/mc_translate.c : new include needed
due to group alloc.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12341 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
ec062e8d96a361af9905b5447027819dfbfee01a 23-Oct-2011 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update all copyright dates, from 20xy-2010 to 20xy-2011.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12206 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9eecbbb9a9cbbd30b903c09a9e04d8efc20bda33 03-May-2010 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates to 2010.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11121 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9f207460d70d38c46c9e81996a3dcdf90961c6db 10-Mar-2009 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Updated copyright years.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9344 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
889a5d6885675a32530affd24ac3f66ba6ae026c 23-Feb-2009 bart <bart@a5019735-40e9-0310-863c-91ae7b9d1cf9> Declared those function arguments that are not modified as const.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9245 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
f6ff3653ef3b3a63fae603cc8abc7dff41a355a7 21-Feb-2009 bart <bart@a5019735-40e9-0310-863c-91ae7b9d1cf9> VG_(OSetGen_ResetIterAt)() now also works for OSet's that do not have an
explicit comparison function.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9212 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
c4431bfe04c7490ea2d74939d222d87f13f30960 15-Jan-2009 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Introduce a new type, PtrdiffT. Replace lots of uses of OffT (all those
that are memory offsets) with PtrdiffT; OffT should only be used for file
sizes and offsets.

Change Off64T from a ULong to a Long, as it should be. Replace some uses
of ULong in the address space manager with Off64T to match.

Also add a comment explaining the meanings of the basic types like Addr,
OffT, SizeT, etc.

Also fix the prototype for VG_(pread) -- the last arg is an OffT, not an
Int.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@8959 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
23d446924f0348da64ca5e8702d94bafc81ebf2b 21-Nov-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Helgrind's event-map garbage collector hammers VG_(OSetGen_Next).
Import an optimisation from the analogous function in m_wordfm.c.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@8795 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9c606bd8634cd6b67bb41fa645b5c639668cfa2d 18-Sep-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Merge all remaining changes from branches/PTRCHECK. These are some
relatively minor extensions to m_debuginfo, a major overhaul of
m_debuginfo/readdwarf3.c to get its space usage under control, and
changes throughout the system to enable heap-use profiling.

The majority of the merged changes were committed into
branches/PTRCHECK as the following revs: 8591 8595 8598 8599 8601 and
8161.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@8621 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
b8b79addf04dd5d0b558916e26df0b1927cbd758 03-Mar-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Merge in the DATASYMS branch.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7540 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
966f0550ec8dcaf65973115e8ab33027bdba4525 23-Feb-2008 bart <bart@a5019735-40e9-0310-863c-91ae7b9d1cf9> Added const keyword to second argument of VG_(OSetGen_Remove)().

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7436 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
4d474d086188fd1f29fa97dbd84d8ea2e589a9b8 11-Feb-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates ("200X-2007" --> "200X-2008").


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7398 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
5a835d5980202c293b27f55f257e8e4ef3d170a0 30-Dec-2007 tom <tom@a5019735-40e9-0310-863c-91ae7b9d1cf9> Add const qualifiers to appropriate arguments of OSet routines.

Patch from Bart Van Assche <bart.vanassche@gmail.com>.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7308 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9bc8d9e3c2c88d6c98609e48f123d673ed4bcb67 09-Dec-2007 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Don't do comparisons of (signed) Words by merely subtracting them, as
this does not always produce correct results. Instead use a slower
but correct method. Fixes #147545. (Nick Nethercote, Tom Hughes et
al)



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7283 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
e2a9ad3b71e0eccca6115349192d5e844be4eb0a 17-Sep-2007 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Split the OSet interface into two parts: "OSetGen_", which is the existing
interface and provides full power; and "OSetWord_", which is an
easier-to-use interface for if you just want to store words.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6841 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9ebd6e0c607fa30301b1325874eb8de871c21cc5 08-Jan-2007 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6488 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
dff46d5963fd0199234597a147da6a8dff45705a 17-Oct-2006 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Merge r6133:

Inline stackPush and stackPop and placate gcc's resulting concerns
about uninitialised variables.

and also change ownership.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6270 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
851ba8df51b3b05471a22f701a6cf22111523022 24-Feb-2006 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Minor readability change.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5698 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
afa12261c2989fc05af6aeea5151574f8bd373bc 24-Dec-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix a nasty 64-bit-uncleanness bug in OSet spotted by Julian -- for fast
comparisons it was only considering the bottom 32-bits of the key.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5427 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
e004d72552b5c767e51b3d807734829e18b87d55 22-Dec-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Add a destructor function to OSet_Destroy() which can be called for each
node.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5402 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
a527a4998aa88e72f0108deefb2cf4cb182a86b3 16-Dec-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Add info about overhead in heap blocks and OSet nodes.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5361 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
60a4b0b77180f0c54ddca5c8d9ca20a877637f01 12-Oct-2005 tom <tom@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix statement-before-declaration warnings for the core code.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4906 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
aa260e8b6412ada7ce839a56f9783a6a278d330e 17-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Added VG_(OSet_LookupWithCmp)(), which can be useful.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4444 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
9a46324fe85e70f08777cf7e37863293a25637ba 16-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> lots of little wibbles



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4432 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
0684dd4bf89d1dd83ace18c8c9b04cb5a22b4c2b 15-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> wibbles


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4417 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
1d68e532e93e849e771437dd8a61c88fac21302f 15-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> wibble



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4414 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
6db347097fa2dd5f54388783d99c651ac42d5658 15-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Trim some fat; removing this assertion makes Remove() about 5% faster.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4413 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c
e1b2b96331fba55d5b15edf348cbb863d2e5feee 15-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Added new module, m_oset, which provides a generic data structure, OSet,
which is a sorted set with no duplicates. This is derived from
m_skiplist, which it will hopefully replace. The interface has the
following improvements:

- Avoided all mention of how the data structure is implemented in the
interface, so it could be replaced with another data structure without
changing external code.
- Two kinds of comparison: fast -- use the first word of each element
for comparison; slow -- use a custom function. The custom function
compares a key with an element, so non-overlapping interval lists can
be supported easily. m_skiplist only supports the slow variant, and it
makes things almost 2x faster.
- Users pass in malloc() and free() functions, so m_oset.c it doesn't
rely on any particular allocator.
- It has a Destroy() function which will deallocate all the nodes.
- It allows variable-sized nodes.
- No static constructor; I needed the flexibility of being able to
execute arbitrary code in the constructor. This also means no type
internals are exposed.

No part of Valgrind actually uses OSet yet, although I've privately
converted several data structures, and so I'm confident that the
interface is basically sound. Some functions may be added later.

The implementation uses AVL trees, and has the following
characteristics:

- Lookup is much faster than for skiplists -- around 3x. This is
because the inner lookup loop is much tighter.
- Insertion and removal is similar speed to skiplists, maybe a little
slower, but there's still some fat to be trimmed.
- The code is a bit longer and more complex than the skiplist code.

This was intended to replace the need for the VgHashTable type. But my
experiments have shown that VgHashTable is really fast, faster than both
AVL trees and skiplists in all but extreme cases (eg. if the hashtable
becomes way too full): insertion takes constant time, because you always
prepend to chains; lookup depends on chain length, but the inner loop
is so tight that you need about 20 elements per chain before it gets
worse than the AVL tree; removal is similar to lookup. And because
insertion uses prepending, any locality in accesses will help things. If
VgHashTable had its interface cleaned up to look like OSet's, and was made
to auto-resize when it got too full, it might be a better OSet (although
it's not sorted).

So, it's currently unclear exactly how the AVL tree OSet will be used.
The skiplist could be converted to the new interface (I have a 90%
complete version which I used in the comparison experiments). If
VgHashTable was converted to the same interface (or as close as
possible) it would make direct comparison of important places (eg.
Memcheck's malloc_lists) simple.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4410 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_oset.c