1 /* 2 * FDBLoanerTypes.h 3 * 4 * This source file is part of the FoundationDB open source project 5 * 6 * Copyright 2013-2018 Apple Inc. and the FoundationDB project authors 7 * 8 * Licensed under the Apache License, Version 2.0 (the "License"); 9 * you may not use this file except in compliance with the License. 10 * You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 21 #ifndef FDB_FLOW_LOANER_TYPES_H 22 #define FDB_FLOW_LOANER_TYPES_H 23 24 namespace FDB { 25 typedef StringRef KeyRef; 26 typedef StringRef ValueRef; 27 28 typedef int64_t Version; 29 30 typedef Standalone<KeyRef> Key; 31 typedef Standalone<ValueRef> Value; 32 keyAfter(const KeyRef & key)33 inline Key keyAfter( const KeyRef& key ) { 34 if(key == LiteralStringRef("\xff\xff")) 35 return key; 36 37 Standalone<StringRef> r; 38 uint8_t* s = new (r.arena()) uint8_t[ key.size() + 1 ]; 39 memcpy(s, key.begin(), key.size() ); 40 s[key.size()] = 0; 41 ((StringRef&) r) = StringRef( s, key.size() + 1 ); 42 return r; 43 } 44 keyAfter(const KeyRef & key,Arena & arena)45 inline KeyRef keyAfter( const KeyRef& key, Arena& arena ) { 46 if(key == LiteralStringRef("\xff\xff")) 47 return key; 48 uint8_t* t = new ( arena ) uint8_t[ key.size()+1 ]; 49 memcpy(t, key.begin(), key.size() ); 50 t[key.size()] = 0; 51 return KeyRef(t,key.size()+1); 52 } 53 54 struct KeySelectorRef { 55 KeyRef key; // Find the last item less than key 56 bool orEqual; // (or equal to key, if this is true) 57 int offset; // and then move forward this many items (or backward if negative) KeySelectorRefKeySelectorRef58 KeySelectorRef() {} KeySelectorRefKeySelectorRef59 KeySelectorRef( const KeyRef& key, bool orEqual, int offset ) : key(key), orEqual(orEqual), offset(offset) {} 60 KeySelectorRefKeySelectorRef61 KeySelectorRef( Arena& arena, const KeySelectorRef& copyFrom ) : key(arena,copyFrom.key), orEqual(copyFrom.orEqual), offset(copyFrom.offset) {} expectedSizeKeySelectorRef62 int expectedSize() const { return key.expectedSize(); } 63 64 // std::string toString() const { 65 // if (offset > 0) { 66 // if (orEqual) return format("firstGreaterThan(%s)%+d", printable(key).c_str(), offset-1); 67 // else return format("firstGreaterOrEqual(%s)%+d", printable(key).c_str(), offset-1); 68 // } else { 69 // if (orEqual) return format("lastLessOrEqual(%s)%+d", printable(key).c_str(), offset); 70 // else return format("lastLessThan(%s)%+d", printable(key).c_str(), offset); 71 // } 72 // } 73 isBackwardKeySelectorRef74 bool isBackward() const { return !orEqual && offset<=0; } // True if the resolution of the KeySelector depends only on keys less than key isFirstGreaterOrEqualKeySelectorRef75 bool isFirstGreaterOrEqual() const { return !orEqual && offset==1; } isFirstGreaterThanKeySelectorRef76 bool isFirstGreaterThan() const { return orEqual && offset==1; } isLastLessOrEqualKeySelectorRef77 bool isLastLessOrEqual() const { return orEqual && offset==0; } 78 79 // True iff, regardless of the contents of the database, lhs must resolve to a key > rhs isDefinitelyGreaterKeySelectorRef80 bool isDefinitelyGreater( KeyRef const& k ) { 81 return offset >= 1 && ( isFirstGreaterOrEqual() ? key > k : key >= k ); 82 } 83 // True iff, regardless of the contents of the database, lhs must resolve to a key < rhs isDefinitelyLessKeySelectorRef84 bool isDefinitelyLess( KeyRef const& k ) { 85 return offset <= 0 && ( isLastLessOrEqual() ? key < k : key <= k ); 86 } 87 88 template <class Ar> serializeKeySelectorRef89 void serialize( Ar& ar ) { 90 serializer(ar, key, orEqual, offset); 91 } 92 }; 93 inline bool operator == (const KeySelectorRef& lhs, const KeySelectorRef& rhs) { return lhs.key == rhs.key && lhs.orEqual==rhs.orEqual && lhs.offset==rhs.offset; } lastLessThan(const KeyRef & k)94 inline KeySelectorRef lastLessThan( const KeyRef& k ) { 95 return KeySelectorRef( k, false, 0 ); 96 } lastLessOrEqual(const KeyRef & k)97 inline KeySelectorRef lastLessOrEqual( const KeyRef& k ) { 98 return KeySelectorRef( k, true, 0 ); 99 } firstGreaterThan(const KeyRef & k)100 inline KeySelectorRef firstGreaterThan( const KeyRef& k ) { 101 return KeySelectorRef( k, true, +1 ); 102 } firstGreaterOrEqual(const KeyRef & k)103 inline KeySelectorRef firstGreaterOrEqual( const KeyRef& k ) { 104 return KeySelectorRef( k, false, +1 ); 105 } 106 inline KeySelectorRef operator + (const KeySelectorRef& s, int off) { 107 return KeySelectorRef(s.key, s.orEqual, s.offset+off); 108 } 109 inline KeySelectorRef operator - (const KeySelectorRef& s, int off) { 110 return KeySelectorRef(s.key, s.orEqual, s.offset-off); 111 } 112 113 typedef Standalone<KeySelectorRef> KeySelector; 114 115 struct KeyValueRef { 116 KeyRef key; 117 ValueRef value; KeyValueRefKeyValueRef118 KeyValueRef() {} KeyValueRefKeyValueRef119 KeyValueRef( const KeyRef& key, const ValueRef& value ) : key(key), value(value) {} KeyValueRefKeyValueRef120 KeyValueRef( Arena& a, const KeyValueRef& copyFrom ) : key(a, copyFrom.key), value(a, copyFrom.value) {} 121 bool operator == ( const KeyValueRef& r ) const { return key == r.key && value == r.value; } 122 expectedSizeKeyValueRef123 int expectedSize() const { return key.expectedSize() + value.expectedSize(); } 124 125 template <class Ar> serializeKeyValueRef126 force_inline void serialize(Ar& ar) { serializer(ar, key, value); } 127 128 struct OrderByKey { operatorKeyValueRef::OrderByKey129 bool operator()(KeyValueRef const& a, KeyValueRef const& b) const { 130 return a.key < b.key; 131 } 132 template <class T> operatorKeyValueRef::OrderByKey133 bool operator()(T const& a, KeyValueRef const& b) const { 134 return a < b.key; 135 } 136 template <class T> operatorKeyValueRef::OrderByKey137 bool operator()(KeyValueRef const& a, T const& b) const { 138 return a.key < b; 139 } 140 }; 141 142 struct OrderByKeyBack { operatorKeyValueRef::OrderByKeyBack143 bool operator()(KeyValueRef const& a, KeyValueRef const& b) const { 144 return a.key > b.key; 145 } 146 template <class T> operatorKeyValueRef::OrderByKeyBack147 bool operator()(T const& a, KeyValueRef const& b) const { 148 return a > b.key; 149 } 150 template <class T> operatorKeyValueRef::OrderByKeyBack151 bool operator()(KeyValueRef const& a, T const& b) const { 152 return a.key > b; 153 } 154 }; 155 }; 156 157 typedef Standalone<KeyValueRef> KeyValue; 158 159 struct RangeResultRef : VectorRef<KeyValueRef> { 160 bool more; // True if (but not necessarily only if) values remain in the *key* range requested (possibly beyond the limits requested) 161 // False implies that no such values remain 162 Optional<KeyRef> readThrough; // Only present when 'more' is true. When present, this value represent the end (or beginning if reverse) of the range 163 // which was read to produce these results. This is guarenteed to be less than the requested range. 164 bool readToBegin; 165 bool readThroughEnd; 166 RangeResultRefRangeResultRef167 RangeResultRef() : more(false), readToBegin(false), readThroughEnd(false) {} RangeResultRefRangeResultRef168 RangeResultRef( Arena& p, const RangeResultRef& toCopy ) : more( toCopy.more ), readToBegin( toCopy.readToBegin ), readThroughEnd( toCopy.readThroughEnd ), readThrough( toCopy.readThrough.present() ? KeyRef( p, toCopy.readThrough.get() ) : Optional<KeyRef>() ), VectorRef<KeyValueRef>( p, toCopy ) {} 169 RangeResultRef( const VectorRef<KeyValueRef>& value, bool more, Optional<KeyRef> readThrough = Optional<KeyRef>() ) : VectorRef<KeyValueRef>( value ), more( more ), readThrough( readThrough ), readToBegin( false ), readThroughEnd( false ) {} RangeResultRefRangeResultRef170 RangeResultRef( bool readToBegin, bool readThroughEnd ) : more(false), readToBegin(readToBegin), readThroughEnd(readThroughEnd) { } 171 172 template <class Ar> serializeRangeResultRef173 void serialize( Ar& ar ) { 174 serializer(ar, ((VectorRef<KeyValueRef>&)*this), more, readThrough, readToBegin, readThroughEnd); 175 } 176 }; 177 178 struct GetRangeLimits { 179 enum { ROW_LIMIT_UNLIMITED = -1, BYTE_LIMIT_UNLIMITED = -1 }; 180 181 int rows; 182 int minRows; 183 int bytes; 184 GetRangeLimitsGetRangeLimits185 GetRangeLimits() : rows( ROW_LIMIT_UNLIMITED ), minRows(1), bytes( BYTE_LIMIT_UNLIMITED ) {} GetRangeLimitsGetRangeLimits186 explicit GetRangeLimits( int rowLimit ) : rows( rowLimit ), minRows(1), bytes( BYTE_LIMIT_UNLIMITED ) {} GetRangeLimitsGetRangeLimits187 GetRangeLimits( int rowLimit, int byteLimit ) : rows( rowLimit ), minRows(1), bytes( byteLimit ) {} 188 189 void decrement( VectorRef<KeyValueRef> const& data ); 190 void decrement( KeyValueRef const& data ); 191 192 // True if either the row or byte limit has been reached 193 bool isReached(); 194 195 // True if data would cause the row or byte limit to be reached 196 bool reachedBy( VectorRef<KeyValueRef> const& data ); 197 198 bool hasByteLimit(); 199 bool hasRowLimit(); 200 201 bool hasSatisfiedMinRows(); isValidGetRangeLimits202 bool isValid() { return (rows >= 0 || rows == ROW_LIMIT_UNLIMITED) 203 && (bytes >= 0 || bytes == BYTE_LIMIT_UNLIMITED) 204 && minRows >= 0 && (minRows <= rows || rows == ROW_LIMIT_UNLIMITED); } 205 }; 206 207 struct KeyRangeRef { 208 const KeyRef begin, end; KeyRangeRefKeyRangeRef209 KeyRangeRef() {} KeyRangeRefKeyRangeRef210 KeyRangeRef( const KeyRef& begin, const KeyRef& end ) : begin(begin), end(end) { 211 if( begin > end ) { 212 throw inverted_range(); 213 } 214 } KeyRangeRefKeyRangeRef215 KeyRangeRef( Arena& a, const KeyRangeRef& copyFrom ) : begin(a, copyFrom.begin), end(a, copyFrom.end) {} 216 bool operator == ( const KeyRangeRef& r ) const { return begin == r.begin && end == r.end; } 217 bool operator != ( const KeyRangeRef& r ) const { return begin != r.begin || end != r.end; } containsKeyRangeRef218 bool contains( const KeyRef& key ) const { return begin <= key && key < end; } containsKeyRangeRef219 bool contains( const KeyRangeRef& keys ) const { return begin <= keys.begin && keys.end <= end; } intersectsKeyRangeRef220 bool intersects( const KeyRangeRef& keys ) const { return begin < keys.end && keys.begin < end; } emptyKeyRangeRef221 bool empty() const { return begin == end; } 222 withPrefixKeyRangeRef223 Standalone<KeyRangeRef> withPrefix( const StringRef& prefix ) const { 224 return KeyRangeRef( begin.withPrefix(prefix), end.withPrefix(prefix) ); 225 } 226 227 const KeyRangeRef& operator = (const KeyRangeRef& rhs) { 228 const_cast<KeyRef&>(begin) = rhs.begin; 229 const_cast<KeyRef&>(end) = rhs.end; 230 return *this; 231 } 232 expectedSizeKeyRangeRef233 int expectedSize() const { return begin.expectedSize() + end.expectedSize(); } 234 235 template <class Ar> serializeKeyRangeRef236 force_inline void serialize(Ar& ar) { 237 serializer(ar, const_cast<KeyRef&>(begin), const_cast<KeyRef&>(end)); 238 if( begin > end ) { 239 throw inverted_range(); 240 }; 241 } 242 243 struct ArbitraryOrder { operatorKeyRangeRef::ArbitraryOrder244 bool operator()(KeyRangeRef const& a, KeyRangeRef const& b) const { 245 if (a.begin < b.begin) return true; 246 if (a.begin > b.begin) return false; 247 return a.end < b.end; 248 } 249 }; 250 }; 251 252 inline KeyRangeRef operator & (const KeyRangeRef& lhs, const KeyRangeRef& rhs) { 253 KeyRef b = std::max(lhs.begin, rhs.begin), e = std::min(lhs.end, rhs.end); 254 if (e < b) 255 return KeyRangeRef(); 256 return KeyRangeRef(b,e); 257 } 258 259 typedef Standalone<KeyRangeRef> KeyRange; 260 261 std::string printable( const StringRef& val ); 262 263 template <class T> describe(T const & item)264 static std::string describe(T const& item) { 265 return item.toString(); 266 } 267 template <class K, class V> 268 static std::string describe(std::map<K, V> const& items, int max_items = -1) { 269 if (!items.size()) 270 return "[no items]"; 271 272 std::string s; 273 int count = 0; 274 for (auto it = items.begin(); it != items.end(); it++) { 275 if (++count > max_items && max_items >= 0) 276 break; 277 if (count > 1) s += ","; 278 s += describe(it->first) + "=>" + describe(it->second); 279 } 280 return s; 281 } 282 283 template <class T> describeList(T const & items,int max_items)284 static std::string describeList(T const& items, int max_items) { 285 if (!items.size()) 286 return "[no items]"; 287 288 std::string s; 289 int count = 0; 290 for (auto const& item : items) { 291 if (++count > max_items && max_items >= 0) 292 break; 293 if (count > 1) s += ","; 294 s += describe(item); 295 } 296 return s; 297 } 298 299 template <class T> 300 static std::string describe(std::vector<T> const& items, int max_items = -1) { 301 return describeList(items, max_items); 302 } 303 304 template <class T> 305 static std::string describe(std::set<T> const& items, int max_items = -1) { 306 return describeList(items, max_items); 307 } 308 309 template <class T1, class T2> describe(std::pair<T1,T2> const & pair)310 static std::string describe(std::pair<T1, T2> const& pair) { 311 return "first: " + describe(pair.first) + " second: " + describe(pair.second); 312 } 313 } 314 315 #endif /* FDB_LOANER_TYPES_H */ 316