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.
38template <int kSize>
39class PtrToBoolCache {
40 public:
41  PtrToBoolCache() {
42    Flush();
43  }
44  void Flush() {
45    memset(this, 0, sizeof(*this));
46  }
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  }
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.
72template <int32_t kSize>
73class IntPairToBoolCache {
74 public:
75  IntPairToBoolCache() {
76    Flush();
77  }
78  void Flush() {
79    memset(arr_, 0, sizeof(arr_));
80  }
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  }
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:
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