aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT/ImmutableMap.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-07Mark ImmutableMap::remove/add() const.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169629 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-07Add manualRetain() and manualRelease() to ImmutableMapRef, and add a new ↵Ted Kremenek
constructor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169572 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-06Revert "Allow modifying an ImmutableMap without canonicalizing it immediately."Ted Kremenek
Jordan and I discussed this, and we don't want this in the API. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169541 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-06Allow modifying an ImmutableMap without canonicalizing it immediately.Jordan Rose
This is an alternative to the ImmutableMapRef interface where a factory should still be canonicalizing by default, but in certain cases an improvement can be made by delaying the canonicalization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169532 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
2011-09-23Add getTreeFactory() to ImmutableSet to allow construction of ↵Anna Zaks
ImmutableSetRef from an ImmutableSet object. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140402 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
2011-02-22Fix C++0x incompatibility. The signature of std::make_pair<> changes from:Nick Lewycky
template <class T1, class T2> pair<T1,T2> make_pair(const T1&, const T2&); to template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&); so explicitly specifying the template arguments to make_pair<> is going to break when C++0x rolls through. Replace them with equivalent std::pair<>. Patch by James Dennett! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126256 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19Add ImmutableMap methods 'manualRetain()', 'manualRelease()', and ↵Ted Kremenek
'getRootWithoutRetain()' to help more aggressively reclaim memory in the static analyzer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126011 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-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-02-0211.8p1: A nested class is a member and as such has the same access rights asZhongxing Xu
any other member. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95047 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-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
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-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-02-23Correctly implement ImmutableMap::getMaxElement() by getting the actual ↵Ted Kremenek
<key, value> pair. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65327 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-20Fixed lint errors:Misha Brukman
* Alphabetized #includes * Removed trailing whitespace * Wrapped or shortened lines over 80 chars git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65181 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-08-14Removed redundant ctor.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54789 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-10Added ImmutableMap constructor that accepts a const TreeTy*.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53429 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-07Removed ImmutableMap::SlimFind and replaced it with ImmutableMap::lookup. ↵Ted Kremenek
The new method does the same thing, except that it returns a pointer to the mapped data type, and not to an internal tree node. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53171 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-03Implement operator-> for ImmutableMap iterators.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50603 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-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 'Profile' method of ImmutableMap to use the 'Profile' methodTed Kremenek
of the contained ImutAVLTree root. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46719 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-18Reverted implementation of ImmutableMap::find() to return a TreeTy* instead ofTed Kremenek
an iterator, since the implementation returned an iterator that pointed to a different node! Renamed this implementation to SlimFind() so that users do not expect it to return an iterator (it is a more efficient implementation than returning an iterator if the user just wants to find the value of a key). Added a FIXME to implement ImmutableMap::find() that returns an iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46150 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-17Implemented "FIXME" in ImutAVLTree: isEqual() now also compares the *data* valueTed Kremenek
and not just the key value when comparing trees. To do this we added data_type and data_type_ref to the ImutContainerInfo trait classes. For values stored in the tree that do not have separate key and data components, data_type is simply a typedef of bool, and isDataEqual() always evaluates to true. This allows us to support both ImmutableSet and ImmutableMap using the same underlying logic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46130 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-15Changed ImmutableMap::find to return an iterator instead of a pointerTed Kremenek
to the tree node. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46034 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-08Added "getRoot()" to ImmutableMap.Ted Kremenek
Made the ctor for ImmutableMap to construct a map from an AVL tree public. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45756 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-08Fixed 80 col. violation.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45752 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-02Inverted argument order for ImmutableMap::Profile.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45507 91177308-0d34-0410-b5e6-96231b3b80d8
2008-01-02Added iterator and profiling (i.e. FoldingSetNodeID) support to ImmutableMap.Ted Kremenek
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45503 91177308-0d34-0410-b5e6-96231b3b80d8
2007-12-29Don't attribute in file headers anymore. See llvmdev for theChris Lattner
discussion of this change. Boy are my fingers tired. ;-) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45411 91177308-0d34-0410-b5e6-96231b3b80d8
2007-10-09Added implementation of immutable (functional) maps and sets, asTed Kremenek
implemented on top of a functional AVL tree. The AVL balancing code is inspired by the OCaml implementation of Map, which also uses a functional AVL tree. Documentation is currently limited and cleanups are planned, but this code compiles and has been tested. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42813 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-22 17:04:16 +0000