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.transition; 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 mixin (genOpCmp( 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 body 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 body 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 body 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 body 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 this.buckets.length = n; 516 this.bucket_list_indices.length = n; 517 518 /* 519 * this.n_filled must be adjusted for clear() to work because clear() 520 * resets all elements in this.filled_buckets, which is 521 * this.buckets[0 .. this.n_filled]. 522 */ 523 if (this.n_filled > n) 524 { 525 this.n_filled = n; 526 } 527 528 this.clear(); 529 } 530 531 /************************************************************************** 532 533 Prints the bucket infos. 534 535 **************************************************************************/ 536 537 debug (BucketInfo) private void print ( char[] prefix, size_t bucket_index ) 538 { 539 Stderr(prefix); 540 Stderr.format("{,2} >>>>> ", bucket_index); 541 542 foreach (bucket; this.buckets[0 .. this.n_filled]) 543 { 544 bucket.print(); 545 } 546 547 Stderr('|'); 548 549 foreach (bucket; this.buckets[this.n_filled .. $]) 550 { 551 bucket.print(); 552 } 553 554 Stderr('\n').flush(); 555 } 556 } 557 558 /******************************************************************************* 559 560 Verify bug #823 (empty buckets were reported to be not empty) is fixed 561 562 *******************************************************************************/ 563 564 version (UnitTest): 565 566 import ocean.core.Test; 567 568 unittest 569 { 570 auto info = new BucketInfo(3); 571 572 // Checks if the number of elements reported by info for each bucket is 573 // the expected value. 574 575 void checkNumElements ( int[] expected ... ) 576 in 577 { 578 test(expected.length == info.num_buckets); 579 } 580 body 581 { 582 foreach (i, n; expected) 583 { 584 // BucketInfo.opIndex(x) returns the number of elements in bucket x. 585 test!("==")(info[i], n); 586 } 587 } 588 589 checkNumElements(0, 0, 0); 590 591 // BucketInfo.put(x) increases the number of elements in bucket x by 1. 592 593 info.put(2); 594 checkNumElements(0, 0, 1); 595 596 info.put(0); 597 checkNumElements(1, 0, 1); 598 599 info.put(1); 600 checkNumElements(1, 1, 1); 601 602 info.clearResize(4); 603 checkNumElements(0, 0, 0, 0); 604 605 info.put(3); 606 checkNumElements(0, 0, 0, 1); 607 608 info.put(1); 609 checkNumElements(0, 1, 0, 1); 610 611 info.put(0); 612 checkNumElements(1, 1, 0, 1); 613 614 info.put(2); 615 checkNumElements(1, 1, 1, 1); 616 }