hphp/runtime/vm/fixed_string_map.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/vm/core_types.h"
  18 #include "hphp/runtime/vm/fixed_string_map.h"
  19 #include "hphp/runtime/base/macros.h"
  20
  21 namespace HPHP {
  22
  23 TRACE_SET_MOD(runtime);
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26
  27 class Func;
  28
  29 inline bool strEqual(bool case_sensitive,
  30                      const StringData* sd1, const StringData* sd2) {
  31   if (sd1 == sd2) return true;
  32   if (sd1->size() != sd2->size()) return false;
  33   return case_sensitive ?
  34       (0 == memcmp(sd1->data(), sd2->data(), sd1->size())) :
  35       bstrcaseeq(sd1->data(), sd2->data(), sd1->size());
  36 }
  37
  38 template <typename V, bool case_sensitive>
  39 void FixedStringMap<V, case_sensitive>::init(int num) {
  40   static const double kLoadFactor = 0.80;
  41   int capac = 1;
  42   while (num >= kLoadFactor * capac) {
  43     capac *= 2;
  44   }
  45   TRACE(1, "FixedStringMap::init: %d -> %d\n", num, capac);
  46   assert(!m_table);
  47   m_table = (Elm*)calloc(capac * sizeof(Elm), 1);
  48   assert(m_table);
  49   m_mask = capac - 1;
  50 }
  51
  52 template <typename V, bool case_sensitive>
  53 void FixedStringMap<V, case_sensitive>::add(const StringData* sd, const V& v) {
  54   assert(sd->isStatic());
  55
  56   Elm* elm = &m_table[sd->hash() & m_mask];
  57   UNUSED unsigned numProbes = 0;
  58   while (elm->sd) {
  59     assert(numProbes++ < m_mask + 1);
  60     // Semantics for multiple insertion: new value wins.
  61     if (strEqual(case_sensitive, elm->sd, sd)) break;
  62     if (UNLIKELY(++elm == &m_table[m_mask + 1])) elm = m_table;
  63   }
  64   elm->sd = sd;
  65   elm->data = v;
  66 }
  67
  68 template <typename V, bool case_sensitive>
  69 V* FixedStringMap<V, case_sensitive>::find(const StringData* sd) const {
  70   Elm* elm = &m_table[sd->hash() & m_mask];
  71   UNUSED unsigned numProbes = 0;
  72   for(;;) {
  73     assert(numProbes++ < m_mask + 1);
  74     if (UNLIKELY(nullptr == elm->sd)) return nullptr;
  75     if (strEqual(case_sensitive, elm->sd, sd)) return &elm->data;
  76     if (UNLIKELY(++elm == &m_table[m_mask + 1])) elm = m_table;
  77   }
  78 }
  79
  80 template class FixedStringMap<Slot, false>;
  81 template class FixedStringMap<Slot, true>;
  82 template class FixedStringMap<Id, false>;
  83 template class FixedStringMap<Id, true>;
  84 template class FixedStringMap<Func*, false>;
  85 template class FixedStringMap<unsigned char* /* TCA */, true>;
  86
  87 ///////////////////////////////////////////////////////////////////////////////
  88
  89  }