database.hpp

#pragma once
 
#include <cstdint>
#include <cstring>
 
#include "flash.hpp"
#include "libxr.hpp"
#include "libxr_def.hpp"
#include "libxr_type.hpp"
 
namespace LibXR
{
 
static constexpr uint16_t LIBXR_DATABASE_VERSION = 3;
 
class Database
{
 public:
  class KeyBase
  {
   public:
    const char* name_;  
    RawData raw_data_;  
 
    KeyBase(const char* name, RawData raw_data) : name_(name), raw_data_(raw_data) {}
  };
 
  template <typename Data>
  class Key : public KeyBase
  {
   public:
    Data data_;           
    Database& database_;  
 
    Key(Database& database, const char* name, Data init_value)
        : KeyBase(name, RawData(data_)), database_(database)
    {
      if (database.Get(*this) == ErrorCode::NOT_FOUND)
      {
        data_ = init_value;
        database.Add(*this);
      }
    }
 
    Key(Database& database, const char* name)
        : KeyBase(name, RawData(data_)), database_(database)
    {
      if (database.Get(*this) == ErrorCode::NOT_FOUND)
      {
        memset(&data_, 0, sizeof(Data));
        database.Add(*this);
      }
    }
 
    operator Data() { return data_; }
 
    ErrorCode Set(Data data) { return database_.Set(*this, RawData(data)); }
 
    ErrorCode Load() { return database_.Get(*this); }
 
    ErrorCode operator=(Data data) { return Set(data); }  // NOLINT
  };
 
 private:
  virtual ErrorCode Get(KeyBase& key) = 0;
 
  virtual ErrorCode Set(KeyBase& key, RawData data) = 0;
 
  virtual ErrorCode Add(KeyBase& key) = 0;
};
 
class DatabaseRawSequential : public Database
{
 public:
  explicit DatabaseRawSequential(Flash& flash, size_t max_buffer_size = 256);
 
  void Init();
 
  void Save();
 
  void Load();
 
  void Restore();
 
  ErrorCode Get(Database::KeyBase& key) override;
 
  ErrorCode Set(KeyBase& key, RawData data) override
  {
    return SetKey(key.name_, data.addr_, data.size_);
  }
 
  ErrorCode Add(KeyBase& key) override
  {
    return AddKey(key.name_, key.raw_data_.addr_, key.raw_data_.size_);
  }
 
 private:
  enum class BlockType : uint8_t
  {
    MAIN = 0,   
    BACKUP = 1  
  };
 
#pragma pack(push, 1)
  struct KeyInfo
  {
    uint32_t raw_data;
 
    KeyInfo() : raw_data(0xFFFFFFFF) {}
 
    KeyInfo(bool nextKey, uint8_t nameLength, uint32_t dataSize) : raw_data(0)
    {
      SetNextKeyExist(nextKey);
      SetNameLength(nameLength);
      SetDataSize(dataSize);
    }
 
    void SetNextKeyExist(bool value)
    {
      raw_data = (raw_data & 0x7FFFFFFF) | (static_cast<uint32_t>(value & 0x1) << 31);
    }
    bool GetNextKeyExist() const { return (raw_data >> 31) & 0x1; }
 
    void SetNameLength(uint8_t len)
    {
      raw_data = (raw_data & 0x80FFFFFF) | (static_cast<uint32_t>(len & 0x7F) << 24);
    }
    uint8_t GetNameLength() const { return (raw_data >> 24) & 0x7F; }
 
    void SetDataSize(uint32_t size)
    {
      raw_data = (raw_data & 0xFF000000) | (size & 0x00FFFFFF);
    }
    uint32_t GetDataSize() const { return raw_data & 0x00FFFFFF; }
  };
 
  static_assert(sizeof(KeyInfo) == 4, "KeyInfo size must be 4 bytes");
#pragma pack(pop)
 
  struct FlashInfo
  {
    uint32_t header;  
    KeyInfo key;      
  };
 
