Home | History | Annotate | Download | only in Shared 
      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