可迭代的映射

大家都知道solidity中的mapping是不支持迭代的，在solidity文档中有给出“可迭代的映射”的例子。

总体数据结构：

• IterableMapping作为库合约，用于支持迭代操作
• struct itmap用于保存需要迭代的数据
  • mapping(uint => IndexValue) data：其中uint为数据的key，struct IndexValue为对数据value的封装
  • KeyFlag[] keys：KeyFlag为对数据的key的封装
  • uint size：数据的size大小
• struct IndexValue：对数据value的封装
  • uint keyIndex：此数据value对应的key值在数组keys中的索引值
  • uint value：数据value
• struct KeyFlag：对数据的key的封装
  • uint key：数据key
  • bool deleted：标识此key对应的数据是否已删除，这样可以保留数据的顺序且不会有大的改动

/// @dev Models a uint -> uint mapping where it is possible to iterate over all keys.
library IterableMapping
{
  struct itmap
  {
    mapping(uint => IndexValue) data;
    KeyFlag[] keys;
    uint size;
  }
  struct IndexValue { uint keyIndex; uint value; }
  struct KeyFlag { uint key; bool deleted; }
  function insert(itmap storage self, uint key, uint value) returns (bool replaced)
  {
    uint keyIndex = self.data[key].keyIndex;
    self.data[key].value = value;
    if (keyIndex > 0)
      return true;
    else
    {
      keyIndex = self.keys.length++;
      self.data[key].keyIndex = keyIndex + 1;
      self.keys[keyIndex].key = key;
      self.size++;
      return false;
    }
  }
  function remove(itmap storage self, uint key) returns (bool success)
  {
    uint keyIndex = self.data[key].keyIndex;
    if (keyIndex == 0)
      return false;
    delete self.data[key];
    self.keys[keyIndex - 1].deleted = true;
    self.size --;
  }
  function contains(itmap storage self, uint key) returns (bool)
  {
    return self.data[key].keyIndex > 0;
  }
  function iterate_start(itmap storage self) returns (uint keyIndex)
  {
    return iterate_next(self, uint(-1));
  }
  function iterate_valid(itmap storage self, uint keyIndex) returns (bool)
  {
    return keyIndex < self.keys.length;
  }
  function iterate_next(itmap storage self, uint keyIndex) returns (uint r_keyIndex)
  {
    keyIndex++;
    while (keyIndex < self.keys.length && self.keys[keyIndex].deleted)
      keyIndex++;
    return keyIndex;
  }
  function iterate_get(itmap storage self, uint keyIndex) returns (uint key, uint value)
  {
    key = self.keys[keyIndex].key;
    value = self.data[key].value;
  }
}

使用方法：

// How to use it:
contract User
{
  using IterableMapping for IterableMapping.itmap;
  // Just a struct holding our data.
  IterableMapping.itmap data;
  // Insert something
  function insert(uint k, uint v) returns (uint size)
  {
    // Actually calls itmap_impl.insert, auto-supplying the first parameter for us.
    data.insert(k, v);
    // We can still access members of the struct - but we should take care not to mess with them.
    return data.size;
  }
  // Computes the sum of all stored data.
  function sum() returns (uint s)
  {
    for (var i = data.iterate_start(); data.iterate_valid(i); i = data.iterate_next(i))
    {
        var (key, value) = data.iterate_get(i);
        s += value;
    }
  }
}

此库合约的适用范围应该是需要在删除一条数据后仍然保持顺序的场景。