]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2013 Facebook |
2 | /** | |
3 | * A (persistent) Redis API built using the rocksdb backend. | |
4 | * Implements Redis Lists as described on: http://redis.io/commands#list | |
5 | * | |
6 | * @throws All functions may throw a RedisListException on error/corruption. | |
7 | * | |
8 | * @notes Internally, the set of lists is stored in a rocksdb database, | |
9 | * mapping keys to values. Each "value" is the list itself, storing | |
10 | * some kind of internal representation of the data. All the | |
11 | * representation details are handled by the RedisListIterator class. | |
12 | * The present file should be oblivious to the representation details, | |
13 | * handling only the client (Redis) API, and the calls to rocksdb. | |
14 | * | |
15 | * @TODO Presently, all operations take at least O(NV) time where | |
16 | * N is the number of elements in the list, and V is the average | |
17 | * number of bytes per value in the list. So maybe, with merge operator | |
18 | * we can improve this to an optimal O(V) amortized time, since we | |
19 | * wouldn't have to read and re-write the entire list. | |
20 | * | |
21 | * @author Deon Nicholas (dnicholas@fb.com) | |
22 | */ | |
23 | ||
24 | #ifndef ROCKSDB_LITE | |
25 | #include "redis_lists.h" | |
26 | ||
27 | #include <iostream> | |
28 | #include <memory> | |
29 | #include <cmath> | |
30 | ||
31 | #include "rocksdb/slice.h" | |
32 | #include "util/coding.h" | |
33 | ||
34 | namespace rocksdb | |
35 | { | |
36 | ||
37 | /// Constructors | |
38 | ||
39 | RedisLists::RedisLists(const std::string& db_path, | |
40 | Options options, bool destructive) | |
41 | : put_option_(), | |
42 | get_option_() { | |
43 | ||
44 | // Store the name of the database | |
45 | db_name_ = db_path; | |
46 | ||
47 | // If destructive, destroy the DB before re-opening it. | |
48 | if (destructive) { | |
49 | DestroyDB(db_name_, Options()); | |
50 | } | |
51 | ||
52 | // Now open and deal with the db | |
53 | DB* db; | |
54 | Status s = DB::Open(options, db_name_, &db); | |
55 | if (!s.ok()) { | |
56 | std::cerr << "ERROR " << s.ToString() << std::endl; | |
57 | assert(false); | |
58 | } | |
59 | ||
60 | db_ = std::unique_ptr<DB>(db); | |
61 | } | |
62 | ||
63 | ||
64 | /// Accessors | |
65 | ||
66 | // Number of elements in the list associated with key | |
67 | // : throws RedisListException | |
68 | int RedisLists::Length(const std::string& key) { | |
69 | // Extract the string data representing the list. | |
70 | std::string data; | |
71 | db_->Get(get_option_, key, &data); | |
72 | ||
73 | // Return the length | |
74 | RedisListIterator it(data); | |
75 | return it.Length(); | |
76 | } | |
77 | ||
78 | // Get the element at the specified index in the (list: key) | |
79 | // Returns <empty> ("") on out-of-bounds | |
80 | // : throws RedisListException | |
81 | bool RedisLists::Index(const std::string& key, int32_t index, | |
82 | std::string* result) { | |
83 | // Extract the string data representing the list. | |
84 | std::string data; | |
85 | db_->Get(get_option_, key, &data); | |
86 | ||
87 | // Handle REDIS negative indices (from the end); fast iff Length() takes O(1) | |
88 | if (index < 0) { | |
89 | index = Length(key) - (-index); //replace (-i) with (N-i). | |
90 | } | |
91 | ||
92 | // Iterate through the list until the desired index is found. | |
93 | int curIndex = 0; | |
94 | RedisListIterator it(data); | |
95 | while(curIndex < index && !it.Done()) { | |
96 | ++curIndex; | |
97 | it.Skip(); | |
98 | } | |
99 | ||
100 | // If we actually found the index | |
101 | if (curIndex == index && !it.Done()) { | |
102 | Slice elem; | |
103 | it.GetCurrent(&elem); | |
11fdf7f2 | 104 | if (result != nullptr) { |
7c673cae FG |
105 | *result = elem.ToString(); |
106 | } | |
107 | ||
108 | return true; | |
109 | } else { | |
110 | return false; | |
111 | } | |
112 | } | |
113 | ||
114 | // Return a truncated version of the list. | |
115 | // First, negative values for first/last are interpreted as "end of list". | |
116 | // So, if first == -1, then it is re-set to index: (Length(key) - 1) | |
117 | // Then, return exactly those indices i such that first <= i <= last. | |
118 | // : throws RedisListException | |
119 | std::vector<std::string> RedisLists::Range(const std::string& key, | |
120 | int32_t first, int32_t last) { | |
121 | // Extract the string data representing the list. | |
122 | std::string data; | |
123 | db_->Get(get_option_, key, &data); | |
124 | ||
125 | // Handle negative bounds (-1 means last element, etc.) | |
126 | int listLen = Length(key); | |
127 | if (first < 0) { | |
128 | first = listLen - (-first); // Replace (-x) with (N-x) | |
129 | } | |
130 | if (last < 0) { | |
131 | last = listLen - (-last); | |
132 | } | |
133 | ||
134 | // Verify bounds (and truncate the range so that it is valid) | |
135 | first = std::max(first, 0); | |
136 | last = std::min(last, listLen-1); | |
137 | int len = std::max(last-first+1, 0); | |
138 | ||
139 | // Initialize the resulting list | |
140 | std::vector<std::string> result(len); | |
141 | ||
142 | // Traverse the list and update the vector | |
143 | int curIdx = 0; | |
144 | Slice elem; | |
145 | for (RedisListIterator it(data); !it.Done() && curIdx<=last; it.Skip()) { | |
146 | if (first <= curIdx && curIdx <= last) { | |
147 | it.GetCurrent(&elem); | |
148 | result[curIdx-first].assign(elem.data(),elem.size()); | |
149 | } | |
150 | ||
151 | ++curIdx; | |
152 | } | |
153 | ||
154 | // Return the result. Might be empty | |
155 | return result; | |
156 | } | |
157 | ||
158 | // Print the (list: key) out to stdout. For debugging mostly. Public for now. | |
159 | void RedisLists::Print(const std::string& key) { | |
160 | // Extract the string data representing the list. | |
161 | std::string data; | |
162 | db_->Get(get_option_, key, &data); | |
163 | ||
164 | // Iterate through the list and print the items | |
165 | Slice elem; | |
166 | for (RedisListIterator it(data); !it.Done(); it.Skip()) { | |
167 | it.GetCurrent(&elem); | |
168 | std::cout << "ITEM " << elem.ToString() << std::endl; | |
169 | } | |
170 | ||
171 | //Now print the byte data | |
172 | RedisListIterator it(data); | |
173 | std::cout << "==Printing data==" << std::endl; | |
174 | std::cout << data.size() << std::endl; | |
175 | std::cout << it.Size() << " " << it.Length() << std::endl; | |
176 | Slice result = it.WriteResult(); | |
177 | std::cout << result.data() << std::endl; | |
178 | if (true) { | |
179 | std::cout << "size: " << result.size() << std::endl; | |
180 | const char* val = result.data(); | |
181 | for(int i=0; i<(int)result.size(); ++i) { | |
182 | std::cout << (int)val[i] << " " << (val[i]>=32?val[i]:' ') << std::endl; | |
183 | } | |
184 | std::cout << std::endl; | |
185 | } | |
186 | } | |
187 | ||
188 | /// Insert/Update Functions | |
189 | /// Note: The "real" insert function is private. See below. | |
190 | ||
191 | // InsertBefore and InsertAfter are simply wrappers around the Insert function. | |
192 | int RedisLists::InsertBefore(const std::string& key, const std::string& pivot, | |
193 | const std::string& value) { | |
194 | return Insert(key, pivot, value, false); | |
195 | } | |
196 | ||
197 | int RedisLists::InsertAfter(const std::string& key, const std::string& pivot, | |
198 | const std::string& value) { | |
199 | return Insert(key, pivot, value, true); | |
200 | } | |
201 | ||
202 | // Prepend value onto beginning of (list: key) | |
203 | // : throws RedisListException | |
204 | int RedisLists::PushLeft(const std::string& key, const std::string& value) { | |
205 | // Get the original list data | |
206 | std::string data; | |
207 | db_->Get(get_option_, key, &data); | |
208 | ||
209 | // Construct the result | |
210 | RedisListIterator it(data); | |
211 | it.Reserve(it.Size() + it.SizeOf(value)); | |
212 | it.InsertElement(value); | |
213 | ||
214 | // Push the data back to the db and return the length | |
215 | db_->Put(put_option_, key, it.WriteResult()); | |
216 | return it.Length(); | |
217 | } | |
218 | ||
219 | // Append value onto end of (list: key) | |
220 | // TODO: Make this O(1) time. Might require MergeOperator. | |
221 | // : throws RedisListException | |
222 | int RedisLists::PushRight(const std::string& key, const std::string& value) { | |
223 | // Get the original list data | |
224 | std::string data; | |
225 | db_->Get(get_option_, key, &data); | |
226 | ||
227 | // Create an iterator to the data and seek to the end. | |
228 | RedisListIterator it(data); | |
229 | it.Reserve(it.Size() + it.SizeOf(value)); | |
230 | while (!it.Done()) { | |
231 | it.Push(); // Write each element as we go | |
232 | } | |
233 | ||
234 | // Insert the new element at the current position (the end) | |
235 | it.InsertElement(value); | |
236 | ||
237 | // Push it back to the db, and return length | |
238 | db_->Put(put_option_, key, it.WriteResult()); | |
239 | return it.Length(); | |
240 | } | |
241 | ||
242 | // Set (list: key)[idx] = val. Return true on success, false on fail. | |
243 | // : throws RedisListException | |
244 | bool RedisLists::Set(const std::string& key, int32_t index, | |
245 | const std::string& value) { | |
246 | // Get the original list data | |
247 | std::string data; | |
248 | db_->Get(get_option_, key, &data); | |
249 | ||
250 | // Handle negative index for REDIS (meaning -index from end of list) | |
251 | if (index < 0) { | |
252 | index = Length(key) - (-index); | |
253 | } | |
254 | ||
255 | // Iterate through the list until we find the element we want | |
256 | int curIndex = 0; | |
257 | RedisListIterator it(data); | |
258 | it.Reserve(it.Size() + it.SizeOf(value)); // Over-estimate is fine | |
259 | while(curIndex < index && !it.Done()) { | |
260 | it.Push(); | |
261 | ++curIndex; | |
262 | } | |
263 | ||
264 | // If not found, return false (this occurs when index was invalid) | |
265 | if (it.Done() || curIndex != index) { | |
266 | return false; | |
267 | } | |
268 | ||
269 | // Write the new element value, and drop the previous element value | |
270 | it.InsertElement(value); | |
271 | it.Skip(); | |
272 | ||
273 | // Write the data to the database | |
274 | // Check status, since it needs to return true/false guarantee | |
275 | Status s = db_->Put(put_option_, key, it.WriteResult()); | |
276 | ||
277 | // Success | |
278 | return s.ok(); | |
279 | } | |
280 | ||
281 | /// Delete / Remove / Pop functions | |
282 | ||
283 | // Trim (list: key) so that it will only contain the indices from start..stop | |
284 | // Invalid indices will not generate an error, just empty, | |
285 | // or the portion of the list that fits in this interval | |
286 | // : throws RedisListException | |
287 | bool RedisLists::Trim(const std::string& key, int32_t start, int32_t stop) { | |
288 | // Get the original list data | |
289 | std::string data; | |
290 | db_->Get(get_option_, key, &data); | |
291 | ||
292 | // Handle negative indices in REDIS | |
293 | int listLen = Length(key); | |
294 | if (start < 0) { | |
295 | start = listLen - (-start); | |
296 | } | |
297 | if (stop < 0) { | |
298 | stop = listLen - (-stop); | |
299 | } | |
300 | ||
301 | // Truncate bounds to only fit in the list | |
302 | start = std::max(start, 0); | |
303 | stop = std::min(stop, listLen-1); | |
304 | ||
305 | // Construct an iterator for the list. Drop all undesired elements. | |
306 | int curIndex = 0; | |
307 | RedisListIterator it(data); | |
308 | it.Reserve(it.Size()); // Over-estimate | |
309 | while(!it.Done()) { | |
310 | // If not within the range, just skip the item (drop it). | |
311 | // Otherwise, continue as usual. | |
312 | if (start <= curIndex && curIndex <= stop) { | |
313 | it.Push(); | |
314 | } else { | |
315 | it.Skip(); | |
316 | } | |
317 | ||
318 | // Increment the current index | |
319 | ++curIndex; | |
320 | } | |
321 | ||
322 | // Write the (possibly empty) result to the database | |
323 | Status s = db_->Put(put_option_, key, it.WriteResult()); | |
324 | ||
325 | // Return true as long as the write succeeded | |
326 | return s.ok(); | |
327 | } | |
328 | ||
329 | // Return and remove the first element in the list (or "" if empty) | |
330 | // : throws RedisListException | |
331 | bool RedisLists::PopLeft(const std::string& key, std::string* result) { | |
332 | // Get the original list data | |
333 | std::string data; | |
334 | db_->Get(get_option_, key, &data); | |
335 | ||
336 | // Point to first element in the list (if it exists), and get its value/size | |
337 | RedisListIterator it(data); | |
338 | if (it.Length() > 0) { // Proceed only if list is non-empty | |
339 | Slice elem; | |
340 | it.GetCurrent(&elem); // Store the value of the first element | |
341 | it.Reserve(it.Size() - it.SizeOf(elem)); | |
342 | it.Skip(); // DROP the first item and move to next | |
343 | ||
344 | // Update the db | |
345 | db_->Put(put_option_, key, it.WriteResult()); | |
346 | ||
347 | // Return the value | |
11fdf7f2 | 348 | if (result != nullptr) { |
7c673cae FG |
349 | *result = elem.ToString(); |
350 | } | |
351 | return true; | |
352 | } else { | |
353 | return false; | |
354 | } | |
355 | } | |
356 | ||
357 | // Remove and return the last element in the list (or "" if empty) | |
358 | // TODO: Make this O(1). Might require MergeOperator. | |
359 | // : throws RedisListException | |
360 | bool RedisLists::PopRight(const std::string& key, std::string* result) { | |
361 | // Extract the original list data | |
362 | std::string data; | |
363 | db_->Get(get_option_, key, &data); | |
364 | ||
365 | // Construct an iterator to the data and move to last element | |
366 | RedisListIterator it(data); | |
367 | it.Reserve(it.Size()); | |
368 | int len = it.Length(); | |
369 | int curIndex = 0; | |
370 | while(curIndex < (len-1) && !it.Done()) { | |
371 | it.Push(); | |
372 | ++curIndex; | |
373 | } | |
374 | ||
375 | // Extract and drop/skip the last element | |
376 | if (curIndex == len-1) { | |
377 | assert(!it.Done()); // Sanity check. Should not have ended here. | |
378 | ||
379 | // Extract and pop the element | |
380 | Slice elem; | |
381 | it.GetCurrent(&elem); // Save value of element. | |
382 | it.Skip(); // Skip the element | |
383 | ||
384 | // Write the result to the database | |
385 | db_->Put(put_option_, key, it.WriteResult()); | |
386 | ||
387 | // Return the value | |
11fdf7f2 | 388 | if (result != nullptr) { |
7c673cae FG |
389 | *result = elem.ToString(); |
390 | } | |
391 | return true; | |
392 | } else { | |
393 | // Must have been an empty list | |
394 | assert(it.Done() && len==0 && curIndex == 0); | |
395 | return false; | |
396 | } | |
397 | } | |
398 | ||
399 | // Remove the (first or last) "num" occurrences of value in (list: key) | |
400 | // : throws RedisListException | |
401 | int RedisLists::Remove(const std::string& key, int32_t num, | |
402 | const std::string& value) { | |
403 | // Negative num ==> RemoveLast; Positive num ==> Remove First | |
404 | if (num < 0) { | |
405 | return RemoveLast(key, -num, value); | |
406 | } else if (num > 0) { | |
407 | return RemoveFirst(key, num, value); | |
408 | } else { | |
409 | return RemoveFirst(key, Length(key), value); | |
410 | } | |
411 | } | |
412 | ||
413 | // Remove the first "num" occurrences of value in (list: key). | |
414 | // : throws RedisListException | |
415 | int RedisLists::RemoveFirst(const std::string& key, int32_t num, | |
416 | const std::string& value) { | |
417 | // Ensure that the number is positive | |
418 | assert(num >= 0); | |
419 | ||
420 | // Extract the original list data | |
421 | std::string data; | |
422 | db_->Get(get_option_, key, &data); | |
423 | ||
424 | // Traverse the list, appending all but the desired occurrences of value | |
425 | int numSkipped = 0; // Keep track of the number of times value is seen | |
426 | Slice elem; | |
427 | RedisListIterator it(data); | |
428 | it.Reserve(it.Size()); | |
429 | while (!it.Done()) { | |
430 | it.GetCurrent(&elem); | |
431 | ||
432 | if (elem == value && numSkipped < num) { | |
433 | // Drop this item if desired | |
434 | it.Skip(); | |
435 | ++numSkipped; | |
436 | } else { | |
437 | // Otherwise keep the item and proceed as normal | |
438 | it.Push(); | |
439 | } | |
440 | } | |
441 | ||
442 | // Put the result back to the database | |
443 | db_->Put(put_option_, key, it.WriteResult()); | |
444 | ||
445 | // Return the number of elements removed | |
446 | return numSkipped; | |
447 | } | |
448 | ||
449 | ||
450 | // Remove the last "num" occurrences of value in (list: key). | |
451 | // TODO: I traverse the list 2x. Make faster. Might require MergeOperator. | |
452 | // : throws RedisListException | |
453 | int RedisLists::RemoveLast(const std::string& key, int32_t num, | |
454 | const std::string& value) { | |
455 | // Ensure that the number is positive | |
456 | assert(num >= 0); | |
457 | ||
458 | // Extract the original list data | |
459 | std::string data; | |
460 | db_->Get(get_option_, key, &data); | |
461 | ||
462 | // Temporary variable to hold the "current element" in the blocks below | |
463 | Slice elem; | |
464 | ||
465 | // Count the total number of occurrences of value | |
466 | int totalOccs = 0; | |
467 | for (RedisListIterator it(data); !it.Done(); it.Skip()) { | |
468 | it.GetCurrent(&elem); | |
469 | if (elem == value) { | |
470 | ++totalOccs; | |
471 | } | |
472 | } | |
473 | ||
474 | // Construct an iterator to the data. Reserve enough space for the result. | |
475 | RedisListIterator it(data); | |
476 | int bytesRemoved = std::min(num,totalOccs)*it.SizeOf(value); | |
477 | it.Reserve(it.Size() - bytesRemoved); | |
478 | ||
479 | // Traverse the list, appending all but the desired occurrences of value. | |
480 | // Note: "Drop the last k occurrences" is equivalent to | |
481 | // "keep only the first n-k occurrences", where n is total occurrences. | |
482 | int numKept = 0; // Keep track of the number of times value is kept | |
483 | while(!it.Done()) { | |
484 | it.GetCurrent(&elem); | |
485 | ||
486 | // If we are within the deletion range and equal to value, drop it. | |
487 | // Otherwise, append/keep/push it. | |
488 | if (elem == value) { | |
489 | if (numKept < totalOccs - num) { | |
490 | it.Push(); | |
491 | ++numKept; | |
492 | } else { | |
493 | it.Skip(); | |
494 | } | |
495 | } else { | |
496 | // Always append the others | |
497 | it.Push(); | |
498 | } | |
499 | } | |
500 | ||
501 | // Put the result back to the database | |
502 | db_->Put(put_option_, key, it.WriteResult()); | |
503 | ||
504 | // Return the number of elements removed | |
505 | return totalOccs - numKept; | |
506 | } | |
507 | ||
508 | /// Private functions | |
509 | ||
510 | // Insert element value into (list: key), right before/after | |
511 | // the first occurrence of pivot | |
512 | // : throws RedisListException | |
513 | int RedisLists::Insert(const std::string& key, const std::string& pivot, | |
514 | const std::string& value, bool insert_after) { | |
515 | // Get the original list data | |
516 | std::string data; | |
517 | db_->Get(get_option_, key, &data); | |
518 | ||
519 | // Construct an iterator to the data and reserve enough space for result. | |
520 | RedisListIterator it(data); | |
521 | it.Reserve(it.Size() + it.SizeOf(value)); | |
522 | ||
523 | // Iterate through the list until we find the element we want | |
524 | Slice elem; | |
525 | bool found = false; | |
526 | while(!it.Done() && !found) { | |
527 | it.GetCurrent(&elem); | |
528 | ||
529 | // When we find the element, insert the element and mark found | |
530 | if (elem == pivot) { // Found it! | |
531 | found = true; | |
532 | if (insert_after == true) { // Skip one more, if inserting after it | |
533 | it.Push(); | |
534 | } | |
535 | it.InsertElement(value); | |
536 | } else { | |
537 | it.Push(); | |
538 | } | |
539 | ||
540 | } | |
541 | ||
542 | // Put the data (string) into the database | |
543 | if (found) { | |
544 | db_->Put(put_option_, key, it.WriteResult()); | |
545 | } | |
546 | ||
547 | // Returns the new (possibly unchanged) length of the list | |
548 | return it.Length(); | |
549 | } | |
550 | ||
551 | } // namespace rocksdb | |
552 | #endif // ROCKSDB_LITE |