26 // Each bucket is a bitmap with a bit corresponding to a single slot offset.
30     FREE_EMPTY_BUCKETS,     // An empty bucket will be deallocated immediately.
31     PREFREE_EMPTY_BUCKETS,  // An empty bucket will be unlinked from the slot
34     KEEP_EMPTY_BUCKETS      // An empty bucket will be kept.
54   // allocation of the bucket is not thread-safe.
62     Bucket bucket = LoadBucket<access_mode>(&buckets_[bucket_index]);  in Insert()  local
63     if (bucket == nullptr) {  in Insert()
64       bucket = AllocateBucket();  in Insert()
65       if (!SwapInNewBucket<access_mode>(&buckets_[bucket_index], bucket)) {  in Insert()
66         DeleteArray<uint32_t>(bucket);  in Insert()
67         bucket = LoadBucket<access_mode>(&buckets_[bucket_index]);  in Insert()
70     // Check that monotonicity is preserved, i.e., once a bucket is set we do  in Insert()
72     DCHECK_NOT_NULL(bucket);  in Insert()
73     DCHECK_EQ(bucket, LoadBucket<access_mode>(&buckets_[bucket_index]));  in Insert()
75     if ((LoadCell<access_mode>(&bucket[cell_index]) & mask) == 0) {  in Insert()
76       SetCellBits<access_mode>(&bucket[cell_index], mask);  in Insert()
85     Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in Contains()  local
86     if (bucket == nullptr) return false;  in Contains()
87     return (LoadCell(&bucket[cell_index]) & (1u << bit_index)) != 0;  in Contains()
94     Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in Remove()  local
95     if (bucket != nullptr) {  in Remove()
96       uint32_t cell = LoadCell(&bucket[cell_index]);  in Remove()
99         ClearCellBits(&bucket[cell_index], bit_mask);  in Remove()
115     Bucket bucket;  in RemoveRange()  local
117       bucket = LoadBucket(&buckets_[start_bucket]);  in RemoveRange()
118       if (bucket != nullptr) {  in RemoveRange()
119         ClearCellBits(&bucket[start_cell], ~(start_mask | end_mask));  in RemoveRange()
125     bucket = LoadBucket(&buckets_[current_bucket]);  in RemoveRange()
126     if (bucket != nullptr) {  in RemoveRange()
127       ClearCellBits(&bucket[current_cell], ~start_mask);  in RemoveRange()
131       if (bucket != nullptr) {  in RemoveRange()
132         ClearBucket(bucket, current_cell, kCellsPerBucket);  in RemoveRange()
134       // The rest of the current bucket is cleared.  in RemoveRange()
135       // Move on to the next bucket.  in RemoveRange()
148         bucket = LoadBucket(&buckets_[current_bucket]);  in RemoveRange()
149         if (bucket != nullptr) {  in RemoveRange()
150           ClearBucket(bucket, 0, kCellsPerBucket);  in RemoveRange()
156     bucket = LoadBucket(&buckets_[current_bucket]);  in RemoveRange()
158     if (current_bucket == kBuckets || bucket == nullptr) {  in RemoveRange()
162       StoreCell(&bucket[current_cell], 0);  in RemoveRange()
167     ClearCellBits(&bucket[end_cell], ~end_mask);  in RemoveRange()
174     Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in Lookup()  local
175     if (bucket == nullptr) return false;  in Lookup()
176     return (LoadCell(&bucket[cell_index]) & (1u << bit_index)) != 0;  in Lookup()
193       Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in Iterate()  local
194       if (bucket != nullptr) {  in Iterate()
198           uint32_t cell = LoadCell(&bucket[i]);  in Iterate()
215               ClearCellBits(&bucket[i], mask);  in Iterate()
235       Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in PreFreeEmptyBuckets()  local
236       if (bucket != nullptr) {  in PreFreeEmptyBuckets()
237         if (IsEmptyBucket(bucket)) {  in PreFreeEmptyBuckets()
246       Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in FreeEmptyBuckets()  local
247       if (bucket != nullptr) {  in FreeEmptyBuckets()
248         if (IsEmptyBucket(bucket)) {  in FreeEmptyBuckets()
258       Bucket top = to_be_freed_buckets_.top();  in FreeToBeFreedBuckets()
266   typedef uint32_t* Bucket;  typedef
276   Bucket AllocateBucket() {  in AllocateBucket()
277     Bucket result = NewArray<uint32_t>(kCellsPerBucket);  in AllocateBucket()
284   void ClearBucket(Bucket bucket, int start_cell, int end_cell) {  in ClearBucket()  argument
289       StoreCell(&bucket[current_cell], 0);  in ClearBucket()
295     Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in PreFreeEmptyBucket()  local
296     if (bucket != nullptr) {  in PreFreeEmptyBucket()
298       to_be_freed_buckets_.push(bucket);  in PreFreeEmptyBucket()
304     Bucket bucket = LoadBucket(&buckets_[bucket_index]);  in ReleaseBucket()  local
306     DeleteArray<uint32_t>(bucket);  in ReleaseBucket()
310   Bucket LoadBucket(Bucket* bucket) {  in LoadBucket()  argument
312       return base::AsAtomicPointer::Acquire_Load(bucket);  in LoadBucket()
313     return *bucket;  in LoadBucket()
317   void StoreBucket(Bucket* bucket, Bucket value) {  in StoreBucket()  argument
319       base::AsAtomicPointer::Release_Store(bucket, value);  in StoreBucket()
321       *bucket = value;  in StoreBucket()
325   bool IsEmptyBucket(Bucket bucket) {  in IsEmptyBucket()  argument
327       if (LoadCell(&bucket[i])) {  in IsEmptyBucket()
335   bool SwapInNewBucket(Bucket* bucket, Bucket value) {  in SwapInNewBucket()  argument
337       return base::AsAtomicPointer::Release_CompareAndSwap(bucket, nullptr,  in SwapInNewBucket()
340       DCHECK_NULL(*bucket);  in SwapInNewBucket()
341       *bucket = value;  in SwapInNewBucket()
370   // Converts the slot offset into bucket/cell/bit index.
381   Bucket buckets_[kBuckets];