1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* 3 * Copyright 2016-2020 Couchbase, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 #ifndef CBC_PILLOWFIGHT_SEQGEN_H 19 #define CBC_PILLOWFIGHT_SEQGEN_H 20 21 namespace Pillowfight 22 { 23 24 /** 25 * Stateful sequence generator, divides sequences based on number of threads. 26 * 27 * On input, it takes a total range amount as well as a number of threads 28 * to serve the range, and finally, the index of the current thread. 29 * 30 * There is one generator per thread, as it is stateful 31 */ 32 class SeqGenerator 33 { 34 public: 35 /** Constructor for sequential key generators */ SeqGenerator(uint32_t start,uint32_t end,int num_workers,int cur_worker)36 SeqGenerator(uint32_t start, uint32_t end, int num_workers, int cur_worker) 37 { 38 offset = start; 39 uint32_t total = end - start; 40 total_self = total / num_workers; 41 locked = std::vector< bool >(total_self, false); 42 lnum = 0; 43 offset += total_self * cur_worker; 44 rnum = 0; 45 sequential = true; 46 curr_seqno = 0; 47 } 48 49 /** Initialize as a random range */ SeqGenerator(uint32_t start,uint32_t end)50 SeqGenerator(uint32_t start, uint32_t end) 51 { 52 total_self = end - start; 53 locked = std::vector< bool >(total_self, false); 54 lnum = 0; 55 offset = start; 56 rnum = 0; 57 curr_seqno = 0; 58 sequential = false; 59 60 for (int ii = 0; ii < 8192; ii++) { 61 seqpool.push_back(rand()); 62 } 63 } 64 65 /** 66 * Get the next sequence in range 67 * @return A number appropriate for the current sequence 68 */ next()69 uint32_t next() 70 { 71 if (sequential) { 72 rnum++; 73 rnum %= total_self; 74 rnum += offset; 75 return rnum; 76 77 } else { 78 rnum += seqpool[curr_seqno]; 79 curr_seqno++; 80 if (curr_seqno >= seqpool.size()) { 81 curr_seqno = 0; 82 } 83 uint32_t seq = rnum; 84 seq %= total_self; 85 seq += offset; 86 return seq; 87 } 88 } 89 checkout()90 uint32_t checkout() 91 { 92 uint32_t num; 93 num = next(); 94 if (lnum == locked.size()) { 95 lnum = 0; 96 std::fill(locked.begin(), locked.end(), false); 97 } else { 98 while (locked[num - offset]) { 99 num = next(); 100 } 101 } 102 locked[num - offset] = true; 103 lnum++; 104 return num; 105 } 106 checkin(uint32_t num)107 void checkin(uint32_t num) 108 { 109 if (num - offset < locked.size()) { 110 locked[num - offset] = 0; 111 } 112 } 113 maxItems()114 uint32_t maxItems() const 115 { 116 return total_self; 117 } 118 119 private: 120 bool sequential; 121 std::vector< uint32_t > seqpool; 122 std::vector< bool > locked; // lock markers 123 uint32_t lnum; // number of locked keys 124 uint32_t rnum; // internal iterator 125 uint32_t offset; // beginning numerical offset 126 uint32_t total_self; // maximum value of iterator 127 uint32_t curr_seqno; 128 }; 129 } // namespace Pillowfight 130 #endif 131