[ceph.git] / ceph / src / include / compact_set.h

/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2015 Red Hat, Inc
 *
 * 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_COMPACT_SET_H
#define CEPH_COMPACT_SET_H

#include "buffer.h"
#include "encoding.h"

#include <memory>
#include <set>

template <class T, class Set>
class compact_set_base {
protected:
  std::unique_ptr<Set> set;
  void alloc_internal() {
    if (!set)
      set.reset(new Set);
  }
  void free_internal() {
    set.reset();
  }
  template <class It>
  class iterator_base {
  private:
    const compact_set_base* set;
    It it;
    iterator_base() : set(0) { }
    iterator_base(const compact_set_base* s) : set(s) { }
    iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
    friend class compact_set_base;
  public:
    iterator_base(const iterator_base& o) {
      set = o.set;
      it = o.it;
    }
    bool operator==(const iterator_base& o) const {
      return (set == o.set) && (!set->set || it == o.it);
    }
    bool operator!=(const iterator_base& o) const {
      return !(*this == o);;
    }
    iterator_base& operator=(const iterator_base& o) {
      set->set = o.set;
      it = o.it;
      return *this;
    }
    iterator_base& operator++() {
      ++it;
      return *this;
    }
    iterator_base operator++(int) {
      iterator_base tmp = *this;
      ++it;
      return tmp;
    }
    iterator_base& operator--() {
      --it;
      return *this;
    }
    const T& operator*() {
      return *it;
    }
  };
public:
  class const_iterator : public iterator_base<typename Set::const_iterator> {
    public:
      const_iterator() { }
      const_iterator(const iterator_base<typename Set::const_iterator>& o)
	: iterator_base<typename Set::const_iterator>(o) { }
      const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
      const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
	: iterator_base<typename Set::const_iterator>(s, i) { }
  };
  class iterator : public iterator_base<typename Set::iterator> {
    public:
      iterator() { }
      iterator(const iterator_base<typename Set::iterator>& o)
	: iterator_base<typename Set::iterator>(o) { }
      iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
      iterator(compact_set_base* s, const typename Set::iterator& i)
	: iterator_base<typename Set::iterator>(s, i) { }
      operator const_iterator() const {
	return const_iterator(this->set, this->it);
      }
  };
  class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
    public:
      const_reverse_iterator() { }
      const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
	: iterator_base<typename Set::const_reverse_iterator>(o) { }
      const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
      const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
	: iterator_base<typename Set::const_reverse_iterator>(s, i) { }
  };
  class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
    public:
      reverse_iterator() { }
      reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
	: iterator_base<typename Set::reverse_iterator>(o) { }
      reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
      reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
	: iterator_base<typename Set::reverse_iterator>(s, i) { }
      operator const_iterator() const {
	return const_iterator(this->set, this->it);
      }
  };

  compact_set_base() {}
  compact_set_base(const compact_set_base& o) {
    if (o.set) {
      alloc_internal();
      *set = *o.set;
    }
  }
  ~compact_set_base() {}


  bool empty() const {
    return !set || set->empty();
  }
  size_t size() const {
    return set ? set->size() : 0;
  }
  bool operator==(const compact_set_base& o) const {
    return (empty() && o.empty()) || (set && o.set && *set == *o.set);
  }
  bool operator!=(const compact_set_base& o) const {
    return !(*this == o);
  }
  size_t count(const T& t) const {
    return set ? set->count(t) : 0;
  }
  iterator erase (iterator p) {
    if (set) {
      ceph_assert(this == p.set);
      auto it = set->erase(p.it);
      if (set->empty()) {
        free_internal();
        return iterator(this);
      } else {
        return iterator(this, it);
      }
    } else {
      return iterator(this);
    }
  }
  size_t erase (const T& t) {
    if (!set)
      return 0;
    size_t r = set->erase(t);
    if (set->empty())
      free_internal();
    return r;
  }
  void clear() {
    free_internal();
  }
  void swap(compact_set_base& o) {
    set.swap(o.set);
  }
  compact_set_base& operator=(const compact_set_base& o) {
    if (o.set) {
      alloc_internal();
      *set = *o.set;
    } else
      free_internal();
    return *this;
  }
  std::pair<iterator,bool> insert(const T& t) {
    alloc_internal();
    std::pair<typename Set::iterator,bool> r = set->insert(t);
    return std::make_pair(iterator(this, r.first), r.second);
  }
  template <class... Args>
  std::pair<iterator,bool> emplace ( Args&&... args ) {
    alloc_internal();
    auto em = set->emplace(std::forward<Args>(args)...);
    return std::pair<iterator,bool>(iterator(this, em.first), em.second);
  }

  iterator begin() {
   if (!set)
     return iterator(this);
   return iterator(this, set->begin());
  }
  iterator end() {
   if (!set)
     return iterator(this);
   return iterator(this, set->end());
  }
  reverse_iterator rbegin() {
   if (!set)
     return reverse_iterator(this);
   return reverse_iterator(this, set->rbegin());
  }
  reverse_iterator rend() {
   if (!set)
     return reverse_iterator(this);
   return reverse_iterator(this, set->rend());
  }
  iterator find(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->find(t));
  }
  iterator lower_bound(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->lower_bound(t));
  }
  iterator upper_bound(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->upper_bound(t));
  }
  const_iterator begin() const {
   if (!set)
     return const_iterator(this);
   return const_iterator(this, set->begin());
  }
  const_iterator end() const {
   if (!set)
     return const_iterator(this);
   return const_iterator(this, set->end());
  }
  const_reverse_iterator rbegin() const {
   if (!set)
     return const_reverse_iterator(this);
   return const_reverse_iterator(this, set->rbegin());
  }
  const_reverse_iterator rend() const {
   if (!set)
     return const_reverse_iterator(this);
   return const_reverse_iterator(this, set->rend());
  }
  const_iterator find(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->find(t));
  }
  const_iterator lower_bound(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->lower_bound(t));
  }
  const_iterator upper_bound(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->upper_bound(t));
  }
  void encode(ceph::buffer::list &bl) const {
    using ceph::encode;
    if (set)
      encode(*set, bl);
    else
      encode((uint32_t)0, bl);
  }
  void decode(ceph::buffer::list::const_iterator& p) {
    using ceph::decode;
    uint32_t n;
    decode(n, p);
    if (n > 0) {
      alloc_internal();
      ceph::decode_nohead(n, *set, p);
    } else
      free_internal();
  }
};