  ErrorCode AddKey(const char* name, const void* data, size_t size);
  ErrorCode SetKey(const char* name, const void* data, size_t size);
  ErrorCode SetKey(size_t offset, const void* data, size_t size);
  ErrorCode GetKeyData(size_t offset, RawData data);
  void InitBlock(BlockType block);
  bool IsBlockInited(BlockType block);
  bool IsBlockEmpty(BlockType block);
  bool IsBlockError(BlockType block);
  bool HasLastKey(size_t offset);
  size_t GetKeySize(size_t offset);
  size_t GetNextKey(size_t offset);
  size_t GetLastKey(BlockType block);
  void SetNestKeyExist(size_t offset, bool exist);
  bool KeyDataCompare(size_t offset, const void* data, size_t size);
  bool KeyNameCompare(size_t offset, const char* name);
  size_t SearchKey(const char* name);
 
  static constexpr uint32_t FLASH_HEADER =
      0x12345678 + LIBXR_DATABASE_VERSION;  
  static constexpr uint8_t CHECKSUM_BYTE = 0x56;  
 
  Flash& flash_;              
  uint8_t* buffer_;           
  uint32_t block_size_;       
  uint32_t max_buffer_size_;  
};
 
template <size_t MinWriteSize>
class DatabaseRaw : public Database
{
  static constexpr uint32_t FLASH_HEADER =
      0x12345678 + LIBXR_DATABASE_VERSION;  
 
  static constexpr uint32_t CHECKSUM_BYTE = 0x9abcedf0;  
 
  enum class BlockType : uint8_t
  {
    MAIN = 0,   
    BACKUP = 1  
  };
 
#pragma pack(push, 1)
  template <size_t BlockSize>
  struct BlockBoolData
  {
    uint8_t data[BlockSize];
  };
#pragma pack(pop)
 
  template <size_t BlockSize>
  class BlockBoolUtil
  {
   public:
    static void SetFlag(BlockBoolData<BlockSize>& obj, bool value)
    {
      memset(obj.data, 0xFF, BlockSize);
      if (!value)
      {
        obj.data[BlockSize - 1] &= 0xF0;
      }
    }
 
    static bool ReadFlag(const BlockBoolData<BlockSize>& obj)
    {
      uint8_t last_4bits = obj.data[BlockSize - 1] & 0x0F;
      return last_4bits == 0x0F;
    }
 
    static bool Valid(const BlockBoolData<BlockSize>& obj)
    {
      if (BlockSize == 0)
      {
        return false;
      }
 
      for (size_t i = 0; i < BlockSize - 1; ++i)
      {
        if (obj.data[i] != 0xFF)
        {
          return false;
        }
      }
 
      uint8_t last_byte = obj.data[BlockSize - 1];
      if ((last_byte & 0xF0) != 0xF0)
      {
        return false;
      }
 
      uint8_t last_4bits = last_byte & 0x0F;
      if (!(last_4bits == 0x0F || last_4bits == 0x00))
      {
        return false;
      }
 
      return true;
    }
  };
 
#pragma pack(push, 1)
  struct KeyInfo
  {
    BlockBoolData<MinWriteSize> no_next_key;     
    BlockBoolData<MinWriteSize> available_flag;  
    BlockBoolData<MinWriteSize> uninit;          
 
    uint32_t raw_info = 0;  
 
    // 默认构造
    KeyInfo()
    {
      BlockBoolUtil<MinWriteSize>::SetFlag(no_next_key, true);
      BlockBoolUtil<MinWriteSize>::SetFlag(available_flag, true);
      BlockBoolUtil<MinWriteSize>::SetFlag(uninit, true);
    }
 
    void SetNameLength(uint8_t len)
    {
      raw_info = (raw_info & 0x01FFFFFF) | ((len & 0x7F) << 25);
    }
 
    uint8_t GetNameLength() const { return (raw_info >> 25) & 0x7F; }
 
