1 /******************************************************************************* 2 3 Free list of dynamically allocated objects. 4 Implemented as a linked list; a subclass must get and set the next one of 5 a given object. 6 7 Copyright: 8 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 9 All rights reserved. 10 11 License: 12 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 13 Alternatively, this file may be distributed under the terms of the Tango 14 3-Clause BSD License (see LICENSE_BSD.txt for details). 15 16 *******************************************************************************/ 17 18 module ocean.util.container.map.model.BucketElementFreeList; 19 20 21 import ocean.util.container.map.model.IAllocator; 22 23 import ocean.core.Array: clear; 24 25 /******************************************************************************* 26 27 Free list of currently unused bucket elements. 28 29 *******************************************************************************/ 30 31 class BucketElementFreeList ( BucketElement ) : IBucketElementFreeList 32 { 33 static assert(is(BucketElement == struct), 34 "BucketElement type needs to be a struct, which " ~ 35 BucketElement.stringof ~ " is not"); 36 37 static if(is(typeof(BucketElement.next) Next)) 38 { 39 static assert(is(Next == BucketElement*), 40 BucketElement.stringof ~ ".next needs to be of type " ~ 41 (BucketElement*).stringof ~ ", not " ~ Next.stringof); 42 } 43 else 44 { 45 static assert(false, "need " ~ (BucketElement*).stringof ~ " " ~ 46 BucketElement.stringof ~ ".next"); 47 } 48 49 /*************************************************************************** 50 51 Constructor. 52 53 ***************************************************************************/ 54 55 public this ( ) 56 { 57 super(BucketElement.sizeof); 58 } 59 60 /************************************************************************** 61 62 Obtains the next element of element. 63 64 Params: 65 element = bucket element of which to obtain the next one 66 67 Returns: 68 the next bucket element (which may be null). 69 70 **************************************************************************/ 71 72 protected override void* getNext ( void* element ) 73 { 74 return (cast(BucketElement*)element).next; 75 } 76 77 /************************************************************************** 78 79 Sets the next element of element. 80 81 Params: 82 element = bucket element to which to set the next one 83 next = next bucket element for element (nay be null) 84 85 **************************************************************************/ 86 87 protected override void setNext ( void* element, void* next ) 88 { 89 (cast(BucketElement*)element).next = cast(BucketElement*)next; 90 } 91 92 /************************************************************************** 93 94 Allocates a bucket element. 95 96 Returns: 97 a new bucket element. 98 99 **************************************************************************/ 100 101 protected override void* newElement ( ) 102 { 103 return new BucketElement; 104 } 105 } 106 107 /******************************************************************************* 108 109 Creates an instance of BucketElementFreeList which is suitable for usage 110 with the Map type passed as a template parameter. 111 112 Params: 113 Map = the type to create the allocator according to 114 115 Returns: 116 an instance of type BucketElementFreeList class 117 118 *******************************************************************************/ 119 120 public BucketElementFreeList!(Map.Bucket.Element) instantiateAllocator ( Map ) ( ) 121 { 122 return new BucketElementFreeList!(Map.Bucket.Element); 123 } 124 125 126 /******************************************************************************* 127 128 Type generic BucketElementFreeList base class. 129 130 *******************************************************************************/ 131 132 abstract class IBucketElementFreeList: IAllocator 133 { 134 import ocean.core.Verify; 135 136 /************************************************************************** 137 138 First free element. 139 140 **************************************************************************/ 141 142 private void* first = null; 143 144 /************************************************************************** 145 146 Free list length. 147 148 **************************************************************************/ 149 150 private size_t n_free = 0; 151 152 /************************************************************************** 153 154 True while a ParkingStack instance for this instance exists. 155 156 **************************************************************************/ 157 158 private bool parking_stack_open = false; 159 160 /************************************************************************** 161 162 Consistency check and assertion that at most one ParkingStack instance 163 for this instance exists at a time. 164 165 **************************************************************************/ 166 167 invariant ( ) 168 { 169 if (this.first) 170 { 171 assert (this.n_free); 172 } 173 else 174 { 175 assert (!this.n_free); 176 } 177 178 assert (!this.parking_stack_open, "attempted to use the outer " ~ 179 typeof (this).stringof ~ " instance of an existing " ~ 180 ParkingStack.stringof ~ " instance"); 181 } 182 183 /*************************************************************************** 184 185 Constructor. 186 187 Params: 188 bucket_element_sizeof = the amount of memory used by each allocated 189 element. 190 191 ***************************************************************************/ 192 193 public this( size_t bucket_element_sizeof ) 194 { 195 super(bucket_element_sizeof); 196 } 197 198 /************************************************************************** 199 200 Obtains an object either from the free list, if available, or from 201 new_object if the free list is empty. 202 203 Returns: 204 new object 205 206 Out: 207 The returned object cannot be null. 208 209 **************************************************************************/ 210 211 protected override void* allocate ( ) 212 out (object) 213 { 214 assert (object !is null); 215 } 216 do 217 { 218 if (this.first) 219 { 220 return this.get_(); 221 } 222 else 223 { 224 return this.newElement(); 225 } 226 } 227 228 /************************************************************************** 229 230 Allocates a new object. Called by get() if the list is empty. 231 232 Returns: 233 a new object. 234 235 **************************************************************************/ 236 237 abstract protected void* newElement ( ); 238 239 /************************************************************************** 240 241 Appends old_object to the free list. 242 243 Params: 244 old_object = object to recycle 245 246 In: 247 old_object must not be null. 248 249 **************************************************************************/ 250 251 protected override void deallocate ( void* old_object ) 252 { 253 verify (old_object !is null); 254 255 scope (success) this.n_free++; 256 257 this.recycle_(old_object); 258 } 259 260 /************************************************************************** 261 262 Returns: 263 the number of objects in the free list. 264 265 **************************************************************************/ 266 267 public size_t length ( ) 268 { 269 return this.n_free; 270 } 271 272 /************************************************************************** 273 274 Obtains the next object of object. object is never null but the next 275 object may be. 276 277 Params: 278 object = object of which to obtain the next object (is never null) 279 280 Returns: 281 the next object (which may be null). 282 283 **************************************************************************/ 284 285 abstract protected void* getNext ( void* object ); 286 287 /************************************************************************** 288 289 Sets the next object of object. object is never null but next may be. 290 291 Params: 292 object = object to which to set the next object (is never null) 293 next = next object for object (nay be null) 294 295 **************************************************************************/ 296 297 abstract protected void setNext ( void* object, void* next ); 298 299 /************************************************************************** 300 301 Obtains free_list[n] and sets free_list[n] to null. 302 303 Params: 304 n = free list index 305 306 Returns: 307 free_list[n] 308 309 **************************************************************************/ 310 311 private void* get_ ( ) 312 { 313 verify (this.first !is null); 314 315 void* element = this.first; 316 317 this.first = this.getNext(element); 318 this.n_free--; 319 this.setNext(element, null); 320 321 return element; 322 } 323 324 /************************************************************************** 325 326 Appends object to the free list using n as insertion index. n is 327 expected to refer to the position immediately after the last object in 328 the free list, which may be free_list.length. 329 330 Params: 331 n = free list insertion index 332 333 Returns: 334 free_list[n] 335 336 **************************************************************************/ 337 338 private void* recycle_ ( void* object ) 339 { 340 this.setNext(object, this.first); 341 342 return this.first = object; 343 } 344 345 /*************************************************************************** 346 347 Calls dg with an IParkingStack instance that is set up to keep n 348 elements. 349 350 Params: 351 n = number of elements to park 352 dg = delegate to call with the IParkingStack instance 353 354 ***************************************************************************/ 355 356 public override void parkElements (size_t n, 357 scope void delegate ( IParkingStack park ) dg) 358 { 359 scope parking_stack = this.new ParkingStack(n); 360 361 dg(parking_stack); 362 } 363 364 /************************************************************************** 365 366 Allows using the free list as a stack to park objects without marking 367 them as free. The parked object are appended to the free list after the 368 free objects currently in the list. 369 At most one ParkingStack instance may exist at a time. While a 370 ParkingStack instance exists, no public FreeList method may be used. 371 372 **************************************************************************/ 373 374 class ParkingStack: IParkingStack 375 { 376 /********************************************************************** 377 378 Constructor. 379 380 Params: 381 max_length = maximum number of objects that will be stored 382 383 **********************************************************************/ 384 385 private this ( size_t max_length ) 386 { 387 verify (!this.outer.parking_stack_open); 388 389 this.outer.parking_stack_open = true; 390 super(max_length); 391 } 392 393 /********************************************************************** 394 395 Destructor; removes the remaining stack elements, if any. 396 397 **********************************************************************/ 398 399 ~this ( ) 400 { 401 scope ( exit ) this.outer.parking_stack_open = false; 402 while (this.pop()) { } 403 } 404 405 /********************************************************************** 406 407 Pushes an object on the stack. 408 409 Params: 410 object = object to push 411 n = number of parked objects before object is pushed 412 (guaranteed to be less than max_length) 413 414 **********************************************************************/ 415 416 protected override void push_ ( void* object, size_t n ) 417 { 418 this.outer.recycle_(object); 419 } 420 421 /********************************************************************** 422 423 Pops an object from the stack. This method is never called if the 424 stack is empty. 425 426 Params: 427 n = number of parked objects after object is popped (guaranteed 428 to be less than max_length) 429 430 Returns: 431 object popped from the stack or null if the stack is empty. 432 433 **********************************************************************/ 434 435 protected override void* pop_ ( size_t n ) 436 { 437 return this.outer.get_(); 438 } 439 } 440 }