X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Finclude%2Finterval_set.h;fp=src%2Fceph%2Fsrc%2Finclude%2Finterval_set.h;h=0000000000000000000000000000000000000000;hb=7da45d65be36d36b880cc55c5036e96c24b53f00;hp=e05eacae41efacf6383731da8aa09706ea9e2bc8;hpb=691462d09d0987b47e112d6ee8740375df3c51b2;p=stor4nfv.git

diff --git a/src/ceph/src/include/interval_set.h b/src/ceph/src/include/interval_set.h
deleted file mode 100644
index e05eaca..0000000
--- a/src/ceph/src/include/interval_set.h
+++ /dev/null
@@ -1,641 +0,0 @@
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
-// vim: ts=8 sw=2 smarttab
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
- *
- * This is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License version 2.1, as published by the Free Software 
- * Foundation.  See file COPYING.
- * 
- */
-
-
-#ifndef CEPH_INTERVAL_SET_H
-#define CEPH_INTERVAL_SET_H
-
-#include <iterator>
-#include <map>
-#include <ostream>
-
-#include "encoding.h"
-
-#ifndef MIN
-# define MIN(a,b)  ((a)<=(b) ? (a):(b))
-#endif
-#ifndef MAX
-# define MAX(a,b)  ((a)>=(b) ? (a):(b))
-#endif
-
-
-template<typename T>
-class interval_set {
- public:
-
-  class const_iterator;
-
-  class iterator : public std::iterator <std::forward_iterator_tag, T>
-  {
-    public:
-        explicit iterator(typename std::map<T,T>::iterator iter)
-          : _iter(iter)
-        { }
-
-        // For the copy constructor and assignment operator, the compiler-generated functions, which
-        // perform simple bitwise copying, should be fine.
-
-        bool operator==(const iterator& rhs) const {
-          return (_iter == rhs._iter);
-        }
-
-        bool operator!=(const iterator& rhs) const {
-          return (_iter != rhs._iter);
-        }
-
-        // Dereference this iterator to get a pair.
-        std::pair < T, T > &operator*() {
-                return *_iter;
-        }
-
-        // Return the interval start.
-        T get_start() const {
-                return _iter->first;
-        }
-
-        // Return the interval length.
-        T get_len() const {
-                return _iter->second;
-        }
-
-        // Set the interval length.
-        void set_len(T len) {
-                _iter->second = len;
-        }
-
-        // Preincrement
-        iterator &operator++()
-        {
-                ++_iter;
-                return *this;
-        }
-
-        // Postincrement
-        iterator operator++(int)
-        {
-                iterator prev(_iter);
-                ++_iter;
-                return prev;
-        }
-
-    friend class interval_set<T>::const_iterator;
-
-    protected:
-        typename std::map<T,T>::iterator _iter;
-    friend class interval_set<T>;
-  };
-
-  class const_iterator : public std::iterator <std::forward_iterator_tag, T>
-  {
-    public:
-        explicit const_iterator(typename std::map<T,T>::const_iterator iter)
-          : _iter(iter)
-        { }
-
-        const_iterator(const iterator &i)
-	  : _iter(i._iter)
-        { }
-
-        // For the copy constructor and assignment operator, the compiler-generated functions, which
-        // perform simple bitwise copying, should be fine.
-
-        bool operator==(const const_iterator& rhs) const {
-          return (_iter == rhs._iter);
-        }
-
-        bool operator!=(const const_iterator& rhs) const {
-          return (_iter != rhs._iter);
-        }
-
-        // Dereference this iterator to get a pair.
-        std::pair < T, T > operator*() const {
-                return *_iter;
-        }
-
-        // Return the interval start.
-        T get_start() const {
-                return _iter->first;
-        }
-
-        // Return the interval length.
-        T get_len() const {
-                return _iter->second;
-        }
-
-        // Preincrement
-        const_iterator &operator++()
-        {
-                ++_iter;
-                return *this;
-        }
-
-        // Postincrement
-        const_iterator operator++(int)
-        {
-                const_iterator prev(_iter);
-                ++_iter;
-                return prev;
-        }
-
-    protected:
-        typename std::map<T,T>::const_iterator _iter;
-  };
-
-  interval_set() : _size(0) {}
-  interval_set(std::map<T,T>& other) {
-    m.swap(other);
-    _size = 0;
-    for (auto& i : m) {
-      _size += i.second;
-    }
-  }
-
-  int num_intervals() const
-  {
-    return m.size();
-  }
-
-  typename interval_set<T>::iterator begin() {
-    return typename interval_set<T>::iterator(m.begin());
-  }
-
-  typename interval_set<T>::iterator lower_bound(T start) {
-    return typename interval_set<T>::iterator(find_inc_m(start));
-  }
-
-  typename interval_set<T>::iterator end() {
-    return typename interval_set<T>::iterator(m.end());
-  }
-
-  typename interval_set<T>::const_iterator begin() const {
-    return typename interval_set<T>::const_iterator(m.begin());
-  }
-
-  typename interval_set<T>::const_iterator lower_bound(T start) const {
-    return typename interval_set<T>::const_iterator(find_inc(start));
-  }
-
-  typename interval_set<T>::const_iterator end() const {
-    return typename interval_set<T>::const_iterator(m.end());
-  }
-
-  // helpers
- private:
-  typename std::map<T,T>::const_iterator find_inc(T start) const {
-    typename std::map<T,T>::const_iterator p = m.lower_bound(start);  // p->first >= start
-    if (p != m.begin() &&
-        (p == m.end() || p->first > start)) {
-      p--;   // might overlap?
-      if (p->first + p->second <= start)
-        p++; // it doesn't.
-    }
-    return p;
-  }
-  
-  typename std::map<T,T>::iterator find_inc_m(T start) {
-    typename std::map<T,T>::iterator p = m.lower_bound(start);
-    if (p != m.begin() &&
-        (p == m.end() || p->first > start)) {
-      p--;   // might overlap?
-      if (p->first + p->second <= start)
-        p++; // it doesn't.
-    }
-    return p;
-  }
-  
-  typename std::map<T,T>::const_iterator find_adj(T start) const {
-    typename std::map<T,T>::const_iterator p = m.lower_bound(start);
-    if (p != m.begin() &&
-        (p == m.end() || p->first > start)) {
-      p--;   // might touch?
-      if (p->first + p->second < start)
-        p++; // it doesn't.
-    }
-    return p;
-  }
-  
-  typename std::map<T,T>::iterator find_adj_m(T start) {
-    typename std::map<T,T>::iterator p = m.lower_bound(start);
-    if (p != m.begin() &&
-        (p == m.end() || p->first > start)) {
-      p--;   // might touch?
-      if (p->first + p->second < start)
-        p++; // it doesn't.
-    }
-    return p;
-  }
-  
- public:
-  bool operator==(const interval_set& other) const {
-    return _size == other._size && m == other.m;
-  }
-
-  int64_t size() const {
-    return _size;
-  }
-
-  void bound_encode(size_t& p) const {
-    denc_traits<std::map<T,T>>::bound_encode(m, p);
-  }
-  void encode(bufferlist::contiguous_appender& p) const {
-    denc(m, p);
-  }
-  void decode(bufferptr::iterator& p) {
-    denc(m, p);
-    _size = 0;
-    for (const auto& i : m) {
-      _size += i.second;
-    }
-  }
-  void decode(bufferlist::iterator& p) {
-    denc(m, p);
-    _size = 0;
-    for (const auto& i : m) {
-      _size += i.second;
-    }
-  }
-
-  void encode_nohead(bufferlist::contiguous_appender& p) const {
-    denc_traits<std::map<T,T>>::encode_nohead(m, p);
-  }
-  void decode_nohead(int n, bufferptr::iterator& p) {
-    denc_traits<std::map<T,T>>::decode_nohead(n, m, p);
-    _size = 0;
-    for (const auto& i : m) {
-      _size += i.second;
-    }
-  }
-
-  void clear() {
-    m.clear();
-    _size = 0;
-  }
-
-  bool contains(T i, T *pstart=0, T *plen=0) const {
-    typename std::map<T,T>::const_iterator p = find_inc(i);
-    if (p == m.end()) return false;
-    if (p->first > i) return false;
-    if (p->first+p->second <= i) return false;
-    assert(p->first <= i && p->first+p->second > i);
-    if (pstart)
-      *pstart = p->first;
-    if (plen)
-      *plen = p->second;
-    return true;
-  }
-  bool contains(T start, T len) const {
-    typename std::map<T,T>::const_iterator p = find_inc(start);
-    if (p == m.end()) return false;
-    if (p->first > start) return false;
-    if (p->first+p->second <= start) return false;
-    assert(p->first <= start && p->first+p->second > start);
-    if (p->first+p->second < start+len) return false;
-    return true;
-  }
-  bool intersects(T start, T len) const {
-    interval_set a;
-    a.insert(start, len);
-    interval_set i;
-    i.intersection_of( *this, a );
-    if (i.empty()) return false;
-    return true;
-  }
-
-  // outer range of set
-  bool empty() const {
-    return m.empty();
-  }
-  T range_start() const {
-    assert(!empty());
-    typename std::map<T,T>::const_iterator p = m.begin();
-    return p->first;
-  }
-  T range_end() const {
-    assert(!empty());
-    typename std::map<T,T>::const_iterator p = m.end();
-    p--;
-    return p->first+p->second;
-  }
-
-  // interval start after p (where p not in set)
-  bool starts_after(T i) const {
-    assert(!contains(i));
-    typename std::map<T,T>::const_iterator p = find_inc(i);
-    if (p == m.end()) return false;
-    return true;
-  }
-  T start_after(T i) const {
-    assert(!contains(i));
-    typename std::map<T,T>::const_iterator p = find_inc(i);
-    return p->first;
-  }
-
-  // interval end that contains start
-  T end_after(T start) const {
-    assert(contains(start));
-    typename std::map<T,T>::const_iterator p = find_inc(start);
-    return p->first+p->second;
-  }
-  
-  void insert(T val) {
-    insert(val, 1);
-  }
-
-  void insert(T start, T len, T *pstart=0, T *plen=0) {
-    //cout << "insert " << start << "~" << len << endl;
-    assert(len > 0);
-    _size += len;
-    typename std::map<T,T>::iterator p = find_adj_m(start);
-    if (p == m.end()) {
-      m[start] = len;                  // new interval
-      if (pstart)
-	*pstart = start;
-      if (plen)
-	*plen = len;
-    } else {
-      if (p->first < start) {
-        
-        if (p->first + p->second != start) {
-          //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
-          ceph_abort();
-        }
-        
-        p->second += len;               // append to end
-        
-        typename std::map<T,T>::iterator n = p;
-        n++;
-        if (n != m.end() && 
-            start+len == n->first) {   // combine with next, too!
-          p->second += n->second;
-          m.erase(n);
-        }
-	if (pstart)
-	  *pstart = p->first;
-	if (plen)
-	  *plen = p->second;
-      } else {
-        if (start+len == p->first) {
-          m[start] = len + p->second;  // append to front 
-	  if (pstart)
-	    *pstart = start;
-	  if (plen)
-	    *plen = len + p->second;
-          m.erase(p);
-        } else {
-          assert(p->first > start+len);
-          m[start] = len;              // new interval
-	  if (pstart)
-	    *pstart = start;
-	  if (plen)
-	    *plen = len;
-        }
-      }
-    }
-  }
-
-  void swap(interval_set<T>& other) {
-    m.swap(other.m);
-    std::swap(_size, other._size);
-  }    
-  
-  void erase(iterator &i) {
-    _size -= i.get_len();
-    assert(_size >= 0);
-    m.erase(i._iter);
-  }
-
-  void erase(T val) {
-    erase(val, 1);
-  }
-
-  void erase(T start, T len) {
-    typename std::map<T,T>::iterator p = find_inc_m(start);
-
-    _size -= len;
-    assert(_size >= 0);
-
-    assert(p != m.end());
-    assert(p->first <= start);
-
-    T before = start - p->first;
-    assert(p->second >= before+len);
-    T after = p->second - before - len;
-    
-    if (before) 
-      p->second = before;        // shorten bit before
-    else
-      m.erase(p);
-    if (after)
-      m[start+len] = after;
-  }
-
-
-  void subtract(const interval_set &a) {
-    for (typename std::map<T,T>::const_iterator p = a.m.begin();
-         p != a.m.end();
-         p++)
-      erase(p->first, p->second);
-  }
-
-  void insert(const interval_set &a) {
-    for (typename std::map<T,T>::const_iterator p = a.m.begin();
-         p != a.m.end();
-         p++)
-      insert(p->first, p->second);
-  }
-
-
-  void intersection_of(const interval_set &a, const interval_set &b) {
-    assert(&a != this);
-    assert(&b != this);
-    clear();
-
-    typename std::map<T,T>::const_iterator pa = a.m.begin();
-    typename std::map<T,T>::const_iterator pb = b.m.begin();
-    typename decltype(m)::iterator mi = m.begin();
-
-    while (pa != a.m.end() && pb != b.m.end()) {
-      // passing?
-      if (pa->first + pa->second <= pb->first) 
-        { pa++;  continue; }
-      if (pb->first + pb->second <= pa->first) 
-        { pb++;  continue; }
-
-      if (*pa == *pb) {
-        do {
-          mi = m.insert(mi, *pa);
-          _size += pa->second;
-          ++pa;
-          ++pb;
-        } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
-        continue;
-      }
-
-      T start = MAX(pa->first, pb->first);
-      T en = MIN(pa->first+pa->second, pb->first+pb->second);
-      assert(en > start);
-      typename decltype(m)::value_type i{start, en - start};
-      mi = m.insert(mi, i);
-      _size += i.second;
-      if (pa->first+pa->second > pb->first+pb->second)
-        pb++;
-      else
-        pa++; 
-    }
-  }
-  void intersection_of(const interval_set& b) {
-    interval_set a;
-    swap(a);
-    intersection_of(a, b);
-  }
-
-  void union_of(const interval_set &a, const interval_set &b) {
-    assert(&a != this);
-    assert(&b != this);
-    clear();
-    
-    //cout << "union_of" << endl;
-
-    // a
-    m = a.m;
-    _size = a._size;
-
-    // - (a*b)
-    interval_set ab;
-    ab.intersection_of(a, b);
-    subtract(ab);
-
-    // + b
-    insert(b);
-    return;
-  }
-  void union_of(const interval_set &b) {
-    interval_set a;
-    swap(a);    
-    union_of(a, b);
-  }
-  void union_insert(T off, T len) {
-    interval_set a;
-    a.insert(off, len);
-    union_of(a);
-  }
-
-  bool subset_of(const interval_set &big) const {
-    for (typename std::map<T,T>::const_iterator i = m.begin();
-         i != m.end();
-         i++) 
-      if (!big.contains(i->first, i->second)) return false;
-    return true;
-  }  
-
-  /*
-   * build a subset of @other, starting at or after @start, and including
-   * @len worth of values, skipping holes.  e.g.,
-   *  span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
-   */
-  void span_of(const interval_set &other, T start, T len) {
-    clear();
-    typename std::map<T,T>::const_iterator p = other.find_inc(start);
-    if (p == other.m.end())
-      return;
-    if (p->first < start) {
-      if (p->first + p->second < start)
-	return;
-      if (p->first + p->second < start + len) {
-	T howmuch = p->second - (start - p->first);
-	insert(start, howmuch);
-	len -= howmuch;
-	p++;
-      } else {
-	insert(start, len);
-	return;
-      }
-    }
-    while (p != other.m.end() && len > 0) {
-      if (p->second < len) {
-	insert(p->first, p->second);
-	len -= p->second;
-	p++;
-      } else {
-	insert(p->first, len);
-	return;
-      }
-    }
-  }
-
-  /*
-   * Move contents of m into another std::map<T,T>. Use that instead of
-   * encoding interval_set into bufferlist then decoding it back into std::map.
-   */
-  void move_into(std::map<T,T>& other) {
-    other = std::move(m);
-  }
-
-private:
-  // data
-  int64_t _size;
-  std::map<T,T> m;   // map start -> len
-};
-
-// declare traits explicitly because (1) it's templatized, and (2) we
-// want to include _nohead variants.
-template<typename T>
-struct denc_traits<interval_set<T>> {
-  static constexpr bool supported = true;
-  static constexpr bool bounded = false;
-  static constexpr bool featured = false;
-  static constexpr bool need_contiguous = denc_traits<T>::need_contiguous;
-  static void bound_encode(const interval_set<T>& v, size_t& p) {
-    v.bound_encode(p);
-  }
-  static void encode(const interval_set<T>& v,
-		     bufferlist::contiguous_appender& p) {
-    v.encode(p);
-  }
-  static void decode(interval_set<T>& v, bufferptr::iterator& p) {
-    v.decode(p);
-  }
-  template<typename U=T>
-    static typename std::enable_if<sizeof(U) && !need_contiguous>::type
-    decode(interval_set<T>& v, bufferlist::iterator& p) {
-    v.decode(p);
-  }
-  static void encode_nohead(const interval_set<T>& v,
-			    bufferlist::contiguous_appender& p) {
-    v.encode_nohead(p);
-  }
-  static void decode_nohead(size_t n, interval_set<T>& v,
-			    bufferptr::iterator& p) {
-    v.decode_nohead(n, p);
-  }
-};
-
-
-template<class T>
-inline std::ostream& operator<<(std::ostream& out, const interval_set<T> &s) {
-  out << "[";
-  const char *prequel = "";
-  for (typename interval_set<T>::const_iterator i = s.begin();
-       i != s.end();
-       ++i)
-  {
-    out << prequel << i.get_start() << "~" << i.get_len();
-    prequel = ",";
-  }
-  out << "]";
-  return out;
-}
-
-
-#endif