template<class T, class Set>
inline void encode(const compact_set_base<T, Set>& m, ceph::buffer::list& bl) {
  m.encode(bl);
}
template<class T, class Set>
inline void decode(compact_set_base<T, Set>& m, ceph::buffer::list::const_iterator& p) {
  m.decode(p);
}

template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
class compact_set : public compact_set_base<T, std::set<T, Compare, Alloc> > {
};

template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
inline std::ostream& operator<<(std::ostream& out, const compact_set<T,Compare,Alloc>& s)
{
  bool first = true;
  for (auto &v : s) {
    if (!first)
      out << ",";
    out << v;
    first = false;
  }
  return out;
}
#endif
Commit	Line	Data
7c673cae FG	1	/*
	2	* Ceph - scalable distributed file system
	3	*
	4	* Copyright (C) 2015 Red Hat, Inc
	5	*
	6	* This is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU Lesser General Public
	8	* License version 2.1, as published by the Free Software
	9	* Foundation. See file COPYING.
	10	*
	11	*/
	12	#ifndef CEPH_COMPACT_SET_H
	13	#define CEPH_COMPACT_SET_H
	14
94b18763 FG	15	#include "buffer.h"
94b18763 FG	16	#include "encoding.h"
7c673cae	17
94b18763 FG	18	#include <memory>
94b18763 FG	19	#include <set>
7c673cae FG	20
	21	template <class T, class Set>
	22	class compact_set_base {
	23	protected:
94b18763	24	std::unique_ptr<Set> set;
7c673cae FG	25	void alloc_internal() {
7c673cae FG	26	if (!set)
94b18763	27	set.reset(new Set);
7c673cae FG	28	}
7c673cae FG	29	void free_internal() {
94b18763	30	set.reset();
7c673cae FG	31	}
	32	template <class It>
	33	class iterator_base {
	34	private:
	35	const compact_set_base* set;
	36	It it;
	37	iterator_base() : set(0) { }
	38	iterator_base(const compact_set_base* s) : set(s) { }
	39	iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
	40	friend class compact_set_base;
	41	public:
	42	iterator_base(const iterator_base& o) {
	43	set = o.set;
	44	it = o.it;
	45	}
	46	bool operator==(const iterator_base& o) const {
	47	return (set == o.set) && (!set->set \|\| it == o.it);
	48	}
	49	bool operator!=(const iterator_base& o) const {
	50	return !(*this == o);;
	51	}
	52	iterator_base& operator=(const iterator_base& o) {
	53	set->set = o.set;
	54	it = o.it;
	55	return *this;
	56	}
	57	iterator_base& operator++() {
	58	++it;
	59	return *this;
	60	}
	61	iterator_base operator++(int) {
	62	iterator_base tmp = *this;
	63	++it;
	64	return tmp;
	65	}
	66	iterator_base& operator--() {
	67	--it;
	68	return *this;
	69	}
	70	const T& operator*() {
	71	return *it;
	72	}
	73	};
	74	public:
	75	class const_iterator : public iterator_base<typename Set::const_iterator> {
	76	public:
	77	const_iterator() { }
	78	const_iterator(const iterator_base<typename Set::const_iterator>& o)
	79	: iterator_base<typename Set::const_iterator>(o) { }
	80	const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
	81	const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
	82	: iterator_base<typename Set::const_iterator>(s, i) { }
	83	};
	84	class iterator : public iterator_base<typename Set::iterator> {
	85	public:
	86	iterator() { }
	87	iterator(const iterator_base<typename Set::iterator>& o)
	88	: iterator_base<typename Set::iterator>(o) { }
	89	iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
	90	iterator(compact_set_base* s, const typename Set::iterator& i)
	91	: iterator_base<typename Set::iterator>(s, i) { }
	92	operator const_iterator() const {
	93	return const_iterator(this->set, this->it);
	94	}
95	};
96	class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
97	public:
98	const_reverse_iterator() { }
99	const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
100	: iterator_base<typename Set::const_reverse_iterator>(o) { }
101	const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
102	const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
103	: iterator_base<typename Set::const_reverse_iterator>(s, i) { }
104	};
105	class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
106	public:
107	reverse_iterator() { }
108	reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
109	: iterator_base<typename Set::reverse_iterator>(o) { }
110	reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
111	reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
112	: iterator_base<typename Set::reverse_iterator>(s, i) { }
113	operator const_iterator() const {
114	return const_iterator(this->set, this->it);
115	}
116	};
117
94b18763 FG	118	compact_set_base() {}
94b18763 FG	119	compact_set_base(const compact_set_base& o) {
7c673cae FG	120	if (o.set) {
	121	alloc_internal();
	122	set = o.set;
	123	}
	124	}
