1 /******************************************************************************* 2 3 Bucket set helper class for bookkeeping of the number of elements in each 4 bucket. 5 6 Copyright: 7 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 8 All rights reserved. 9 10 License: 11 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 12 Alternatively, this file may be distributed under the terms of the Tango 13 3-Clause BSD License (see LICENSE_BSD.txt for details). 14 15 *******************************************************************************/ 16 17 module ocean.util.container.map.model.BucketInfo; 18 19 20 import ocean.meta.types.Qualifiers; 21 debug (BucketInfo) import ocean.io.Stdout; 22 23 /*******************************************************************************/ 24 25 class BucketInfo 26 { 27 import ocean.core.Verify; 28 29 /************************************************************************** 30 31 Information about a non-empty bucket. 32 33 **************************************************************************/ 34 35 struct Bucket 36 { 37 /********************************************************************** 38 39 Bucket index, the index of the bucket in the array of buckets. It 40 is meaningful only if length > 0 so for easier bug detection the 41 initial value is an out-of-range index. 42 43 **********************************************************************/ 44 45 size_t index = size_t.max; 46 47 /********************************************************************** 48 49 Bucket length, the number of elements in the bucket. 0 means that 50 the bucket is empty. 51 52 **********************************************************************/ 53 54 size_t length = 0; 55 56 /********************************************************************** 57 58 Sorting criterium: Makes .sort of an array of this struct sort the 59 elements by .length in descending order. 60 61 **********************************************************************/ 62 63 public int opCmp ( const typeof(this) rhs ) const 64 { 65 return (this.length >= rhs.length)? this.length > rhs.length : -1; 66 } 67 68 public equals_t opEquals (Bucket rhs) 69 { 70 return this.opCmp(rhs) == 0; 71 } 72 73 /**********************************************************************/ 74 75 debug (BucketInfo) private void print ( ) 76 { 77 Stderr.format(" {,2}/{,2}", this.index, this.length); 78 } 79 } 80 81 /************************************************************************** 82 83 Number of non-empty buckets. 84 85 **************************************************************************/ 86 87 private size_t n_filled = 0; 88 89 /************************************************************************** 90 91 List of Bucket info instances, with the non-empty buckets first, so that 92 buckets[0 .. n_filled] refers to the non-empty buckets. 93 94 All elements in buckets[n_filled .. $] must always have the initial 95 value Bucket.init so that, given a bucket index b, if 96 97 bucket_list_indices[b] >= n_filled 98 99 then 100 101 buckets[bucket_list_indices[b]].length == 0. 102 103 **************************************************************************/ 104 105 private Bucket[] buckets; 106 107 /************************************************************************** 108 109 Index in the list of Bucket info instances by bucket index, so that for 110 a bucket index b the bucket info for this bucket can be obtained by 111 buckets[bucket_list_indices[b]]. 112 113 All elements of this array are initialised to buckets.length - 1 114 because, as described for the buckets array, given a bucket index b that 115 refers to an empty bucket, bucket_list_indices[b] must be at least 116 n_filled, and as long as there are empty buckets, n_filled is less than 117 buckets.length. 118 119 **************************************************************************/ 120 121 private size_t[] bucket_list_indices; 122 123 /************************************************************************** 124 125 Number of elements that are currently in the map. 126 127 **************************************************************************/ 128 129 private size_t n_elements; 130 131 /************************************************************************** 132 133 Consistency check. 134 135 **************************************************************************/ 136 137 invariant ( ) 138 { 139 assert (this.buckets.length == this.bucket_list_indices.length); 140 assert (this.n_filled <= this.buckets.length); 141 assert (this.n_filled <= this.n_elements); 142 143 if (this.n_elements) 144 { 145 assert (this.n_filled); 146 } 147 else 148 { 149 assert(!this.n_filled); 150 } 151 } 152 153 /************************************************************************** 154 155 Constructor. 156 157 Params: 158 num_buckets = number of buckets 159 160 **************************************************************************/ 161 162 public this ( size_t num_buckets ) 163 { 164 this.buckets = new Bucket[num_buckets]; 165 this.bucket_list_indices = new size_t[num_buckets]; 166 167 /* 168 * Initialise bucket_list_indices, see bucket_list_indices documentation 169 * for details. 170 */ 171 this.bucket_list_indices[] = this.buckets.length - 1; 172 } 173 174 /************************************************************************** 175 176 Returns: 177 the number of non-empty buckets. 178 179 **************************************************************************/ 180 181 public size_t num_buckets ( ) 182 { 183 return this.buckets.length; 184 } 185 186 /************************************************************************** 187 188 Returns: 189 the number of elements currently in the map. 190 191 **************************************************************************/ 192 193 public size_t length ( ) 194 { 195 return this.n_elements; 196 } 197 198 /************************************************************************** 199 200 Returns: 201 the number of non-empty buckets. 202 203 **************************************************************************/ 204 205 public size_t num_filled_buckets ( ) 206 { 207 return this.n_filled; 208 } 209 210 /*************************************************************************** 211 212 Returns: 213 the average load of the bucket set 214 215 ***************************************************************************/ 216 217 public float load ( ) 218 { 219 return (cast(float)this.n_elements) / this.buckets.length; 220 } 221 222 /*************************************************************************** 223 224 Returns: 225 the maximum load of the bucket set (i.e. the number of elements in 226 the most-filled bucket) 227 228 ***************************************************************************/ 229 230 public size_t max_load ( ) 231 { 232 size_t max_load; 233 234 foreach ( bucket; this.buckets ) 235 { 236 if ( bucket.length > max_load ) 237 { 238 max_load = bucket.length; 239 } 240 } 241 242 return max_load; 243 } 244 245 /*************************************************************************** 246 247 Increases the length of the bucket info for the bucket specified by 248 bucket_index by 1. If the bucket is currently empty, a bucket info is 249 created and the number of non-empty buckets increased by 1. 250 251 Params: 252 bucket_index = index of the bucket into which one element has 253 been put 254 255 ***************************************************************************/ 256 257 package void put ( size_t bucket_index ) 258 { 259 if (this.buckets[this.bucket_list_indices[bucket_index]].length) 260 { 261 this.update(bucket_index); 262 } 263 else 264 { 265 this.create(bucket_index); 266 } 267 } 268 269 /*************************************************************************** 270 271 Creates a bucket info for the currently empty bucket specified by 272 bucket_index, sets the length to 1; increases the number of non-empty 273 buckets by 1. 274 275 Params: 276 bucket_index = index of the bucket into which the first element has 277 been put 278 279 In: 280 The bucket is expected to be currently empty. 281 282 ***************************************************************************/ 283 284 package void create ( size_t bucket_index ) 285 out 286 { 287 assert (this); 288 assert (this.n_filled, "all buckets are empty after create"); 289 290 debug (BucketInfo) this.print(" ", bucket_index); 291 } 292 do 293 { 294 assert (this); // call invariant 295 296 verify (this.n_filled < this.buckets.length, 297 "create: one element or more in each bucket"); 298 299 debug (BucketInfo) this.print("cre ", bucket_index); 300 301 with (this.buckets[this.n_filled]) 302 { 303 verify(index >= this.buckets.length); 304 index = bucket_index; 305 306 verify(!length); 307 length = 1; 308 } 309 310 verify(this.bucket_list_indices[bucket_index] >= this.n_filled); 311 this.bucket_list_indices[bucket_index] = this.n_filled++; 312 313 this.n_elements++; 314 } 315 316 /*************************************************************************** 317 318 Increases the length of the bucket info for the non-empty bucket 319 specified by bucket_index by 1. 320 321 Params: 322 bucket_index = index of the bucket into which another element has 323 been put 324 325 In: 326 The bucket is expected to be non-empty. 327 328 ***************************************************************************/ 329 330 package void update ( size_t bucket_index ) 331 out 332 { 333 assert (this); 334 assert (this.n_filled, "all buckets are empty after update"); 335 336 debug (BucketInfo) this.print(" ", bucket_index); 337 } 338 do 339 { 340 assert (this); // call invariant 341 342 verify (this.n_elements > 0, "update: no element in map"); 343 344 verify (this.buckets[this.bucket_list_indices[bucket_index]].length > 0, 345 "attempted to update an empty bucket info: use create()/put() " 346 ~ "instead"); 347 348 debug (BucketInfo) this.print("upd ", bucket_index); 349 350 this.buckets[this.bucket_list_indices[bucket_index]].length++; 351 352 this.n_elements++; 353 } 354 355 /*************************************************************************** 356 357 Decreases the length of the bucket info for the non-empty bucket 358 specified by bucket_index by 1. Decreases the number of non-empty 359 buckets by 1 if the bucket becomes empty. 360 361 Params: 362 bucket_index = index of the bucket into which another element has 363 been put 364 365 In: 366 The bucket is expected to be non-empty. 367 368 ***************************************************************************/ 369 370 package void remove ( size_t bucket_index ) 371 out 372 { 373 assert (this); 374 375 debug (BucketInfo) this.print(" ", bucket_index); 376 } 377 do 378 { 379 assert (this); // call invariant 380 381 verify (this.n_elements > 0, "remove: no element in map"); 382 383 verify (this.buckets[this.bucket_list_indices[bucket_index]].length > 0, 384 "remove: attempted to remove an element from an empty bucket"); 385 386 debug (BucketInfo) this.print("rem ", bucket_index); 387 388 size_t* bucket_info_index = &this.bucket_list_indices[bucket_index]; 389 390 Bucket* info_to_remove = &this.buckets[*bucket_info_index]; 391 392 /* 393 * Decrease the number of elements in the bucket. If it becomes empty, 394 * move the bucket to the back of the bucket info list. 395 * 396 * The 'in' contract makes sure that info_to_remove.length != 0. 397 */ 398 399 if (!--info_to_remove.length) 400 { 401 /* 402 * Get the last bucket info and decrease the number of non-empty 403 * buckets. The 'in' contract together with the class invariant make 404 * sure that this.n_filled != 0. 405 */ 406 407 Bucket* last_info = &this.buckets[--this.n_filled]; 408 409 if (info_to_remove !is last_info) 410 { 411 /* 412 * If this is not the last bucket, overwrite the info to remove 413 * with the last info. To make assertions fail easier in the 414 * case of a bug, clear the last info and set the index for the 415 * empty bucket to buckets.length. 416 */ 417 418 verify (last_info.length > 0, "last bucket info is empty"); 419 420 *info_to_remove = *last_info; 421 422 this.bucket_list_indices[info_to_remove.index] = *bucket_info_index; 423 } 424 425 *last_info = (*last_info).init; 426 427 *bucket_info_index = this.buckets.length; 428 } 429 430 this.n_elements--; 431 } 432 433 /*************************************************************************** 434 435 Obtains the list of bucket infos for the non-empty buckets. Each element 436 contains the bucket index and the number of elements in the bucket. 437 438 DO NOT MODIFY list elements in-place! 439 440 Returns: 441 the list of bucket infos for the non-empty buckets. Each element 442 contains the bucket index and the number of bucket elements. 443 444 ***************************************************************************/ 445 446 package Bucket[] filled_buckets ( ) 447 { 448 return this.buckets[0 .. this.n_filled]; 449 } 450 451 /*************************************************************************** 452 453 Obtains the number of elements in the bucket specified by bucket_index. 454 455 Params: 456 bucket_index = bucket index 457 458 Returns: 459 the number of elements in the bucket specified by bucket_index. 460 461 In: 462 bucket_index must be less than the number of buckets. 463 464 ***************************************************************************/ 465 466 public size_t opIndex ( size_t bucket_index ) 467 { 468 verify (bucket_index < this.bucket_list_indices.length); 469 470 size_t index = this.bucket_list_indices[bucket_index]; 471 472 return (index < this.n_filled)? this.buckets[index].length : 0; 473 } 474 475 /************************************************************************** 476 477 Clears all bucket infos and sets the number of non-empty buckets to 0. 478 479 **************************************************************************/ 480 481 package void clear ( ) 482 out 483 { 484 assert (this); 485 486 assert (!this.n_elements, "clear: remaining elements"); 487 } 488 do 489 { 490 /* 491 * Reset all buckets that have been in use. 492 */ 493 this.filled_buckets[] = Bucket.init; 494 /* 495 * Reinitialise bucket_list_indices, see bucket_list_indices 496 * documentation for details. 497 */ 498 this.bucket_list_indices[] = this.buckets.length - 1; 499 500 this.n_filled = this.n_elements = 0; 501 } 502 503 /************************************************************************** 504 505 Clears all bucket infos, sets the number of non-empty buckets to 0 and 506 sets the total number of buckets to n. 507 508 Params: 509 n = new total number of buckets 510 511 **************************************************************************/ 512 513 package void clearResize ( size_t n ) 514 { 515 assumeSafeAppend(this.buckets); 516 this.buckets.length = n; 517 assumeSafeAppend(this.bucket_list_indices); 518 this.bucket_list_indices.length = n; 519 520 /* 521 * this.n_filled must be adjusted for clear() to work because clear() 522 * resets all elements in this.filled_buckets, which is 523 * this.buckets[0 .. this.n_filled]. 524 */ 525 if (this.n_filled > n) 526 { 527 this.n_filled = n; 528 } 529 530 this.clear(); 531 } 532 533 /************************************************************************** 534 535 Prints the bucket infos. 536 537 **************************************************************************/ 538 539 debug (BucketInfo) private void print ( char[] prefix, size_t bucket_index ) 540 { 541 Stderr(prefix); 542 Stderr.format("{,2} >>>>> ", bucket_index); 543 544 foreach (bucket; this.buckets[0 .. this.n_filled]) 545 { 546 bucket.print(); 547 } 548 549 Stderr('|'); 550 551 foreach (bucket; this.buckets[this.n_filled .. $]) 552 { 553 bucket.print(); 554 } 555 556 Stderr('\n').flush(); 557 } 558 } 559 560 /******************************************************************************* 561 562 Verify bug #823 (empty buckets were reported to be not empty) is fixed 563 564 *******************************************************************************/ 565 566 version (unittest): 567 568 import ocean.core.Test; 569 570 unittest 571 { 572 auto info = new BucketInfo(3); 573 574 // Checks if the number of elements reported by info for each bucket is 575 // the expected value. 576 577 void checkNumElements ( int[] expected ... ) 578 in 579 { 580 test(expected.length == info.num_buckets); 581 } 582 do 583 { 584 foreach (i, n; expected) 585 { 586 // BucketInfo.opIndex(x) returns the number of elements in bucket x. 587 test!("==")(info[i], n); 588 } 589 } 590 591 checkNumElements(0, 0, 0); 592 593 // BucketInfo.put(x) increases the number of elements in bucket x by 1. 594 595 info.put(2); 596 checkNumElements(0, 0, 1); 597 598 info.put(0); 599 checkNumElements(1, 0, 1); 600 601 info.put(1); 602 checkNumElements(1, 1, 1); 603 604 info.clearResize(4); 605 checkNumElements(0, 0, 0, 0); 606 607 info.put(3); 608 checkNumElements(0, 0, 0, 1); 609 610 info.put(1); 611 checkNumElements(0, 1, 0, 1); 612 613 info.put(0); 614 checkNumElements(1, 1, 0, 1); 615 616 info.put(2); 617 checkNumElements(1, 1, 1, 1); 618 }