1 | /* |
2 | * Copyright (C) 2010-2017 Apple Inc. 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 |
6 | * are met: |
7 | * 1. Redistributions of source code must retain the above copyright |
8 | * notice, this list of conditions and the following disclaimer. |
9 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * |
13 | * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' |
14 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
15 | * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS |
17 | * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
18 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
19 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
20 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
21 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
22 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
23 | * THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #include "config.h" |
27 | #include "SharedStringHashTableReadOnly.h" |
28 | |
29 | #include "SharedMemory.h" |
30 | |
31 | namespace WebKit { |
32 | |
33 | using namespace WebCore; |
34 | |
35 | #if !ASSERT_DISABLED |
36 | static inline bool isPowerOf2(unsigned v) |
37 | { |
38 | // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html |
39 | |
40 | return !(v & (v - 1)) && v; |
41 | } |
42 | #endif |
43 | |
44 | static inline unsigned doubleHash(unsigned key) |
45 | { |
46 | key = ~key + (key >> 23); |
47 | key ^= (key << 12); |
48 | key ^= (key >> 7); |
49 | key ^= (key << 2); |
50 | key ^= (key >> 20); |
51 | return key; |
52 | } |
53 | |
54 | SharedStringHashTableReadOnly::SharedStringHashTableReadOnly() |
55 | { |
56 | } |
57 | |
58 | SharedStringHashTableReadOnly::~SharedStringHashTableReadOnly() |
59 | { |
60 | } |
61 | |
62 | void SharedStringHashTableReadOnly::setSharedMemory(RefPtr<SharedMemory>&& sharedMemory) |
63 | { |
64 | m_sharedMemory = WTFMove(sharedMemory); |
65 | |
66 | if (m_sharedMemory) { |
67 | ASSERT(!(m_sharedMemory->size() % sizeof(SharedStringHash))); |
68 | m_table = static_cast<SharedStringHash*>(m_sharedMemory->data()); |
69 | m_tableSize = m_sharedMemory->size() / sizeof(SharedStringHash); |
70 | ASSERT(isPowerOf2(m_tableSize)); |
71 | m_tableSizeMask = m_tableSize - 1; |
72 | } else { |
73 | m_table = nullptr; |
74 | m_tableSize = 0; |
75 | m_tableSizeMask = 0; |
76 | } |
77 | } |
78 | |
79 | bool SharedStringHashTableReadOnly::contains(SharedStringHash sharedStringHash) const |
80 | { |
81 | auto* slot = findSlot(sharedStringHash); |
82 | return slot && *slot; |
83 | } |
84 | |
85 | SharedStringHash* SharedStringHashTableReadOnly::findSlot(SharedStringHash sharedStringHash) const |
86 | { |
87 | if (!m_sharedMemory) |
88 | return nullptr; |
89 | |
90 | int k = 0; |
91 | SharedStringHash* table = m_table; |
92 | int sizeMask = m_tableSizeMask; |
93 | unsigned h = static_cast<unsigned>(sharedStringHash); |
94 | int i = h & sizeMask; |
95 | |
96 | SharedStringHash* entry; |
97 | while (1) { |
98 | entry = table + i; |
99 | |
100 | // Check if we've reached the end of the table. |
101 | if (!*entry) |
102 | return entry; |
103 | |
104 | if (*entry == sharedStringHash) |
105 | return entry; |
106 | |
107 | if (!k) |
108 | k = 1 | doubleHash(h); |
109 | i = (i + k) & sizeMask; |
110 | } |
111 | } |
112 | |
113 | } // namespace WebKit |
114 | |