94b18763	125	~compact_set_base() {}
7c673cae FG	126
	127
	128	bool empty() const {
	129	return !set \|\| set->empty();
	130	}
	131	size_t size() const {
	132	return set ? set->size() : 0;
	133	}
	134	bool operator==(const compact_set_base& o) const {
	135	return (empty() && o.empty()) \|\| (set && o.set && set == o.set);
	136	}
	137	bool operator!=(const compact_set_base& o) const {
	138	return !(*this == o);
	139	}
	140	size_t count(const T& t) const {
	141	return set ? set->count(t) : 0;
	142	}
94b18763	143	iterator erase (iterator p) {
7c673cae	144	if (set) {
11fdf7f2	145	ceph_assert(this == p.set);
94b18763 FG	146	auto it = set->erase(p.it);
	147	if (set->empty()) {
	148	free_internal();
	149	return iterator(this);
	150	} else {
	151	return iterator(this, it);
	152	}
	153	} else {
	154	return iterator(this);
7c673cae FG	155	}
	156	}
	157	size_t erase (const T& t) {
	158	if (!set)
	159	return 0;
	160	size_t r = set->erase(t);
	161	if (set->empty())
94b18763	162	free_internal();
7c673cae FG	163	return r;
	164	}
	165	void clear() {
	166	free_internal();
	167	}
	168	void swap(compact_set_base& o) {
94b18763	169	set.swap(o.set);
7c673cae FG	170	}
	171	compact_set_base& operator=(const compact_set_base& o) {
	172	if (o.set) {
	173	alloc_internal();
	174	set = o.set;
	175	} else
	176	free_internal();
	177	return *this;
	178	}
	179	std::pair<iterator,bool> insert(const T& t) {
	180	alloc_internal();
	181	std::pair<typename Set::iterator,bool> r = set->insert(t);
	182	return std::make_pair(iterator(this, r.first), r.second);
	183	}
