1 ///
2 /// @file   Bucket.hpp
3 /// @brief  A bucket is a container for sieving primes.
4 ///         The Bucket class is designed as a singly linked list,
5 ///         once there is no more space in the current Bucket
6 ///         a new Bucket is allocated.
7 ///
8 /// Copyright (C) 2020 Kim Walisch, <kim.walisch@gmail.com>
9 ///
10 /// This file is distributed under the BSD License. See the COPYING
11 /// file in the top level directory.
12 ///
13 
14 #ifndef BUCKET_HPP
15 #define BUCKET_HPP
16 
17 #include "config.hpp"
18 #include "pmath.hpp"
19 
20 #include <stdint.h>
21 #include <cstddef>
22 #include <cassert>
23 
24 namespace primesieve {
25 
26 /// Each SievingPrime object contains a sieving prime and the
27 /// position of its next multiple inside the sieve array i.e.
28 /// multipleIndex and a wheelIndex. In order to reduce the memory
29 /// usage the multipleIndex and wheelIndex are packed into a
30 /// single 32-bit variable.
31 ///
32 class SievingPrime
33 {
34 public:
35   enum {
36     MAX_MULTIPLEINDEX = (1 << 23) - 1,
37     MAX_WHEELINDEX    = (1 << (32 - 23)) - 1
38   };
39 
40   SievingPrime() = default;
41 
SievingPrime(uint64_t sievingPrime,uint64_t multipleIndex,uint64_t wheelIndex)42   SievingPrime(uint64_t sievingPrime,
43                uint64_t multipleIndex,
44                uint64_t wheelIndex)
45   {
46     set(sievingPrime, multipleIndex, wheelIndex);
47   }
48 
set(uint64_t multipleIndex,uint64_t wheelIndex)49   void set(uint64_t multipleIndex,
50            uint64_t wheelIndex)
51   {
52     assert(multipleIndex <= MAX_MULTIPLEINDEX);
53     assert(wheelIndex <= MAX_WHEELINDEX);
54     indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23));
55   }
56 
set(uint64_t sievingPrime,uint64_t multipleIndex,uint64_t wheelIndex)57   void set(uint64_t sievingPrime,
58            uint64_t multipleIndex,
59            uint64_t wheelIndex)
60   {
61     assert(multipleIndex <= MAX_MULTIPLEINDEX);
62     assert(wheelIndex <= MAX_WHEELINDEX);
63     indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23));
64     sievingPrime_ = (uint32_t) sievingPrime;
65   }
66 
getSievingPrime() const67   uint64_t getSievingPrime() const
68   {
69     return sievingPrime_;
70   }
71 
getMultipleIndex() const72   uint64_t getMultipleIndex() const
73   {
74     return indexes_ & MAX_MULTIPLEINDEX;
75   }
76 
getWheelIndex() const77   uint64_t getWheelIndex() const
78   {
79     return indexes_ >> 23;
80   }
81 
82 private:
83   /// multipleIndex = 23 least significant bits of indexes_
84   /// wheelIndex = 9 most significant bits of indexes_
85   uint32_t indexes_;
86   uint32_t sievingPrime_;
87 };
88 
89 /// The Bucket data structure is used to store sieving primes.
90 /// @see http://www.ieeta.pt/~tos/software/prime_sieve.html
91 /// The Bucket class is designed as a singly linked list, once
92 /// there is no more space in the current Bucket a new Bucket
93 /// is allocated.
94 ///
95 class Bucket
96 {
97 public:
begin()98   SievingPrime* begin() { return &sievingPrimes_[0]; }
end()99   SievingPrime* end()   { return end_; }
next()100   Bucket* next()        { return next_; }
setNext(Bucket * next)101   void setNext(Bucket* next) { next_ = next; }
setEnd(SievingPrime * end)102   void setEnd(SievingPrime* end) { end_ = end; }
reset()103   void reset() { end_ = begin(); }
104 
105   /// Get the sieving prime's bucket.
106   /// For performance reasons we don't keep an array with all
107   /// buckets. Instead we find the sieving prime's bucket by
108   /// doing pointer arithmetic using the sieving prime's address.
109   /// Since all buckets are aligned by sizeof(Bucket) we
110   /// calculate the next address that is smaller than the sieving
111   /// prime's address and that is aligned by sizeof(Bucket).
112   /// That's the address of the sieving prime's bucket.
113   ///
get(SievingPrime * sievingPrime)114   static Bucket* get(SievingPrime* sievingPrime)
115   {
116     assert(sievingPrime != nullptr);
117     std::size_t address = (std::size_t) sievingPrime;
118     // We need to adjust the address
119     // in case the bucket is full.
120     address -= 1;
121     address -= address % sizeof(Bucket);
122     return (Bucket*) address;
123   }
124 
125   /// Returns true if the bucket is full with sieving primes
126   /// (or if there is no bucket i.e. sievingPrime == nullptr).
127   /// Each bucket's memory address is aligned by sizeof(Bucket)
128   /// (which is a power of 2) in the MemoryPool. This allows
129   /// us to quickly check if the bucket is full using the next
130   /// sieving prime's address % sizeof(Bucket).
131   ///
isFull(SievingPrime * sievingPrime)132   static bool isFull(SievingPrime* sievingPrime)
133   {
134     std::size_t address = (std::size_t) sievingPrime;
135     return address % sizeof(Bucket) == 0;
136   }
137 
138 private:
139   enum {
140     SIEVING_PRIMES_OFFSET = sizeof(SievingPrime*) + sizeof(Bucket*),
141     SIEVING_PRIMES_SIZE = (config::BUCKET_BYTES - SIEVING_PRIMES_OFFSET) / sizeof(SievingPrime)
142   };
143 
144   SievingPrime* end_;
145   Bucket* next_;
146   SievingPrime sievingPrimes_[SIEVING_PRIMES_SIZE];
147 };
148 
149 static_assert(isPow2(sizeof(Bucket)), "sizeof(Bucket) must be a power of 2!");
150 
151 } // namespace
152 
153 #endif
154