Source/WebKit2/Shared/VisitedLinkTable.cpp

   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