aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/ADT/ImmutableSet.h
Commit message (Collapse)AuthorAgeFilesLines
* Fix -Asserts warnings.Daniel Dunbar2010-04-131-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101191 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an immutable interval map, prepared to be used by flat memory model Zhongxing Xu2010-02-011-1/+3
| | | | | | | in the analyzer. WIP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94976 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify code. We can compare TNew with T in one batch.Zhongxing Xu2010-02-011-14/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94973 91177308-0d34-0410-b5e6-96231b3b80d8
* Store flags in bitfields instead of masking them into the pointer for the ↵Ted Kremenek2010-01-221-26/+22
| | | | | | 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
* Tidy up assertion syntax. No functionality change.Ted Kremenek2010-01-211-35/+30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94117 91177308-0d34-0410-b5e6-96231b3b80d8
* Make a few more LLVM headers parsable as standalone headers.Douglas Gregor2009-11-051-2/+2
| | | | | | | | | 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
* Move DataTypes.h to include/llvm/System, update all users. This breaks the lastChandler Carruth2009-10-261-1/+1
| | | | | | | direct inclusion edge from System to Support. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85086 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete bogus semicolons.Dan Gohman2009-10-141-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84132 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide a mode for ImmutableMap/ImmutableSet to not automatically ↵Ted Kremenek2009-10-131-6/+12
| | | | | | 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
* Make ImmutableMap/ImmutableSet quicker by only canonicalizing the tree after anTed Kremenek2009-09-031-59/+57
| | | | | | | | 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
* Set the 'cached digest' flag after computing the digest for anTed Kremenek2009-09-031-0/+1
| | | | | | | | | | | | | | 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
* Make default ctor for ImmutableSet::iterator public.Ted Kremenek2009-08-011-2/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77762 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove redundant qualifiers.Daniel Dunbar2009-07-191-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76357 91177308-0d34-0410-b5e6-96231b3b80d8
* ImmutableMap/ImmutableSet: Allow caching of ImutAVLTree digests while the treeTed Kremenek2009-07-101-21/+12
| | | | | | | | | 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
* ImmutableSet/ImmutableMap: Allow caching of null digests by properly using a ↵Ted Kremenek2009-07-091-37/+45
| | | | | | 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
* Add ImmutableMap::getMaxElement(), a method that returns the <key,value> ↵Ted Kremenek2009-02-231-0/+9
| | | | | | 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
* Removed trailing whitespace.Misha Brukman2009-02-201-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65197 91177308-0d34-0410-b5e6-96231b3b80d8
* Add operator->, patch by Ben Laurie!Chris Lattner2009-02-121-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64378 91177308-0d34-0410-b5e6-96231b3b80d8
* Add method 'isSingleton()' to ImmutableSet. This returns true if the set ↵Ted Kremenek2009-02-121-1/+4
| | | | | | contains exactly one element. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64359 91177308-0d34-0410-b5e6-96231b3b80d8
* Removed trailing whitespace.Misha Brukman2009-01-091-272/+272
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62000 91177308-0d34-0410-b5e6-96231b3b80d8
* TypoNick Lewycky2008-11-031-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58594 91177308-0d34-0410-b5e6-96231b3b80d8
* Unbreak build for VC2008. Patch by Argiris Kirtzidis!Anton Korobeynikov2008-02-221-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47480 91177308-0d34-0410-b5e6-96231b3b80d8
* The factories for ImutAVLTree/ImmutableSet/ImmutableMap now take an (optional)Ted Kremenek2008-02-111-6/+25
| | | | | | | | | 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
* Added FoldingSet profiling support to ImmutableSet.Ted Kremenek2008-02-051-1/+14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46757 91177308-0d34-0410-b5e6-96231b3b80d8
* Changed profiling method for ImmutableMap to once again just use itsTed Kremenek2008-02-051-25/+28
| | | | | | | | | | | | | | | 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
* Modified node creation of ImutAVLTree to do a hash lookup for an existingTed Kremenek2008-02-041-77/+124
| | | | | | | | | | | | | | | | 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
* Added "getRoot()" to ImmutableSet. Ted Kremenek2008-01-231-5/+10
| | | | | | | | | 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
* Fixed buggy caching of the hash value of an ImutAVLTree node.Ted Kremenek2008-01-211-3/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46229 91177308-0d34-0410-b5e6-96231b3b80d8
* Moved method call within a conditional branch because its effects willTed Kremenek2008-01-211-1/+1
| | | | | | | be ignored on the false branch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46228 91177308-0d34-0410-b5e6-96231b3b80d8
* Adjusted ImutAVLTree::ComputeHash to compute a hash value that is based on aTed Kremenek2008-01-211-3/+16
| | | | | | | clearer sequence of hashing compositions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46227 91177308-0d34-0410-b5e6-96231b3b80d8
* Replaced (FoldingSet) profiling of ImutAVLTree with a hashing based scheme. TheTed Kremenek2008-01-211-6/+23
| | | | | | | | | | | | | | problem was that we previously hashed based on the pointers of the left and right children, but this is bogus: we can easily have different trees that represent the same set. Now we use a hashing based scheme that compares the *contents* of the trees, but not without having to do a full scan of a tree. The only caveat is that with hashing is that we may have collisions, which result in two different trees being falsely labeled as equivalent. If this becomes a problem, we can add extra data to the profile to hopefully resolve most collisions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46224 91177308-0d34-0410-b5e6-96231b3b80d8
* Modified ImmutableSet/ImmutableMap to use FoldingSet profiling usingTed Kremenek2008-01-191-2/+2
| | | | | | | FoldingSetTrait instead of directly calling a 'Profile' method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46190 91177308-0d34-0410-b5e6-96231b3b80d8
* Implemented "FIXME" in ImutAVLTree: isEqual() now also compares the *data* valueTed Kremenek2008-01-171-2/+16
| | | | | | | | | | | 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
* Don't attribute in file headers anymore. See llvmdev for theChris Lattner2007-12-291-2/+2
| | | | | | | | 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
* Changed the return type of type-specific Allocate() methods to returnTed Kremenek2007-10-181-1/+1
| | | | | | | | | | void*. This is hint that we are returning uninitialized memory rather than a constructed object. Patched ImutAVLTree to conform to this new interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43106 91177308-0d34-0410-b5e6-96231b3b80d8
* ImutAVLTree now allocates tree nodes from the BumpPtrAllocator usingTed Kremenek2007-10-171-4/+3
| | | | | | | the new type-aligned Allocate() method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43100 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed incorrect renaming of method name (forgot two characters).Ted Kremenek2007-10-151-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42999 91177308-0d34-0410-b5e6-96231b3b80d8
* Added more doxygen comments.Ted Kremenek2007-10-151-19/+56
| | | | | | | | Renamed internal method of ImutAVLTree::RemoveMutableFlag to MarkImmutable. Added enum for bit manipulation (more self-documentating). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42998 91177308-0d34-0410-b5e6-96231b3b80d8
* Provided accessors to internal allocator for ImutAVLTree and ImmutableSet.Ted Kremenek2007-10-111-0/+7
| | | | | | | Added postfix ++,-- support for ImmutableSet::iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42877 91177308-0d34-0410-b5e6-96231b3b80d8
* Added iterators to ImmutableSet.Ted Kremenek2007-10-111-3/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42851 91177308-0d34-0410-b5e6-96231b3b80d8
* Added some doxygen comments to ImmutableSet.Ted Kremenek2007-10-101-1/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42850 91177308-0d34-0410-b5e6-96231b3b80d8
* Removed uninformative assertions that catch problems that willTed Kremenek2007-10-101-22/+5
| | | | | | | fire anyway at runtime due to a NULL dereference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42848 91177308-0d34-0410-b5e6-96231b3b80d8
* Removed "height" of an AVL tree node from its Profile. This isTed Kremenek2007-10-101-7/+4
| | | | | | | | implicitly captured by using the addresses of its children in the profile. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42847 91177308-0d34-0410-b5e6-96231b3b80d8
* Removed spurious forward declaration to a structure that will no longer be used.Ted Kremenek2007-10-101-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42839 91177308-0d34-0410-b5e6-96231b3b80d8
* Added some doxygen comments to a few methods of ImutAVLTree.Ted Kremenek2007-10-101-2/+41
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42837 91177308-0d34-0410-b5e6-96231b3b80d8
* Added preliminary support for iterators in ImutAVLTree.Ted Kremenek2007-10-101-4/+218
| | | | | | | Implemented ImutAVLTree::isEqual. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42833 91177308-0d34-0410-b5e6-96231b3b80d8
* Renamed internal method "Create" of ImutAVLTree to "CreateNode".Ted Kremenek2007-10-101-13/+14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42825 91177308-0d34-0410-b5e6-96231b3b80d8
* Added implementation of immutable (functional) maps and sets, asTed Kremenek2007-10-091-0/+608
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.1 at 2024-08-02 08:44:08 +0000