From 13ff01e20ca796676ba74d0b99065199eca9d309 Mon Sep 17 00:00:00 2001 From: Gil Date: Thu, 29 Mar 2018 08:31:47 -0700 Subject: 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 --- .../firebase/firestore/immutable/sorted_map_base.h | 64 ++++++++++++++++++++++ 1 file changed, 64 insertions(+) create mode 100644 Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h (limited to 'Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h') 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 + +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_ -- cgit v1.2.3