hphp/runtime/vm/fixed-string-map.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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/fixed-string-map.h"
  18 #include "hphp/runtime/base/complex-types.h"
  19
  20 namespace HPHP {
  21
  22 TRACE_SET_MOD(runtime);
  23
  24 ///////////////////////////////////////////////////////////////////////////////
  25
  26 class Func;
  27
  28 static const StringData* null_key;
  29
  30 template<bool CaseSensitive>
  31 inline bool strEqual(const StringData* sd1, const StringData* sd2) {
  32   if (sd1 == sd2) return true;
  33   return CaseSensitive ? sd1->same(sd2) : sd1->isame(sd2);
  34 }
  35
  36 template<class V, bool CaseSensitive, class E>
  37 void FixedStringMap<V,CaseSensitive,E>::clear() {
  38   if (m_table && m_table != (Elm*)&null_key + 1) free(m_table - m_mask - 1);
  39   m_table = nullptr;
  40   m_mask = 0;
  41 }
  42
  43 template<class V, bool CaseSensitive, class E>
  44 void FixedStringMap<V,CaseSensitive,E>::init(int num, uint32_t numExtraBytes) {
  45   if (!num && !numExtraBytes) {
  46     m_table = (Elm*)&null_key + 1;
  47     m_mask = 0;
  48     return;
  49   }
  50
  51   static const double kLoadFactor = 0.80;
  52   int capac = 1;
  53   while (num >= kLoadFactor * capac) {
  54     capac *= 2;
  55   }
  56   TRACE(1, "FixedStringMap::init: %d -> %d\n", num, capac);
  57   assert(!m_table);
  58   m_table = (Elm*)calloc(capac * sizeof(Elm) + numExtraBytes, 1) + capac;
  59   assert(m_table);
  60   m_mask = capac - 1;
  61 }
  62
  63 template<class V, bool CaseSensitive, class E>
  64 void FixedStringMap<V,CaseSensitive,E>::add(const StringData* sd, const V& v) {
  65   assert(sd->isStatic());
  66
  67   Elm* elm = &m_table[-1 - int32_t(sd->hash() & m_mask)];
  68   UNUSED unsigned numProbes = 0;
  69   while (elm->sd) {
  70     assert(numProbes++ < m_mask + 1);
  71     // Semantics for multiple insertion: new value wins.
  72     if (strEqual<CaseSensitive>(elm->sd, sd)) break;
  73     if (UNLIKELY(++elm == m_table)) elm -= m_mask + 1;
  74   }
  75   elm->sd = sd;
  76   elm->data = v;
  77 }
  78
  79 template<class V, bool CaseSensitive, class E>
  80 V* FixedStringMap<V,CaseSensitive,E>::find(const StringData* sd) const {
  81   Elm* elm = &m_table[-1 - int32_t(sd->hash() & m_mask)];
  82   UNUSED unsigned numProbes = 0;
  83   for(;;) {
  84     assert(numProbes++ < m_mask + 1);
  85     if (UNLIKELY(nullptr == elm->sd)) return nullptr;
  86     if (strEqual<CaseSensitive>(elm->sd, sd)) return &elm->data;
  87     if (UNLIKELY(++elm == m_table)) elm -= m_mask + 1;
  88   }
  89 }
  90
  91 template class FixedStringMap<Slot,false,Slot>;
  92 template class FixedStringMap<Slot,true,Slot>;
  93 template class FixedStringMap<Id,false,Id>;
  94 template class FixedStringMap<Id,true,Id>;
  95 template class FixedStringMap<Func*,false,int32_t>;
  96 template class FixedStringMap<unsigned char* /* TCA */,true,int32_t>;
  97
  98 ///////////////////////////////////////////////////////////////////////////////
  99
 100 }