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 35 VisitedLinkTable::VisitedLinkTable() 36 : m_tableSize(0) 37 , m_table(0) 38 { 39 } 40 41 VisitedLinkTable::~VisitedLinkTable() 42 { 43 } 44 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 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 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 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 107 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