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