1 /* 2 * index.h 3 * Copyright 2014-2016 John Lindgren 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright notice, 9 * this list of conditions, and the following disclaimer. 10 * 11 * 2. Redistributions in binary form must reproduce the above copyright notice, 12 * this list of conditions, and the following disclaimer in the documentation 13 * provided with the distribution. 14 * 15 * This software is provided "as is" and without any warranty, express or 16 * implied. In no event shall the authors be liable for any damages arising from 17 * the use of this software. 18 */ 19 20 #ifndef LIBAUDCORE_INDEX_H 21 #define LIBAUDCORE_INDEX_H 22 23 #include <libaudcore/templates.h> 24 25 /* 26 * Index is a lightweight list class similar to std::vector, but with the 27 * following differences: 28 * - The base implementation is type-agnostic, so it only needs to be compiled 29 * once. Type-safety is provided by a thin template subclass. 30 * - Objects are moved in memory without calling any assignment operator. 31 * Be careful to use only objects that can handle this. 32 */ 33 34 class IndexBase 35 { 36 public: 37 typedef int (*CompareFunc)(const void * a, const void * b, void * userdata); 38 IndexBase()39 constexpr IndexBase() : m_data(nullptr), m_len(0), m_size(0) {} 40 41 void clear(aud::EraseFunc erase_func); // use as destructor 42 IndexBase(IndexBase && b)43 IndexBase(IndexBase && b) 44 : m_data(b.m_data), m_len(b.m_len), m_size(b.m_size) 45 { 46 b.m_data = nullptr; 47 b.m_len = 0; 48 b.m_size = 0; 49 } 50 begin()51 void * begin() { return m_data; } begin()52 const void * begin() const { return m_data; } end()53 void * end() { return (char *)m_data + m_len; } end()54 const void * end() const { return (char *)m_data + m_len; } 55 len()56 int len() const { return m_len; } 57 58 void * insert(int pos, int len); // no fill 59 void insert(int pos, int len, aud::FillFunc fill_func); 60 void insert(const void * from, int pos, int len, aud::CopyFunc copy_func); 61 void remove(int pos, int len, aud::EraseFunc erase_func); 62 void erase(int pos, int len, aud::FillFunc fill_func, 63 aud::EraseFunc erase_func); 64 void shift(int from, int to, int len, aud::FillFunc fill_func, 65 aud::EraseFunc erase_func); 66 67 void move_from(IndexBase & b, int from, int to, int len, bool expand, 68 bool collapse, aud::FillFunc fill_func, 69 aud::EraseFunc erase_func); 70 71 void sort(CompareFunc compare, int elemsize, void * userdata); 72 int bsearch(const void * key, CompareFunc search, int elemsize, 73 void * userdata) const; 74 75 private: 76 void * m_data; 77 int m_len, m_size; 78 }; 79 80 template<class T> 81 class Index : private IndexBase 82 { 83 private: 84 // provides C-style callback to generic comparison functor 85 template<class Key, class F> 86 struct WrapCompare 87 { runWrapCompare88 static int run(const void * key, const void * val, void * func) 89 { 90 return (*(F *)func)(*(const Key *)key, *(const T *)val); 91 } 92 }; 93 94 public: Index()95 constexpr Index() : IndexBase() {} 96 97 // use with care! base()98 IndexBase & base() { return *this; } 99 clear()100 void clear() { IndexBase::clear(aud::erase_func<T>()); } ~Index()101 ~Index() { clear(); } 102 Index(Index && b)103 Index(Index && b) : IndexBase(std::move(b)) {} 104 Index & operator=(Index && b) 105 { 106 return aud::move_assign(*this, std::move(b)); 107 } 108 begin()109 T * begin() { return (T *)IndexBase::begin(); } begin()110 const T * begin() const { return (const T *)IndexBase::begin(); } end()111 T * end() { return (T *)IndexBase::end(); } end()112 const T * end() const { return (const T *)IndexBase::end(); } 113 len()114 int len() const { return cooked(IndexBase::len()); } 115 116 T & operator[](int i) { return begin()[i]; } 117 const T & operator[](int i) const { return begin()[i]; } 118 insert(int pos,int len)119 void insert(int pos, int len) 120 { 121 IndexBase::insert(raw(pos), raw(len), aud::fill_func<T>()); 122 } 123 insert(const T * from,int pos,int len)124 void insert(const T * from, int pos, int len) 125 { 126 IndexBase::insert(from, raw(pos), raw(len), aud::copy_func<T>()); 127 } 128 remove(int pos,int len)129 void remove(int pos, int len) 130 { 131 IndexBase::remove(raw(pos), raw(len), aud::erase_func<T>()); 132 } 133 erase(int pos,int len)134 void erase(int pos, int len) 135 { 136 IndexBase::erase(raw(pos), raw(len), aud::fill_func<T>(), 137 aud::erase_func<T>()); 138 } 139 shift(int from,int to,int len)140 void shift(int from, int to, int len) 141 { 142 IndexBase::shift(raw(from), raw(to), raw(len), aud::fill_func<T>(), 143 aud::erase_func<T>()); 144 } 145 move_from(Index<T> & b,int from,int to,int len,bool expand,bool collapse)146 void move_from(Index<T> & b, int from, int to, int len, bool expand, 147 bool collapse) 148 { 149 IndexBase::move_from(b, raw(from), raw(to), raw(len), expand, collapse, 150 aud::fill_func<T>(), aud::erase_func<T>()); 151 } 152 153 template<class... Args> append(Args &&...args)154 T & append(Args &&... args) 155 { 156 return *aud::construct<T>::make(IndexBase::insert(-1, sizeof(T)), 157 std::forward<Args>(args)...); 158 } 159 find(const T & val)160 int find(const T & val) const 161 { 162 for (const T * iter = begin(); iter != end(); iter++) 163 { 164 if (*iter == val) 165 return iter - begin(); 166 } 167 168 return -1; 169 } 170 171 // func(val) returns true to remove val, false to keep it 172 template<class F> 173 bool remove_if(F func, bool clear_if_empty = false) 174 { 175 T * iter = begin(); 176 bool changed = false; 177 while (iter != end()) 178 { 179 if (func(*iter)) 180 { 181 remove(iter - begin(), 1); 182 changed = true; 183 } 184 else 185 iter++; 186 } 187 188 if (clear_if_empty && !len()) 189 clear(); 190 191 return changed; 192 } 193 194 // compare(a, b) returns <0 if a<b, 0 if a=b, >0 if a>b 195 template<class F> sort(F compare)196 void sort(F compare) 197 { 198 IndexBase::sort(WrapCompare<T, F>::run, sizeof(T), &compare); 199 } 200 201 // compare(key, val) returns <0 if key<val, 0 if key=val, >0 if key>val 202 template<class Key, class F> bsearch(const Key & key,F compare)203 int bsearch(const Key & key, F compare) 204 { 205 return IndexBase::bsearch(&key, WrapCompare<Key, F>::run, sizeof(T), 206 &compare); 207 } 208 209 // for use of Index as a raw data buffer 210 // unlike insert(), does not zero-fill any added space resize(int size)211 void resize(int size) 212 { 213 static_assert(std::is_trivial<T>::value, "for basic types only"); 214 int diff = size - len(); 215 if (diff > 0) 216 IndexBase::insert(-1, raw(diff)); 217 else if (diff < 0) 218 IndexBase::remove(raw(size), -1, nullptr); 219 } 220 221 private: raw(int len)222 static constexpr int raw(int len) { return len * sizeof(T); } cooked(int len)223 static constexpr int cooked(int len) { return len / sizeof(T); } 224 }; 225 226 #endif // LIBAUDCORE_INDEX_H 227