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