1 files changed, 73 insertions, 0 deletions
diff --git a/common/array.h b/common/array.h
index db1a62ba34..869d79b68b 100644
--- a/common/array.h
+++ b/common/array.h
@@ -361,6 +361,79 @@ protected:
 
 };
 
+/**
+ * Double linked list with sorted nodes.
+ */
+template<class T>
+class SortedArray : public Array<T> {
+public:
+	typedef T *iterator;
+	typedef uint size_type;
+
+	SortedArray(int (*comparator)(const void *, const void *)) {
+		_comparator = comparator;
+	}
+
+	/**
+	 * Inserts element at the sorted position.
+	 */
+	void insert(const T &element) {
+		T *where = (T *)bsearchMin(element, this->front(), this->_size, sizeof(T), _comparator);
+		insert(where, element);
+	}
+
+	T &operator[](size_type idx) {
+		error("Operation not allowed with SortedArray");
+	}
+
+	void insert_at(size_type idx, const T &element) {
+		error("Operation not allowed with SortedArray");
+	}
+
+	void insert_at(size_type idx, const Array<T> &array) {
+		error("Operation not allowed with SortedArray");
+	}
+
+	void insert(iterator pos, const T &element) {
+		error("Operation not allowed with SortedArray");
+	}
+
+	void push_back(const T &element) {
+		error("Operation not allowed with SortedArray");
+	}
+
+	void push_back(const Array<T> &array) {
+		error("Operation not allowed with SortedArray");
+	}
+
+private:
+	// Based on code Copyright (C) 2008-2009 Ksplice, Inc.
+	// Author: Tim Abbott <tabbott@ksplice.com>
+	// Licensed under GPLv2+
+	void *bsearchMin(const void *key, const void *base, uint num, uint size,
+					int (*cmp)(const void *key, const void *elt)) {
+		uint start = 0, end = num;
+		int result;
+
+		while (start < end) {
+			uint mid = start + (end - start) / 2;
+
+			result = cmp(key, (byte *)base + mid * size);
+			if (result < 0)
+				end = mid;
+			else if (result > 0)
+				start = mid + 1;
+			else
+				return (void *)((byte *)base + mid * size);
+		}
+
+		return (void *)((byte *)base + start * size);
+	}
+
+private:
+	int (*_comparator)(const void *, const void *);
+};
+
 } // End of namespace Common
 
 #endif