1 /* Copyright (c) 2008-2010, Google Inc. 2 * All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Neither the name of Google Inc. nor the names of its 11 * contributors may be used to endorse or promote products derived from 12 * this software without specific prior written permission. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 // This file is part of ThreadSanitizer, a dynamic data race detector. 28 // Author: Konstantin Serebryany. 29 // Author: Timur Iskhodzhanov. 30 #ifndef TS_SIMPLE_CACHE_ 31 #define TS_SIMPLE_CACHE_ 32 33 #include "ts_util.h" 34 35 // Few simple 'cache' classes. 36 // -------- PtrToBoolCache ------ {{{1 37 // Maps a pointer to a boolean. 38 template <int kSize> 39 class PtrToBoolCache { 40 public: PtrToBoolCache()41 PtrToBoolCache() { 42 Flush(); 43 } Flush()44 void Flush() { 45 memset(this, 0, sizeof(*this)); 46 } Insert(uintptr_t ptr,bool val)47 void Insert(uintptr_t ptr, bool val) { 48 size_t idx = ptr % kSize; 49 arr_[idx] = ptr; 50 if (val) { 51 bits_[idx / 32] |= 1U << (idx % 32); 52 } else { 53 bits_[idx / 32] &= ~(1U << (idx % 32)); 54 } 55 } Lookup(uintptr_t ptr,bool * val)56 bool Lookup(uintptr_t ptr, bool *val) { 57 size_t idx = ptr % kSize; 58 if (arr_[idx] == ptr) { 59 *val = (bits_[idx / 32] >> (idx % 32)) & 1; 60 return true; 61 } 62 return false; 63 } 64 private: 65 uintptr_t arr_[kSize]; 66 uint32_t bits_[(kSize + 31) / 32]; 67 }; 68 69 // -------- IntPairToBoolCache ------ {{{1 70 // Maps two integers to a boolean. 71 // The second integer should be less than 1^31. 72 template <int32_t kSize> 73 class IntPairToBoolCache { 74 public: IntPairToBoolCache()75 IntPairToBoolCache() { 76 Flush(); 77 } Flush()78 void Flush() { 79 memset(arr_, 0, sizeof(arr_)); 80 } Insert(uint32_t a,uint32_t b,bool val)81 void Insert(uint32_t a, uint32_t b, bool val) { 82 DCHECK((int32_t)b >= 0); 83 uint32_t i = idx(a, b); 84 if (val) { 85 b |= 1U << 31; 86 } 87 arr_[i * 2 + 0] = a; 88 arr_[i * 2 + 1] = b; 89 } Lookup(uint32_t a,uint32_t b,bool * val)90 bool Lookup(uint32_t a, uint32_t b, bool *val) { 91 DCHECK((int32_t)b >= 0); 92 uint32_t i = idx(a, b); 93 if (arr_[i * 2] != a) return false; 94 uint32_t maybe_b = arr_[i * 2 + 1]; 95 if (b == (maybe_b & (~(1U << 31)))) { 96 *val = (maybe_b & (1U << 31)) != 0; 97 return true; 98 } 99 return false; 100 } 101 private: idx(uint32_t a,uint32_t b)102 uint32_t idx(uint32_t a, uint32_t b) { 103 return (a ^ ((b >> 16) | (b << 16))) % kSize; 104 } 105 uint32_t arr_[kSize * 2]; 106 }; 107 108 // end. {{{1 109 #endif // TS_SIMPLE_CACHE_ 110 // vim:shiftwidth=2:softtabstop=2:expandtab:tw=80 111