    void SetDataSize(uint32_t size)
    {
      raw_info = (raw_info & 0xFE000000) | (size & 0x01FFFFFF);
    }
 
    uint32_t GetDataSize() const { return raw_info & 0x01FFFFFF; }
  };
#pragma pack(pop)
 
#pragma pack(push, 1)
  struct FlashInfo
  {
    FlashInfo()
    {
      header = 0xFFFFFFFF;
      memset(padding, 0xFF, MinWriteSize);
    }
 
    union
    {
      uint32_t header;  
      uint8_t padding[MinWriteSize];
    };
    KeyInfo key;  
  };
#pragma pack(pop)
 
  size_t recycle_threshold_ = 0;  
  Flash& flash_;                  
  uint32_t block_size_;           
  uint8_t write_buffer_[MinWriteSize];  
 
  size_t AvailableSize()
  {
    auto offset = GetNextKey(GetLastKey(BlockType::MAIN));
    return block_size_ - sizeof(CHECKSUM_BYTE) - offset;
  }
 
  ErrorCode AddKeyBody(size_t name_len, size_t size, size_t& key_buf_offset)
  {
    bool recycle = false;
  add_again:
    size_t last_key_offset = GetLastKey(BlockType::MAIN);
    key_buf_offset = 0;
 
    if (AvailableSize() <
        AlignSize(sizeof(KeyInfo)) + AlignSize(name_len) + AlignSize(size))
    {
      if (!recycle)
      {
        Recycle();
        recycle = true;
        // NOLINTNEXTLINE
        goto add_again;
      }
      else
      {
        ASSERT(false);
        return ErrorCode::FULL;
      }
    }
 
    if (last_key_offset == 0)
    {
      FlashInfo flash_info;
      flash_info.header = FLASH_HEADER;
      KeyInfo& tmp_key = flash_info.key;
      BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.no_next_key, false);
      BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.available_flag, false);
      BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.uninit, false);
      tmp_key.SetNameLength(0);
      tmp_key.SetDataSize(0);
      Write(0, flash_info);
      key_buf_offset = GetNextKey(OFFSET_OF(FlashInfo, key));
    }
    else
    {
      key_buf_offset = GetNextKey(last_key_offset);
    }
 
    KeyInfo new_key = {};
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.no_next_key, true);
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.available_flag, true);
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.uninit, true);
    new_key.SetNameLength(name_len);
    new_key.SetDataSize(size);
 
    Write(key_buf_offset, new_key);
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.uninit, false);
 
    if (last_key_offset != 0)
    {
      KeyInfo last_key;
      flash_.Read(last_key_offset, last_key);
      KeyInfo new_last_key = {};
      BlockBoolUtil<MinWriteSize>::SetFlag(new_last_key.no_next_key, false);
      BlockBoolUtil<MinWriteSize>::SetFlag(
          new_last_key.available_flag,
          BlockBoolUtil<MinWriteSize>::ReadFlag(last_key.available_flag));
      BlockBoolUtil<MinWriteSize>::SetFlag(
          new_last_key.uninit, BlockBoolUtil<MinWriteSize>::ReadFlag(last_key.uninit));
      new_last_key.SetNameLength(last_key.GetNameLength());
      new_last_key.SetDataSize(last_key.GetDataSize());
 
      Write(last_key_offset, new_last_key);
    }
 
    Write(key_buf_offset, new_key);
 
    return ErrorCode::OK;
  }
 
  ErrorCode AddKey(size_t name_offset, size_t name_len, const void* data, size_t size)
  {
    size_t key_buf_offset = 0;
    ErrorCode ec = AddKeyBody(name_len, size, key_buf_offset);
    if (ec != ErrorCode::OK)
    {
      return ec;
    }
    CopyFlashData(GetKeyName(key_buf_offset), name_offset, name_len);
    Write(GetKeyData(key_buf_offset), {reinterpret_cast<const uint8_t*>(data), size});
    return ErrorCode::OK;
  }
 
  ErrorCode AddKey(const char* name, const void* data, size_t size)
  {
    size_t name_len = strlen(name) + 1;
    if (auto ans = SearchKey(name))
    {
      return SetKey(name, data, size);
    }
    size_t key_buf_offset = 0;
    ErrorCode ec = AddKeyBody(name_len, size, key_buf_offset);
    if (ec != ErrorCode::OK)
    {
      return ec;
    }
    Write(GetKeyName(key_buf_offset), {reinterpret_cast<const uint8_t*>(name), name_len});
    Write(GetKeyData(key_buf_offset), {reinterpret_cast<const uint8_t*>(data), size});
    return ErrorCode::OK;
  }
 
  ErrorCode SetKeyCommon(size_t key_offset, size_t name_len, const void* data,
                         size_t size)
  {
    if (key_offset)
    {
      KeyInfo key;
      flash_.Read(key_offset, key);
      if (key.GetDataSize() == size)
      {
        if (KeyDataCompare(key_offset, data, size))
        {
          KeyInfo new_key = {};
          BlockBoolUtil<MinWriteSize>::SetFlag(
              new_key.no_next_key,
              BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key));
          BlockBoolUtil<MinWriteSize>::SetFlag(new_key.available_flag, false);
          BlockBoolUtil<MinWriteSize>::SetFlag(
              new_key.uninit, BlockBoolUtil<MinWriteSize>::ReadFlag(key.uninit));
          new_key.SetNameLength(name_len);
          new_key.SetDataSize(size);
          Write(key_offset, new_key);
          return AddKey(GetKeyName(key_offset), name_len, data, size);
        }
        return ErrorCode::OK;
      }
    }
    return ErrorCode::FAILED;
  }
 
  ErrorCode SetKey(size_t name_offset, size_t name_length, const void* data, size_t size)
  {
    size_t key_offset = SearchKey(name_offset, name_length);
    return SetKeyCommon(key_offset, name_length, data, size);
  }
 
  ErrorCode SetKey(const char* name, const void* data, size_t size, bool recycle = true)
  {
    size_t key_offset = SearchKey(name);
    if (key_offset)
    {
      KeyInfo key;
      flash_.Read(key_offset, key);
      if (key.GetDataSize() == size)
      {
        if (KeyDataCompare(key_offset, data, size))
        {
          if (AvailableSize() < AlignSize(size) + AlignSize(sizeof(KeyInfo)) +
                                    AlignSize(key.GetNameLength()))
          {
            if (recycle)
            {
              Recycle();
              return SetKey(name, data, size, false);
            }
            else
            {
              ASSERT(false);
              return ErrorCode::FULL;
            }
          }
          KeyInfo new_key = {};
          BlockBoolUtil<MinWriteSize>::SetFlag(
              new_key.no_next_key,
              BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key));
          BlockBoolUtil<MinWriteSize>::SetFlag(new_key.available_flag, false);
          BlockBoolUtil<MinWriteSize>::SetFlag(
              new_key.uninit, BlockBoolUtil<MinWriteSize>::ReadFlag(key.uninit));
          new_key.SetNameLength(key.GetNameLength());
          new_key.SetDataSize(size);
          Write(key_offset, new_key);
          return AddKey(GetKeyName(key_offset), key.GetNameLength(), data, size);
        }
        return ErrorCode::OK;
      }
    }
    return ErrorCode::FAILED;
  }
 
  size_t GetKeyData(size_t offset)
  {
    KeyInfo key;
    flash_.Read(offset, key);
    return offset + AlignSize(sizeof(KeyInfo)) + AlignSize(key.GetNameLength());
  }
 
  size_t GetKeyName(size_t offset) { return offset + AlignSize(sizeof(KeyInfo)); }
 
  void InitBlock(BlockType block)
  {
    size_t offset = 0;
    if (block == BlockType::BACKUP)
    {
      offset = block_size_;
    }
    flash_.Erase(offset, block_size_);
 
    FlashInfo info;  // padding filled with 0xFF by constructor
    info.header = FLASH_HEADER;
    KeyInfo& tmp_key = info.key;
    BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.no_next_key, true);
    BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.available_flag, true);
    BlockBoolUtil<MinWriteSize>::SetFlag(tmp_key.uninit, false);
    tmp_key.SetNameLength(0);
    tmp_key.SetDataSize(0);
    Write(offset, {reinterpret_cast<uint8_t*>(&info), sizeof(FlashInfo)});
    Write(offset + block_size_ - AlignSize(sizeof(CHECKSUM_BYTE)),
          {&CHECKSUM_BYTE, sizeof(CHECKSUM_BYTE)});
  }
 
  bool IsBlockInited(BlockType block)
  {
    size_t offset = 0;
    if (block == BlockType::BACKUP)
    {
      offset = block_size_;
    }
    FlashInfo flash_data;
    flash_.Read(offset, flash_data);
    return flash_data.header == FLASH_HEADER;
  }
 
  bool IsBlockEmpty(BlockType block)
  {
    size_t offset = 0;
    if (block == BlockType::BACKUP)
    {
      offset = block_size_;
    }
    FlashInfo flash_data;
    flash_.Read(offset, flash_data);
    return BlockBoolUtil<MinWriteSize>::ReadFlag(flash_data.key.available_flag) == true;
  }
 
  bool IsBlockError(BlockType block)
  {
    size_t offset = 0;
    if (block == BlockType::BACKUP)
    {
      offset = block_size_;
    }
    uint32_t checksum = 0;
    flash_.Read(offset + block_size_ - AlignSize(sizeof(CHECKSUM_BYTE)), checksum);
    return checksum != CHECKSUM_BYTE;
  }
 
  size_t GetKeySize(size_t offset)
  {
    KeyInfo key;
    flash_.Read(offset, key);
    return AlignSize(sizeof(KeyInfo)) + AlignSize(key.GetNameLength()) +
           AlignSize(key.GetDataSize());
  }
 
  size_t GetNextKey(size_t offset)
  {
    KeyInfo key;
    flash_.Read(offset, key);
    return offset + GetKeySize(offset);
  }
 
  size_t GetLastKey(BlockType block)
  {
    if (IsBlockEmpty(block))
    {
      return 0;
    }
 
    KeyInfo key;
    size_t key_offset = OFFSET_OF(FlashInfo, key);
    if (block != BlockType::MAIN)
    {
      key_offset += block_size_;
    }
    flash_.Read(key_offset, key);
    while (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key))
    {
      key_offset = GetNextKey(key_offset);
      flash_.Read(key_offset, key);
    }
    return key_offset;
  }
 
  bool KeyDataCompare(size_t offset, const void* data, size_t size)
  {
    KeyInfo key;
    flash_.Read(offset, key);
    size_t key_data_offset = GetKeyData(offset);
    uint8_t data_buffer = 0;
    for (size_t i = 0; i < size; i++)
    {
      flash_.Read(key_data_offset + i, data_buffer);
      if (data_buffer != (reinterpret_cast<const uint8_t*>(data))[i])
      {
        return true;
      }
    }
    return false;
  }
 
  bool KeyNameCompare(size_t offset, const char* name)
  {
    KeyInfo key;
    flash_.Read(offset, key);
    for (size_t i = 0; i < key.GetNameLength(); i++)
    {
      uint8_t data_buffer = 0;
      flash_.Read(offset + AlignSize(sizeof(KeyInfo)) + i, data_buffer);
      if (data_buffer != name[i])
      {
        return true;
      }
    }
    return false;
  }
 
  bool KeyNameCompare(size_t offset_a, size_t offset_b)
  {
    KeyInfo key_a, key_b;
    flash_.Read(offset_a, key_a);
    flash_.Read(offset_b, key_b);
    if (key_a.GetNameLength() != key_b.GetNameLength())
    {
      return true;
    }
    for (size_t i = 0; i < key_a.GetNameLength(); i++)
    {
      uint8_t data_buffer_a = 0, data_buffer_b = 0;
      flash_.Read(offset_a + sizeof(KeyInfo) + i, data_buffer_a);
      flash_.Read(offset_b + sizeof(KeyInfo) + i, data_buffer_b);
      if (data_buffer_a != data_buffer_b)
      {
        return true;
      }
    }
    return false;
  }
 
  void CopyFlashData(size_t dst_offset, size_t src_offset, size_t size)
  {
    for (size_t i = 0; i < size; i += MinWriteSize)
    {
      flash_.Read(src_offset + i, {write_buffer_, MinWriteSize});
      flash_.Write(dst_offset + i, {write_buffer_, MinWriteSize});
    }
  }
 
  size_t SearchKey(const char* name)
  {
    if (IsBlockEmpty(BlockType::MAIN))
    {
      return 0;
    }
 
    KeyInfo key;
    size_t key_offset = OFFSET_OF(FlashInfo, key);
    flash_.Read(key_offset, key);
 
    size_t ans = 0, need_cycle = 0;
 
    while (true)
    {
      if (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.available_flag))
      {
        key_offset = GetNextKey(key_offset);
        flash_.Read(key_offset, key);
        need_cycle++;
        continue;
      }
 
      if (!KeyNameCompare(key_offset, name))
      {
        ans = key_offset;
        break;
      }
 
      if (BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key))
      {
        break;
      }
 
      key_offset = GetNextKey(key_offset);
      flash_.Read(key_offset, key);
    }
 
    if (need_cycle > recycle_threshold_)
    {
      Recycle();
      return SearchKey(name);
    }
 
    return ans;
  }
 
  size_t AlignSize(size_t size)
  {
    return static_cast<size_t>((size + MinWriteSize - 1) / MinWriteSize) * MinWriteSize;
  }
 
  ErrorCode Write(size_t offset, ConstRawData data)
  {
    if (data.size_ == 0)
    {
      return ErrorCode::OK;
    }
 
    if (data.size_ % MinWriteSize == 0)
    {
      return flash_.Write(offset, data);
    }
    else
    {
      auto final_block_index = data.size_ - data.size_ % MinWriteSize;
      if (final_block_index != 0)
      {
        flash_.Write(offset, {data.addr_, final_block_index});
      }
      memset(write_buffer_, 0xff, MinWriteSize);
      LibXR::Memory::FastCopy(
          write_buffer_, reinterpret_cast<const uint8_t*>(data.addr_) + final_block_index,
          data.size_ % MinWriteSize);
      return flash_.Write(offset + final_block_index, {write_buffer_, MinWriteSize});
    }
  }
 
 public:
  ErrorCode Get(Database::KeyBase& key) override
  {
    auto ans = SearchKey(key.name_);
    if (!ans)
    {
      return ErrorCode::NOT_FOUND;
    }
 
    KeyInfo key_buffer;
    flash_.Read(ans, key_buffer);
 
    if (key.raw_data_.size_ < key_buffer.GetDataSize())
    {
      return ErrorCode::FAILED;
    }
 
    flash_.Read(GetKeyData(ans), key.raw_data_);
 
    return ErrorCode::OK;
  }
 
  ErrorCode Set(KeyBase& key, RawData data) override
  {
    LibXR::Memory::FastCopy(key.raw_data_.addr_, data.addr_, data.size_);
    return SetKey(key.name_, data.addr_, data.size_);
  }
 
  ErrorCode Add(KeyBase& key) override
  {
    return AddKey(key.name_, key.raw_data_.addr_, key.raw_data_.size_);
  }
 
  explicit DatabaseRaw(Flash& flash, size_t recycle_threshold = 128)
      : recycle_threshold_(recycle_threshold), flash_(flash)
  {
    ASSERT(flash.MinEraseSize() * 2 <= flash_.Size());
    ASSERT(flash_.MinWriteSize() <= MinWriteSize);
    auto block_num = static_cast<size_t>(flash_.Size() / flash.MinEraseSize());
    block_size_ = block_num / 2 * flash.MinEraseSize();
    Init();
  }
 
  void Init()
  {
    if (!IsBlockInited(BlockType::BACKUP) || IsBlockError(BlockType::BACKUP))
    {
      InitBlock(BlockType::BACKUP);
    }
 
    if (!IsBlockInited(BlockType::MAIN) || IsBlockError(BlockType::MAIN))
    {
      if (IsBlockEmpty(BlockType::BACKUP))
      {
        InitBlock(BlockType::MAIN);
      }
      else
      {
        flash_.Erase(0, block_size_);
        for (uint32_t i = 0; i < block_size_; i += MinWriteSize)
        {
          flash_.Read(i + block_size_, {write_buffer_, MinWriteSize});
          flash_.Write(i, {write_buffer_, MinWriteSize});
        }
      }
    }
 
    if (!IsBlockEmpty(BlockType::BACKUP))
    {
      InitBlock(BlockType::BACKUP);
    }
 
    KeyInfo key;
    size_t key_offset = OFFSET_OF(FlashInfo, key);
    flash_.Read(key_offset, key);
    size_t need_cycle = 0;
    while (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key))
    {
      key_offset = GetNextKey(key_offset);
 
      if (key_offset + sizeof(key) >= flash_.Size())
      {
        InitBlock(BlockType::MAIN);
        break;
      }
 
      flash_.Read(key_offset, key);
 
      // TODO: 恢复损坏数据
      if (BlockBoolUtil<MinWriteSize>::ReadFlag(key.uninit))
      {
        InitBlock(BlockType::MAIN);
        break;
      }
      if (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.available_flag))
      {
        need_cycle += 1;
      }
    }
 
    if (need_cycle > recycle_threshold_)
    {
      Recycle();
    }
  }
 
  void Restore()
  {
    InitBlock(BlockType::MAIN);
    InitBlock(BlockType::BACKUP);
  }
 
  ErrorCode Recycle()
  {
    if (IsBlockEmpty(BlockType::MAIN))
    {
      return ErrorCode::OK;
    }
 
    KeyInfo key;
    size_t key_offset = OFFSET_OF(FlashInfo, key);
    flash_.Read(key_offset, key);
 
    if (!IsBlockEmpty(BlockType::BACKUP))
    {
      InitBlock(BlockType::BACKUP);
    }
 
    size_t write_buff_offset = OFFSET_OF(FlashInfo, key) + block_size_;
 
    auto new_key = KeyInfo{};
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.uninit, false);
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.available_flag, false);
    BlockBoolUtil<MinWriteSize>::SetFlag(new_key.no_next_key, false);
    Write(write_buff_offset, new_key);
 
    write_buff_offset += GetKeySize(write_buff_offset);
 
    do
    {
      key_offset = GetNextKey(key_offset);
      flash_.Read(key_offset, key);
 
      if (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.available_flag))
      {
        continue;
      }
 
      Write(write_buff_offset, key);
      write_buff_offset += AlignSize(sizeof(KeyInfo));
      CopyFlashData(write_buff_offset, GetKeyName(key_offset), key.GetNameLength());
      write_buff_offset += AlignSize(key.GetNameLength());
      CopyFlashData(write_buff_offset, GetKeyData(key_offset), key.GetDataSize());
      write_buff_offset += AlignSize(key.GetDataSize());
    } while (!BlockBoolUtil<MinWriteSize>::ReadFlag(key.no_next_key));
 
    flash_.Erase(0, block_size_);
    for (uint32_t i = 0; i < block_size_; i += MinWriteSize)
    {
      flash_.Read(i + block_size_, {write_buffer_, MinWriteSize});
      flash_.Write(i, {write_buffer_, MinWriteSize});
    }
 
    InitBlock(BlockType::BACKUP);
 
    return ErrorCode::OK;
  }
};
 
}  // namespace LibXR