94b18763 FG	184	template <class... Args>
	185	std::pair<iterator,bool> emplace ( Args&&... args ) {
	186	alloc_internal();
	187	auto em = set->emplace(std::forward<Args>(args)...);
	188	return std::pair<iterator,bool>(iterator(this, em.first), em.second);
	189	}
	190
7c673cae FG	191	iterator begin() {
	192	if (!set)
	193	return iterator(this);
	194	return iterator(this, set->begin());
	195	}
	196	iterator end() {
	197	if (!set)
	198	return iterator(this);
	199	return iterator(this, set->end());
	200	}
	201	reverse_iterator rbegin() {
	202	if (!set)
	203	return reverse_iterator(this);
	204	return reverse_iterator(this, set->rbegin());
	205	}
	206	reverse_iterator rend() {
	207	if (!set)
	208	return reverse_iterator(this);
	209	return reverse_iterator(this, set->rend());
	210	}
	211	iterator find(const T& t) {
	212	if (!set)
	213	return iterator(this);
	214	return iterator(this, set->find(t));
	215	}
	216	iterator lower_bound(const T& t) {
	217	if (!set)
	218	return iterator(this);
	219	return iterator(this, set->lower_bound(t));
	220	}
	221	iterator upper_bound(const T& t) {
	222	if (!set)
	223	return iterator(this);
	224	return iterator(this, set->upper_bound(t));
	225	}
	226	const_iterator begin() const {
	227	if (!set)
	228	return const_iterator(this);
	229	return const_iterator(this, set->begin());
	230	}
	231	const_iterator end() const {
	232	if (!set)
	233	return const_iterator(this);
	234	return const_iterator(this, set->end());
	235	}
	236	const_reverse_iterator rbegin() const {
	237	if (!set)
	238	return const_reverse_iterator(this);
	239	return const_reverse_iterator(this, set->rbegin());
	240	}
	241	const_reverse_iterator rend() const {
	242	if (!set)
	243	return const_reverse_iterator(this);
	244	return const_reverse_iterator(this, set->rend());
	245	}
	246	const_iterator find(const T& t) const {
	247	if (!set)
	248	return const_iterator(this);
	249	return const_iterator(this, set->find(t));
	250	}
	251	const_iterator lower_bound(const T& t) const {
	252	if (!set)
	253	return const_iterator(this);
	254	return const_iterator(this, set->lower_bound(t));
255	}
256	const_iterator upper_bound(const T& t) const {
257	if (!set)
258	return const_iterator(this);
259	return const_iterator(this, set->upper_bound(t));
260	}
9f95a23c	261	void encode(ceph::buffer::list &bl) const {
11fdf7f2	262	using ceph::encode;
7c673cae	263	if (set)
11fdf7f2	264	encode(*set, bl);
7c673cae	265	else
11fdf7f2	266	encode((uint32_t)0, bl);
7c673cae	267	}
9f95a23c	268	void decode(ceph::buffer::list::const_iterator& p) {
11fdf7f2	269	using ceph::decode;
7c673cae	270	uint32_t n;
11fdf7f2	271	decode(n, p);
7c673cae FG	272	if (n > 0) {
7c673cae FG	273	alloc_internal();
f67539c2	274	ceph::decode_nohead(n, *set, p);
7c673cae FG	275	} else
	276	free_internal();
	277	}
	278	};
	279
	280	template<class T, class Set>
9f95a23c	281	inline void encode(const compact_set_base<T, Set>& m, ceph::buffer::list& bl) {
7c673cae FG	282	m.encode(bl);
	283	}
	284	template<class T, class Set>
9f95a23c	285	inline void decode(compact_set_base<T, Set>& m, ceph::buffer::list::const_iterator& p) {
7c673cae FG	286	m.decode(p);
	287	}
	288
94b18763 FG	289	template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
94b18763 FG	290	class compact_set : public compact_set_base<T, std::set<T, Compare, Alloc> > {
7c673cae FG	291	};
7c673cae FG	292
94b18763 FG	293	template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
94b18763 FG	294	inline std::ostream& operator<<(std::ostream& out, const compact_set<T,Compare,Alloc>& s)
7c673cae	295	{
94b18763 FG	296	bool first = true;
	297	for (auto &v : s) {
	298	if (!first)
7c673cae	299	out << ",";
94b18763 FG	300	out << v;
94b18763 FG	301	first = false;
7c673cae FG	302	}
	303	return out;
	304	}
	305	#endif