Initial TreeSortedMap and SortedMap in C++ (#980)

* Prepare for TreeSortedMap
  * Factor out SortedMapBase
  * Move ArraySortedMap to impl
  * Factor out SortedMap testing utilities

* Add a minimal TreeSortedMap

* Add the public SortedMap type

1 files changed, 64 insertions, 0 deletions

diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h b/Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h
new file mode 100644
index 0000000..accb5ef
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_MAP_BASE_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_MAP_BASE_H_
+
+#include <stdint.h>
+
+namespace firebase {
+namespace firestore {
+namespace immutable {
+namespace impl {
+
+/**
+ * A base class for implementing sorted maps, containing types and constants
+ * that don't depend upon the template parameters to the main class.
+ *
+ * Note that this exists as a base class rather than as just a namespace in
+ * order to make it possible for users of the SortedMap classes to avoid needing
+ * to declare storage for each instantiation of the template.
+ */
+class SortedMapBase {
+ public:
+  /**
+   * The type of size() methods on immutable collections. Note:
+   *   * This is not size_t specifically to save space in the TreeSortedMap
+   *     implementation.
+   *   * This remains unsigned for straightforward casting to size_t.
+   */
+  using size_type = uint32_t;
+
+  /**
+   * The maximum size of an ArraySortedMap.
+   *
+   * This is the size threshold where we use a tree backed sorted map instead of
+   * an array backed sorted map. This is a more or less arbitrary chosen value,
+   * that was chosen to be large enough to fit most of object kind of Firebase
+   * data, but small enough to not notice degradation in performance for
+   * inserting and lookups. Feel free to empirically determine this constant,
+   * but don't expect much gain in real world performance.
+   */
+  // TODO(wilhuff): actually use this for switching implementations.
+  static constexpr size_type kFixedSize = 25;
+};
+
+}  // namespace impl
+}  // namespace immutable
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_MAP_BASE_H_