Multi reader/writer cache/buffer

media/blink/rangemap.h

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef MEDIA_BLINK_RANGEMAP_H_
+#define MEDIA_BLINK_RANGEMAP_H_
+
+#include <limits>
+#include <map>
+
+#include "base/logging.h"
+
+namespace media {
+
+template<typename T>
+struct Range {
+public:
+  Range(const T& begin_, const T& end_) : begin(begin_), end(end_) {}
+  T begin;
+  T end;
+};
+
+template<typename KeyType, typename ValueType>
+class RangeMapConstIterator {
+public:
+  typedef std::map<KeyType, ValueType> MapType;
+  RangeMapConstIterator() {}
+  RangeMapConstIterator(const MapType* map,
+                        typename MapType::const_iterator first,
+                        typename MapType::const_iterator second) :
+      map_(map),
+      first_(first),
+      second_(second) {
+  }
+  bool operator==(const RangeMapConstIterator& other) {
+    return first_ ==  other.first_ && second_ == other.second_;
+  }
+  bool operator!=(const RangeMapConstIterator& other) {
+    return first_ !=  other.first_ || second_ != other.second_;
+  }
+  KeyType range_begin() const {
+    if (first_ == map_->end()) {
+      return std::numeric_limits<KeyType>::min();
+    } else {
+      return first_->first;
+    }
+  }
+  KeyType range_end() const {
+    if (second_ == map_->end()) {
+      return std::numeric_limits<KeyType>::max();
+    } else {
+      return second_->first;
+    }
+  }
+  Range<KeyType> range() const {
+    return Range<KeyType>(range_begin(), range_end());
+  }
+
+  ValueType value() const {
+    if (first_ == map_->end())
+      return 0;
+    return first_->second;
+  }
+  void operator++() {
+    first_ = second_;
+    second_++;
+  }
+  void operator--() {
+    second_ = first_;
+    if (first_ == map_->begin()) {
+      first_ = map_->end();
+    } else {
+      first_--;
+    }
+  }
+private:
+  typename MapType::const_iterator first_;
+  typename MapType::const_iterator second_;
+  const MapType* map_;
+};
+
+template<typename KeyType, typename ValueType>
+class RangeMap {
+ public:
+  typedef std::map<KeyType, ValueType> MapType;
+typedef RangeMapConstIterator<KeyType, ValueType> const_iterator;
+
+  ValueType operator[](KeyType k) const {
+    typename MapType::const_iterator i = map_.upper_bound(k);
+    if (i == map_.begin()) {
+      return 0;
+    } else {
+      --i;
+      return i->second;
+    }
+  }
+
+  // Increase [from..to) by howmuch.
+  void IncrementRange(KeyType from, KeyType to, ValueType howmuch) {
+    DCHECK_GE(to, from);
+    if (from == to || howmuch == 0)
+      return;
+    typename MapType::iterator a = MakeEntry(from);
+    typename MapType::iterator b = MakeEntry(to);
+    for (typename MapType::iterator i = a; i != b; ++i) {
+      i->second += howmuch;
+    }
+    RemoveDuplicates(a);
+    // b may be invalid
+    RemoveDuplicates(map_.lower_bound(to));
+  }
+
+  // Set [from..to) to howmuch.
+  void SetRange(KeyType from, KeyType to, ValueType howmuch) {
+    DCHECK_GE(to, from);
+    if (from == to)
+      return;
+    typename MapType::iterator a = MakeEntry(from);
+    typename MapType::iterator b = MakeEntry(to);
+    a->second = howmuch;
+    while (true) {
+      typename MapType::iterator c = a;
+      ++c;
+      if (c == b) {
+        break;
+      } else {
+        map_.erase(c);
+      }
+    }
+    RemoveDuplicates(a);
+    // b may be invalid
+    RemoveDuplicates(map_.lower_bound(to));
+  }
+
+  // Returns an iterator to the first range.
+  // Note, there is always at least one range.
+  const_iterator first_range() const {
+    return const_iterator(&map(), map_.end(), map_.begin());
+  }
+
+  // Returns an iterator to the last range.
+  // Note, there is always at least one range.
+  const_iterator last_range() const {
+    if (map_.empty()) {
+      return const_iterator(&map(), map_.end(), map_.end());
+    }
+    typename MapType::const_iterator i = map_.end();
+    --i;
+    return const_iterator(&map(), i, map_.end());
+  }
+
+  // Returns an iterator to the range containing |k|.
+  // Always returns a valid iterator.
+  const_iterator find(KeyType k) const {
+    if (map_.empty()) {
+      return const_iterator(&map(), map_.end(), map_.end());
+    }
+    typename MapType::const_iterator i = map_.upper_bound(k);
+    typename MapType::const_iterator j = i;
+    if (j == map_.begin()) {
+      j = map_.end();
+    } else {
+      --j;
+    }
+    return const_iterator(&map(), j, i);
+  }
+
+  const MapType& map() const { return map_; }
+
+ private:
+  typename MapType::iterator MakeEntry(KeyType k) {
+    typename MapType::value_type tmp(k, 0);
+    std::pair<typename MapType::iterator, bool> insert_result;
+    insert_result = map_.insert(tmp);
+    if (insert_result.second) {
+      if (insert_result.first != map_.begin()) {
+        typename MapType::iterator i = insert_result.first;
+        --i;
+        insert_result.first->second = i->second;
+      }
+    }
+    return insert_result.first;
+  }
+
+  void RemoveDuplicates(typename MapType::iterator i) {
+    if (i == map_.end())
+      return;
+    if (i == map_.begin() && i->second == 0)  {
+      typename MapType::iterator j = i;
+      ++i;
+      map_.erase(j);
+      if (i == map_.end())
+        return;
+    }
+    if (i != map_.begin()) {
+      typename MapType::iterator j = i;
+      --i;
+      if (i ->second == j->second) {
+        map_.erase(j);
+      }
+    }
+    typename MapType::iterator j = i;
+    ++j;
+    if (j != map_.end() && i ->second == j->second) {
+      map_.erase(j);
+    }
+  }
+
+  MapType map_;
+};
+
+
+}  // namespace media
+
+#endif  // MEDIA_BLINK_RANGEMAP_H_