36 |
36 |
37 |
37 |
38 // Starting at (including) pos, find the position of the next 1 bit. |
38 // Starting at (including) pos, find the position of the next 1 bit. |
39 // Return -1 if not found. |
39 // Return -1 if not found. |
40 int BlockListArrayMask::find_next_set_bit(int pos) const { |
40 int BlockListArrayMask::find_next_set_bit(int pos) const { |
41 |
|
42 if (get_bit(pos)) { |
|
43 return pos; |
|
44 } |
|
45 mask_type m2 = _mask; |
41 mask_type m2 = _mask; |
46 int pos2 = pos + 1; |
42 int pos2 = pos + 1; |
47 m2 >>= pos2; |
43 m2 >>= pos2; |
48 if (m2 > 0) { |
44 if (m2 == 0) { |
49 while ((m2 & (mask_type)1) == 0) { |
45 return -1; |
50 m2 >>= 1; |
|
51 pos2 ++; |
|
52 } |
|
53 return pos2; |
|
54 } |
46 } |
55 return -1; |
47 while ((m2 & (mask_type)1) == 0) { |
56 |
48 m2 >>= 1; |
|
49 pos2 ++; |
|
50 } |
|
51 return pos2; |
57 } |
52 } |
58 |
53 |
59 /////////////////////////////////////// |
54 /////////////////////////////////////// |
60 |
55 |
61 template <size_t min_word_size, size_t spread, int num_bins> |
56 template <size_t min_word_size, size_t spread, int num_bins> |
71 _map.set_bit(bno); |
66 _map.set_bit(bno); |
72 } |
67 } |
73 |
68 |
74 template <size_t min_word_size, size_t spread, int num_bins> |
69 template <size_t min_word_size, size_t spread, int num_bins> |
75 block_t* BlockListArray<min_word_size, spread, num_bins>::get(size_t word_size) { |
70 block_t* BlockListArray<min_word_size, spread, num_bins>::get(size_t word_size) { |
76 // Adjust size for spread (we need the bin number which guarantees word_size). |
71 int bno = bin_for_size(word_size); |
77 word_size += (spread - 1); |
72 // First look at the bin holding the band word_size is in. But if the spread is > 1, |
78 if (word_size >= maximal_word_size()) { |
73 // the topmost block in the bin may actually be too small to hold word_size (note that |
79 return NULL; |
74 // blocks in the bin list are unsorted). Still worth a look. |
|
75 if (_bins[bno] != NULL && _bins[bno]->size >= word_size) { |
|
76 // found a fit. |
|
77 } else { |
|
78 // Did not find a fit. Look in the larger bins. |
|
79 bno = _map.find_next_set_bit(bno); |
80 } |
80 } |
81 int bno = bin_for_size(word_size); |
81 |
82 bno = _map.find_next_set_bit(bno); |
|
83 if (bno != -1) { |
82 if (bno != -1) { |
84 assert(bno >= 0 && bno < num_bins, "Sanity"); |
83 assert(bno >= 0 && bno < num_bins, "Sanity"); |
85 assert(_bins[bno] != NULL, "Sanity"); |
84 assert(_bins[bno] != NULL, "Sanity"); |
86 block_t* b = _bins[bno]; |
85 block_t* b = _bins[bno]; |
87 _bins[bno] = b->next; |
86 _bins[bno] = b->next; |
108 #endif // ASSERT |
107 #endif // ASSERT |
109 |
108 |
110 |
109 |
111 template <size_t min_word_size, size_t spread, int num_bins> |
110 template <size_t min_word_size, size_t spread, int num_bins> |
112 void BlockListArray<min_word_size, spread, num_bins>::statistics(block_stats_t* stats) const { |
111 void BlockListArray<min_word_size, spread, num_bins>::statistics(block_stats_t* stats) const { |
|
112 stats->num_blocks = 0; |
|
113 stats->word_size = 0; |
113 for (int i = 0; i < num_bins; i ++) { |
114 for (int i = 0; i < num_bins; i ++) { |
114 for(block_t* b = _bins[i]; b != NULL; b = b->next) { |
115 for(block_t* b = _bins[i]; b != NULL; b = b->next) { |
115 stats->num_blocks ++; |
116 stats->num_blocks ++; |
116 stats->word_size += b->size; |
117 stats->word_size += b->size; |
117 } |
118 } |