+ if (array == static_array) {
+ new_array = (Type *) calloc (new_allocated, sizeof (Type));
+ if (new_array)
+ memcpy (new_array, array, len * sizeof (Type));
+ } else {
+ bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type));
+ if (likely (!overflows)) {
+ new_array = (Type *) realloc (array, new_allocated * sizeof (Type));
+ }
+ }
+
+ if (unlikely (!new_array))
+ return NULL;
+
+ array = new_array;
+ allocated = new_allocated;
+ return &array[len++];
+ }
+
+ inline void pop (void)
+ {
+ len--;
+ /* TODO: shrink array if needed */
+ }
+
+ inline void shrink (unsigned int l)
+ {
+ if (l < len)
+ len = l;
+ /* TODO: shrink array if needed */
+ }
+
+ template <typename T>
+ inline Type *find (T v) {
+ for (unsigned int i = 0; i < len; i++)
+ if (array[i] == v)
+ return &array[i];
+ return NULL;
+ }
+ template <typename T>
+ inline const Type *find (T v) const {
+ for (unsigned int i = 0; i < len; i++)
+ if (array[i] == v)
+ return &array[i];
+ return NULL;
+ }
+
+ inline void sort (void)
+ {
+ qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
+ }
+
+ inline void sort (unsigned int start, unsigned int end)
+ {
+ qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp);
+ }
+
+ template <typename T>
+ inline Type *bsearch (T *key)
+ {
+ return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
+ }
+ template <typename T>
+ inline const Type *bsearch (T *key) const
+ {
+ return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
+ }
+
+ inline void finish (void)
+ {
+ if (array != static_array)
+ free (array);
+ array = NULL;
+ allocated = len = 0;
+ }
+};
+
+template <typename Type>
+struct hb_array_t : hb_prealloced_array_t<Type, 2> {};
+
+
+template <typename item_t, typename lock_t>
+struct hb_lockable_set_t
+{
+ hb_array_t <item_t> items;
+
+ template <typename T>
+ inline item_t *replace_or_insert (T v, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item) {
+ item_t old = *item;
+ *item = v;
+ l.unlock ();
+ old.finish ();
+ } else {
+ item = items.push ();
+ if (likely (item))
+ *item = v;
+ l.unlock ();
+ }
+ return item;
+ }
+
+ template <typename T>
+ inline void remove (T v, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item) {
+ item_t old = *item;
+ *item = items[items.len - 1];
+ items.pop ();
+ l.unlock ();
+ old.finish ();
+ } else {
+ l.unlock ();
+ }
+ }
+
+ template <typename T>
+ inline bool find (T v, item_t *i, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item)
+ *i = *item;
+ l.unlock ();
+ return !!item;
+ }
+
+ template <typename T>
+ inline item_t *find_or_insert (T v, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (!item) {
+ item = items.push ();
+ if (likely (item))
+ *item = v;
+ }
+ l.unlock ();
+ return item;
+ }
+
+ inline void finish (lock_t &l)
+ {
+ l.lock ();
+ while (items.len) {
+ item_t old = items[items.len - 1];
+ items.pop ();
+ l.unlock ();
+ old.finish ();
+ l.lock ();
+ }
+ items.finish ();
+ l.unlock ();
+ }
+
+};
+
+
+HB_BEGIN_DECLS