1 /*
2 * Copyright (C) 2010 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 "VisitedLinkTable.h"
28
29 #include "SharedMemory.h"
30
31 using namespace WebCore;
32
33 namespace WebKit {
34
VisitedLinkTable()35 VisitedLinkTable::VisitedLinkTable()
36 : m_tableSize(0)
37 , m_table(0)
38 {
39 }
40
~VisitedLinkTable()41 VisitedLinkTable::~VisitedLinkTable()
42 {
43 }
44
isPowerOf2(unsigned v)45 static inline bool isPowerOf2(unsigned v)
46 {
47 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
48
49 return !(v & (v - 1)) && v;
50 }
51
setSharedMemory(PassRefPtr<SharedMemory> sharedMemory)52 void VisitedLinkTable::setSharedMemory(PassRefPtr<SharedMemory> sharedMemory)
53 {
54 m_sharedMemory = sharedMemory;
55
56 ASSERT(m_sharedMemory);
57 ASSERT(!(m_sharedMemory->size() % sizeof(LinkHash)));
58
59 m_table = static_cast<LinkHash*>(m_sharedMemory->data());
60 m_tableSize = m_sharedMemory->size() / sizeof(LinkHash);
61 ASSERT(isPowerOf2(m_tableSize));
62
63 m_tableSizeMask = m_tableSize - 1;
64 }
65
doubleHash(unsigned key)66 static inline unsigned doubleHash(unsigned key)
67 {
68 key = ~key + (key >> 23);
69 key ^= (key << 12);
70 key ^= (key >> 7);
71 key ^= (key << 2);
72 key ^= (key >> 20);
73 return key;
74 }
75
addLinkHash(LinkHash linkHash)76 bool VisitedLinkTable::addLinkHash(LinkHash linkHash)
77 {
78 ASSERT(m_sharedMemory);
79
80 int k = 0;
81 LinkHash* table = m_table;
82 int sizeMask = m_tableSizeMask;
83 unsigned h = static_cast<unsigned>(linkHash);
84 int i = h & sizeMask;
85
86 LinkHash* entry;
87 while (1) {
88 entry = table + i;
89
90 // Check if this bucket is empty.
91 if (!*entry)
92 break;
93
94 // Check if the same link hash is in the table already.
95 if (*entry == linkHash)
96 return false;
97
98 if (!k)
99 k = 1 | doubleHash(h);
100 i = (i + k) & sizeMask;
101 }
102
103 *entry = linkHash;
104 return true;
105 }
106
isLinkVisited(LinkHash linkHash) const107 bool VisitedLinkTable::isLinkVisited(LinkHash linkHash) const
108 {
109 if (!m_sharedMemory)
110 return false;
111
112 int k = 0;
113 LinkHash* table = m_table;
114 int sizeMask = m_tableSizeMask;
115 unsigned h = static_cast<unsigned>(linkHash);
116 int i = h & sizeMask;
117
118 LinkHash* entry;
119 while (1) {
120 entry = table + i;
121
122 // Check if we've reached the end of the table.
123 if (!*entry)
124 break;
125
126 if (*entry == linkHash)
127 return true;
128
129 if (!k)
130 k = 1 | doubleHash(h);
131 i = (i + k) & sizeMask;
132 }
133
134 return false;
135 }
136
137 } // namespace WebKit
138