summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Support/StringMap.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Use uniform mechanism for OOM errors handlingSerge Pavlov2018-06-091-6/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a recommit of r333506, which was reverted in r333518. The original commit message is below. In r325551 many calls of malloc/calloc/realloc were replaces with calls of their safe counterparts defined in the namespace llvm. There functions generate crash if memory cannot be allocated, such behavior facilitates handling of out of memory errors on Windows. If the result of *alloc function were checked for success, the function was not replaced with the safe variant. In these cases the calling function made the error handling, like: T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); if (NewElts == nullptr) report_bad_alloc_error("Allocation of SmallVector element failed."); Actually knowledge about the function where OOM occurred is useless. Moreover having a single entry point for OOM handling is convenient for investigation of memory problems. This change removes custom OOM errors handling and replaces them with calls to functions `llvm::safe_*alloc`. Declarations of `safe_*alloc` are moved to a separate include file, to avoid cyclic dependency in SmallVector.h Differential Revision: https://reviews.llvm.org/D47440 llvm-svn: 334344
* Revert commit 333506Serge Pavlov2018-05-301-2/+6
| | | | | | | It looks like this commit is responsible for the fail: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/24382. llvm-svn: 333518
* Use uniform mechanism for OOM errors handlingSerge Pavlov2018-05-301-6/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a recommit of r333390, which was reverted in r333395, because it caused cyclic dependency when building shared library `LLVMDemangle.so`. In this commit `ItaniumDemangler.cpp` was not changed. The original commit message is below. In r325551 many calls of malloc/calloc/realloc were replaces with calls of their safe counterparts defined in the namespace llvm. There functions generate crash if memory cannot be allocated, such behavior facilitates handling of out of memory errors on Windows. If the result of *alloc function were checked for success, the function was not replaced with the safe variant. In these cases the calling function made the error handling, like: T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); if (NewElts == nullptr) report_bad_alloc_error("Allocation of SmallVector element failed."); Actually knowledge about the function where OOM occurred is useless. Moreover having a single entry point for OOM handling is convenient for investigation of memory problems. This change removes custom OOM errors handling and replaces them with calls to functions `llvm::safe_*alloc`. Declarations of `safe_*alloc` are moved to a separate include file, to avoid cyclic dependency in SmallVector.h Differential Revision: https://reviews.llvm.org/D47440 llvm-svn: 333506
* Reverted commits 333390, 333391 and 333394Serge Pavlov2018-05-291-2/+6
| | | | | | Build of shared library LLVMDemangle.so fails due to dependency problem. llvm-svn: 333395
* Use uniform mechanism for OOM errors handlingSerge Pavlov2018-05-291-6/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | In r325551 many calls of malloc/calloc/realloc were replaces with calls of their safe counterparts defined in the namespace llvm. There functions generate crash if memory cannot be allocated, such behavior facilitates handling of out of memory errors on Windows. If the result of *alloc function were checked for success, the function was not replaced with the safe variant. In these cases the calling function made the error handling, like: T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); if (NewElts == nullptr) report_bad_alloc_error("Allocation of SmallVector element failed."); Actually knowledge about the function where OOM occurred is useless. Moreover having a single entry point for OOM handling is convenient for investigation of memory problems. This change removes custom OOM errors handling and replaces them with calls to functions `llvm::safe_*alloc`. Declarations of `safe_*alloc` are moved to a separate include file, to avoid cyclic dependency in SmallVector.h Differential Revision: https://reviews.llvm.org/D47440 llvm-svn: 333390
* Re-land: "[Support] Replace HashString with djbHash."Jonas Devlieghere2018-02-261-19/+20
| | | | | | | | | | | | | | | | | | | | | This patch removes the HashString function from StringExtraces and replaces its uses with calls to djbHash from DJB.h. This change is *almost* NFC. While the algorithm is identical, the djbHash implementation in StringExtras used 0 as its default seed while the implementation in DJB uses 5381. The latter has been shown to result in less collisions and improved avalanching and is used by the DWARF accelerator tables. Because some test were implicitly relying on the hash order, I've reverted to using zero as a seed for the following two files: lld/include/lld/Core/SymbolTable.h llvm/lib/Support/StringMap.cpp Differential revision: https://reviews.llvm.org/D43615 llvm-svn: 326091
* Revert "[Support] Replace HashString with djbHash."Jonas Devlieghere2018-02-261-20/+19
| | | | | | | | | | | | | It looks like some of our tests depend on the ordering of hashed values. I'm reverting my changes while I try to reproduce and fix this locally. Failing builds: lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/18388 lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/6743 lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/15607 llvm-svn: 326082
* [Support] Replace HashString with djbHash.Jonas Devlieghere2018-02-261-19/+20
| | | | | | | | | | | | | | | This removes the HashString function from StringExtraces and replaces its uses with calls to djbHash from DJB.h This is *almost* NFC. While the algorithm is identical, the djbHash implementation in StringExtras used 0 as its seed while the implementation in DJB uses 5381. The latter has been shown to result in less collisions and improved avalanching. https://reviews.llvm.org/D43615 (cherry picked from commit 77f7f965bc9499a9ae768a296ca5a1f7347d1d2c) llvm-svn: 326081
* Report fatal error in the case of out of memorySerge Pavlov2018-02-201-8/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is the second part of recommit of r325224. The previous part was committed in r325426, which deals with C++ memory allocation. Solution for C memory allocation involved functions `llvm::malloc` and similar. This was a fragile solution because it caused ambiguity errors in some cases. In this commit the new functions have names like `llvm::safe_malloc`. The relevant part of original comment is below, updated for new function names. Analysis of fails in the case of out of memory errors can be tricky on Windows. Such error emerges at the point where memory allocation function fails, but manifests itself when null pointer is used. These two points may be distant from each other. Besides, next runs may not exhibit allocation error. In some cases memory is allocated by a call to some of C allocation functions, malloc, calloc and realloc. They are used for interoperability with C code, when allocated object has variable size and when it is necessary to avoid call of constructors. In many calls the result is not checked for null pointer. To simplify checks, new functions are defined in the namespace 'llvm': `safe_malloc`, `safe_calloc` and `safe_realloc`. They behave as corresponding standard functions but produce fatal error if allocation fails. This change replaces the standard functions like 'malloc' in the cases when the result of the allocation function is not checked for null pointer. Finally, there are plain C code, that uses malloc and similar functions. If the result is not checked, assert statement is added. Differential Revision: https://reviews.llvm.org/D43010 llvm-svn: 325551
* Revert r325224 "Report fatal error in the case of out of memory"Serge Pavlov2018-02-151-5/+8
| | | | | | It caused fails on some buildbots. llvm-svn: 325227
* Report fatal error in the case of out of memorySerge Pavlov2018-02-151-8/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Analysis of fails in the case of out of memory errors can be tricky on Windows. Such error emerges at the point where memory allocation function fails, but manifests itself when null pointer is used. These two points may be distant from each other. Besides, next runs may not exhibit allocation error. Usual programming practice does not require checking result of 'operator new' because it throws 'std::bad_alloc' in the case of allocation error. However, LLVM is usually built with exceptions turned off, so 'new' can return null pointer. This change installs custom new handler, which causes fatal error in the case of out of memory. The handler is installed automatically prior to call to 'main' during construction of a static object defined in 'lib/Support/ErrorHandling.cpp'. If the application does not use this file, the handler may be installed manually by a call to 'llvm::install_out_of_memory_new_handler', declared in 'include/llvm/Support/ErrorHandling.h". There are calls to C allocation functions, malloc, calloc and realloc. They are used for interoperability with C code, when allocated object has variable size and when it is necessary to avoid call of constructors. In many calls the result is not checked against null pointer. To simplify checks, new functions are defined in the namespace 'llvm' with the same names as these C function. These functions produce fatal error if allocation fails. User should use 'llvm::malloc' instead of 'std::malloc' in order to use the safe variant. This change replaces 'std::malloc' in the cases when the result of allocation function is not checked against null pointer. Finally, there are plain C code, that uses malloc and similar functions. If the result is not checked, assert statements are added. Differential Revision: https://reviews.llvm.org/D43010 llvm-svn: 325224
* Support, IR, ADT: Check nullptr after allocation with malloc/realloc or callocMatthias Braun2017-07-201-2/+13
| | | | | | | | | | | | As a follow up of the bad alloc handler patch, this patch introduces nullptr checks on pointers returned from the malloc/realloc/calloc functions. In addition some memory size assignments are moved behind the allocation of the corresponding memory to fulfill exception safe memory management (RAII). patch by Klaus Kretzschmar Differential Revision: https://reviews.llvm.org/D35414 llvm-svn: 308576
* Fix some Clang-tidy modernize-use-using and Include What You Use warnings; ↵Eugene Zelenko2016-08-231-6/+4
| | | | | | | | other minor fixes. Differential revision: https://reviews.llvm.org/D23789 llvm-svn: 279535
* Adjust initial size in StringMap constructor to guarantee no grow()Mehdi Amini2016-03-251-1/+15
| | | | | | | | | | | | | | | | | | Summary: StringMap ctor accepts an initialize size, but expect it to be rounded to the next power of 2. The ctor can handle that directly instead of expecting clients to round it. Also, since the map will resize itself when 75% full, take this into account an initialize a larger initial size to avoid any growth. Reviewers: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18344 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 264385
* Sync the __builtin_expects for our 3 quadratically probed hash table ↵Benjamin Kramer2015-02-231-2/+3
| | | | | | | | | | | | | | | | | | implementations. This assumes that a) finding the bucket containing the value is LIKELY b) finding an empty bucket is LIKELY c) growing the table is UNLIKELY I also switched the a) and b) cases for SmallPtrSet as we seem to use the set mostly more for insertion than for checking existence. In a simple benchmark consisting of 2^21 insertions of 2^20 unique pointers into a DenseMap or SmallPtrSet a few percent speedup on average, but nothing statistically significant. llvm-svn: 230232
* Recommit 211309 (StringMap::insert), reverted in 211328 due to issues with ↵David Blaikie2014-06-231-2/+8
| | | | | | | | | | | | private, but non-deleted, move members. Certain versions of GCC (~4.7) couldn't handle the SFINAE on access control, but with "= delete" (hidden behind a macro for portability) this issue is worked around/addressed. Patch by Agustín Bergé llvm-svn: 211525
* Revert "Add StringMap::insert(pair) consistent with the standard associative ↵Rafael Espindola2014-06-201-8/+2
| | | | | | | | | | | | container concept." This reverts commit r211309. It looks like it broke some bots: http://lab.llvm.org:8011/builders/clang-x86_64-ubuntu-gdb-75/builds/15563/steps/compile/logs/stdio llvm-svn: 211328
* Add StringMap::insert(pair) consistent with the standard associative ↵David Blaikie2014-06-191-2/+8
| | | | | | | | container concept. Patch by Agustín Bergé. llvm-svn: 211309
* [C++11] Replace some comparisons with 'nullptr' with simple boolean checks ↵Craig Topper2014-04-091-3/+3
| | | | | | to reduce verbosity. llvm-svn: 205829
* [C++11] Make use of 'nullptr' in the Support library.Craig Topper2014-04-071-5/+5
| | | | llvm-svn: 205697
* Add some __builtin_expect magic to StringMap.Benjamin Kramer2012-08-291-4/+5
| | | | | | | | | Tombstones and full hash collisions are rare, mark the "empty" and "no collision" paths as likely. The bug in simplifycfg that prevented the hints from being picked during selfhost up was fixed recently :) llvm-svn: 162874
* Fix PR13148, an inf-loop in StringMap.Chandler Carruth2012-06-191-1/+1
| | | | | | | | | | | | | | | StringMap suffered from the same bug as DenseMap: when you explicitly construct it with a small number of buckets, you can arrange for the tombstone-based growth path to be followed when the number of buckets was less than '8'. In that case, even with a full map, it would compare '0' as not less than '0', and refuse to grow the table, leading to inf-loops trying to find an empty bucket on the next insertion. The fix is very simple: use '<=' as the comparison. The same fix was applied to DenseMap as well during its recent refactoring. Thanks to Alex Bolz for the great report and test case. =] llvm-svn: 158725
* Switch StringMap from an array of structures to a structure of arrays.Benjamin Kramer2011-12-271-27/+34
| | | | | | | - -25% memory usage of the main table on x86_64 (was wasted in struct padding). - no significant performance change. llvm-svn: 147294
* Reset StringMap's NumTombstones on clears and rehashes.Jakob Stoklund Olesen2011-03-301-0/+3
| | | | | | | | | | | | | StringMap was not properly updating NumTombstones after a clear or rehash. This was not fatal until now because the table was growing faster than NumTombstones could, but with the previous change of preventing infinite growth of the table the invariant (NumItems + NumTombstones <= NumBuckets) stopped being observed, causing infinite loops in certain situations. Patch by José Fonseca! llvm-svn: 128567
* Prevent infinite growth of SmallMap instances.Jakob Stoklund Olesen2011-03-301-1/+13
| | | | | | | | Rehash but don't grow when full of tombstones. Patch by José Fonseca! llvm-svn: 128565
* Change all self assignments X=X to (void)X, so that we can turn on aJeffrey Yasskin2010-12-231-1/+1
| | | | | | | new gcc warning that complains on self-assignments and self-initializations. llvm-svn: 122458
* Pass StringRef by value.Daniel Dunbar2009-11-061-3/+3
| | | | llvm-svn: 86251
* Move StringMap's string has function into StringExtras.hDaniel Dunbar2009-10-171-16/+3
| | | | llvm-svn: 84344
* Convert StringMap to using StringRef for its APIs.Daniel Dunbar2009-07-231-16/+10
| | | | | | | | | | | | - Yay for '-'s and simplifications! - I kept StringMap::GetOrCreateValue for compatibility purposes, this can eventually go away. Likewise the StringMapEntry Create functions still follow the old style. - NIFC. llvm-svn: 76888
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
* stringmap memory managed with malloc nowChris Lattner2007-04-041-1/+1
| | | | llvm-svn: 35666
* use calloc instead of new/memset, it is more efficientChris Lattner2007-04-041-4/+2
| | | | llvm-svn: 35644
* Extend StringMap to support being initialized as completely empty. WhenChris Lattner2007-04-041-2/+22
| | | | | | initialized this way, they do not do a malloc to allocate their buckets. llvm-svn: 35642
* greatly reduce hte default size of stringmap.Chris Lattner2007-04-031-1/+1
| | | | llvm-svn: 35632
* Add support for removing elements out of StringMap.Chris Lattner2007-02-111-11/+52
| | | | llvm-svn: 34185
* Replace the ugly FindValue method with STL-like find methods.Chris Lattner2007-02-111-0/+43
| | | | llvm-svn: 34183
* remove support for stringmap visitors now that iterators exist.Chris Lattner2007-02-111-13/+0
| | | | llvm-svn: 34180
* add support for iterators.Chris Lattner2007-02-111-2/+9
| | | | llvm-svn: 34179
* Rename CStringMap -> StringMap, since it now supports nul characters in theChris Lattner2007-02-081-0/+138
strings. llvm-svn: 34064
OpenPOWER on IntegriCloud