aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT/ImmutableSet.h
AgeCommit message (Collapse)Author
2013-02-14Add missing typename to unbreak the MSVC 2012 build.Francois Pichet
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175129 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-13Fix iterator definitions for ImmutableSet and ImmutableMap.Ryan Govostes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175097 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-13Add iterator_traits to ImmutableMap and ImmutableSet.Ryan Govostes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175085 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-10Fix include guards so they exactly match file names.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172025 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Sort the #include lines for the include/... tree with the script.Chandler Carruth
AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-14Fix a typo that made ImmutableMap::getMaxElement() useless.Benjamin Kramer
Add a basic unit test for ImmutableMap. Found by inspection. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165907 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Mark unimplemented copy constructors and copy assignment operators as ↵Craig Topper
LLVM_DELETED_FUNCTION. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164014 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-16Tidy up formatting of some elses on a separate line from preceding bracing. ↵Craig Topper
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163992 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-16Tidy up trailing whitespace.Craig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163988 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-16Remove unneeded header.Craig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163987 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-18Remove tabs.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160471 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-07Constify (trivially) ImmutableSet::iterator::getVisitState().Jordy Rose
This was probably intended all along. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156318 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-20Make sure ImmutableSet never inserts Tombstone/Entry into DenseMap.Anna Zaks
ImmutAVLTree uses random unsigned values as keys into a DenseMap, which could possibly happen to be the same value as the Tombstone or Entry keys in the DenseMap. Test case is hard to come up with. We randomly get failures on the internal static analyzer bot, which most likely hits this issue (hard to be 100% sure without the full stack). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153148 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Convert assert(0) to llvm_unreachableCraig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149849 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-02Make canonicalization of ImmutableSetRef::asImmutableSet() semi-explicit.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140959 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-16Add ImmutableMapRef and ImmutableSetRef, which consolidate ↵Ted Kremenek
Immutable[Map,Set] and its Factory. This may eventually replace Immtuable[Map,Set]. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139967 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30Performance optimization on ImmutableMap/ImmutableSet:Ted Kremenek
- Use a DenseSet instead of a FoldingSet to cache canonicalized nodes. This reduces the overhead of double-hashing. - Use reference counts in ImutAVLTree to much more aggressively recover tree nodes that are no longer usable. We can generate many transient nodes while using add() and remove() on ImmutableSet/ImmutableMaps to generate a final set/map. For the clang static analyzer (the main client of these data structures), this results in a slight speedup (0.5%) when analyzing sqlite3, but much more importantly results in a 30-60% reduction in peak memory usage when the analyzer is analyzing a given function in a file. On average that's about a ** 44% reduction ** in the memory footprint of the static analyzer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120459 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-29Merge System into Support.Michael J. Spencer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120298 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-24Tweak ImmutableMap/ImmutableSet/ImmutableList APIsTed Kremenek
to use lowercase letters for the start of most method names and to replace some method names with more descriptive names (e.g., "getLeft()" instead of "Left()"). No real functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120070 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-17Fix warnings about missing parents between || and &&.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119454 91177308-0d34-0410-b5e6-96231b3b80d8
2010-04-13Fix -Asserts warnings.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101191 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-01Add an immutable interval map, prepared to be used by flat memory model Zhongxing Xu
in the analyzer. WIP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94976 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-01Simplify code. We can compare TNew with T in one batch.Zhongxing Xu
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94973 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-22Store flags in bitfields instead of masking them into the pointer for the ↵Ted Kremenek
left child. This leads to some nice conceptually cleanups. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94121 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Tidy up assertion syntax. No functionality change.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94117 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-05Make a few more LLVM headers parsable as standalone headers.Douglas Gregor
Fix some problems with the hidden copy constructors for ImmutableMap/ImmutableSet found by Clang++. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86186 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-26Move DataTypes.h to include/llvm/System, update all users. This breaks the lastChandler Carruth
direct inclusion edge from System to Support. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85086 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-14Delete bogus semicolons.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84132 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-13Provide a mode for ImmutableMap/ImmutableSet to not automatically ↵Ted Kremenek
canonicalize the internal functional AVL trees. This should speedup clients that use ImmutableMap/ImmutableSet but don't require fast comparisons of maps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84010 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-03Make ImmutableMap/ImmutableSet quicker by only canonicalizing the tree after anTed Kremenek
Add or Remove operation complete, and not while building the intermediate tree. This trades a little bit more memory usage for less accesses to the FoldingSet. On a benchmark for the clang static analyzer, this shaves off another 13% of execution time when using field/array sensitivity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80955 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-03Set the 'cached digest' flag after computing the digest for anTed Kremenek
ImutAVLTree. This was accidentally left out, and essentially caused digest caching to be ignored in ImmutableMap and ImmutableSet (this bug was detected from shark traces that showed ComputeDigest was in the hot path in the clang static analyzer). This reduces the running time of the clang static analyzer on an example benchmark by ~32% for both RegionStore (field-sensitivty) and BasicStore (without field-sensitivity). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80877 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-01Make default ctor for ImmutableSet::iterator public.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77762 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-19Remove redundant qualifiers.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76357 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-10ImmutableMap/ImmutableSet: Allow caching of ImutAVLTree digests while the treeTed Kremenek
is still mutable. My experiments show this reduces the amount of times we compute a full tree digest by over 50% on very small cases, and potentially much larger on others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75207 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-09ImmutableSet/ImmutableMap: Allow caching of null digests by properly using a ↵Ted Kremenek
flag to record if the digest of an ImutAVLTree has been cached. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75157 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-23Add ImmutableMap::getMaxElement(), a method that returns the <key,value> ↵Ted Kremenek
pair in a ImmutableMap that has the highest ranked key. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65326 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-20Removed trailing whitespace.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65197 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-12Add operator->, patch by Ben Laurie!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64378 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-12Add method 'isSingleton()' to ImmutableSet. This returns true if the set ↵Ted Kremenek
contains exactly one element. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64359 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-09Removed trailing whitespace.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62000 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-03TypoNick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58594 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-22Unbreak build for VC2008. Patch by Argiris Kirtzidis!Anton Korobeynikov
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47480 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-11The factories for ImutAVLTree/ImmutableSet/ImmutableMap now take an (optional)Ted Kremenek
BumpPtrAllocator argument to their constructors. This BumpPtrAllocator will be used to allocate trees. If no BumpPtrAllocator is provided, one is created (as before). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46975 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-05Added FoldingSet profiling support to ImmutableSet.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46757 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-05Changed profiling method for ImmutableMap to once again just use itsTed Kremenek
unique ImutAVLTree* for profiling. Modified ImutAVLTree: (1) changed ComputeHash() to ComputeDigest() and (2) changed Profile() to use the computed digest and (3) modified insertion of IMutAVLTree into the FoldingSet owned by the ImutAVLTreeFactory object to use profiling instead of computing a direct hash. This fixes a bug where our abuse of the FoldingSet would not work when the FoldingSet was resized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46753 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-04Modified node creation of ImutAVLTree to do a hash lookup for an existingTed Kremenek
node in the FoldingSet of nodes held by the Factory object. If we we find a node with a matching hash, we do a full structural comparison. Nodes are also now inserted into the FoldingSet only when we mark them Immutable, as their children can change during intermediate-rebalancing. The 'Profile' method for ImutAVLTree is no longer used when looking up existing ImutAVLTrees with a given set of contents; instead the Profile method is used by other clients that wish to insert such a tree into a folding set. This means that we are not using FoldingSet in ImutAVLTreeFactory in the way it was intended, but instead are using it as an opaque hashtable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46717 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-23Added "getRoot()" to ImmutableSet. Ted Kremenek
Made ImmutableSet::ImmutableSet(ImutAVLTree* Root) public. (this allows handy casting between trees and sets). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46277 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-21Fixed buggy caching of the hash value of an ImutAVLTree node.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46229 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-21Moved method call within a conditional branch because its effects willTed Kremenek
be ignored on the false branch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46228 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-21Adjusted ImutAVLTree::ComputeHash to compute a hash value that is based on aTed Kremenek
clearer sequence of hashing compositions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46227 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-06 03:28:27 +0000