compiler/dwarf/dedup_vector.h

/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_COMPILER_DWARF_DEDUP_VECTOR_H_
#define ART_COMPILER_DWARF_DEDUP_VECTOR_H_

#include <vector>
#include <unordered_map>

namespace art {
namespace dwarf {
  class DedupVector {
   public:
    // Returns an offset to previously inserted identical block of data,
    // or appends the data at the end of the vector and returns offset to it.
    size_t Insert(const uint8_t* ptr, size_t num_bytes) {
      // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
      uint32_t hash = 2166136261u;
      for (size_t i = 0; i < num_bytes; i++) {
        hash = (hash ^ ptr[i]) * 16777619u;
      }
      // Try to find existing copy of the data.
      const auto& range = hash_to_offset_.equal_range(hash);
      for (auto it = range.first; it != range.second; ++it) {
        const size_t offset = it->second;
        if (offset + num_bytes <= vector_.size() &&
            memcmp(vector_.data() + offset, ptr, num_bytes) == 0) {
          return offset;
        }
      }
      // Append the data at the end of the vector.
      const size_t new_offset = vector_.size();
      hash_to_offset_.emplace(hash, new_offset);
      vector_.insert(vector_.end(), ptr, ptr + num_bytes);
      return new_offset;
    }

    const std::vector<uint8_t>& Data() const { return vector_; }

   private:
    struct IdentityHash {
      size_t operator()(uint32_t v) const { return v; }
    };

    // We store the full hash as the key to simplify growing of the table.
    // It avoids storing or referencing the actual data in the hash-table.
    std::unordered_multimap<uint32_t, size_t, IdentityHash> hash_to_offset_;

    std::vector<uint8_t> vector_;
  };
}  // namespace dwarf
}  // namespace art

#endif  // ART_COMPILER_DWARF_DEDUP_VECTOR_H_