clockwerk-opensim-stable – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 vero 1 /*
2 * Copyright (c) Contributors, http://opensimulator.org/
3 * See CONTRIBUTORS.TXT for a full list of copyright holders.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the OpenSimulator Project nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27  
28 using System;
29 using System.Collections;
30 using System.Collections.Generic;
31 using System.Diagnostics;
32  
33 namespace OpenSim.Framework
34 {
35 /// <summary>
36 /// Cenome memory based cache to store key/value pairs (elements) limited time and/or limited size.
37 /// </summary>
38 /// <typeparam name="TKey">
39 /// The type of keys in the cache.
40 /// </typeparam>
41 /// <typeparam name="TValue">
42 /// The type of values in the dictionary.
43 /// </typeparam>
44 /// <remarks>
45 /// <para>
46 /// Cenome memory cache stores elements to hash table generations. When new element is being added to cache, and new size would exceed
47 /// maximal allowed size or maximal amount of allowed element count, then elements in oldest generation are deleted. Last access time
48 /// is also tracked in generation level - thus it is possible that some elements are staying in cache far beyond their expiration time.
49 /// If elements in older generations are accessed through <see cref="TryGetValue"/> method, they are moved to newest generation.
50 /// </para>
51 /// </remarks>
52 public class CnmMemoryCache<TKey, TValue> : ICnmCache<TKey, TValue>
53 {
54 /// <summary>
55 /// Default maximal count.
56 /// </summary>
57 /// <seealso cref="MaxCount"/>
58 public const int DefaultMaxCount = 4096;
59  
60 /// <summary>
61 /// Default maximal size.
62 /// </summary>
63 /// <remarks>
64 /// <para>
65 /// 128MB = 128 * 1024^2 = 134 217 728 bytes.
66 /// </para>
67 /// </remarks>
68 /// <seealso cref="MaxSize"/>
69 public const long DefaultMaxSize = 134217728;
70  
71 /// <summary>
72 /// How many operations between time checks.
73 /// </summary>
74 private const int DefaultOperationsBetweenTimeChecks = 40;
75  
76 /// <summary>
77 /// Default expiration time.
78 /// </summary>
79 /// <remarks>
80 /// <para>
81 /// 30 minutes.
82 /// </para>
83 /// </remarks>
84 public static readonly TimeSpan DefaultExpirationTime = TimeSpan.FromMinutes(30.0);
85  
86 /// <summary>
87 /// Minimal allowed expiration time.
88 /// </summary>
89 /// <remarks>
90 /// <para>
91 /// 5 minutes.
92 /// </para>
93 /// </remarks>
94 public static readonly TimeSpan MinExpirationTime = TimeSpan.FromSeconds(10.0);
95  
96 /// <summary>
97 /// Comparer used to compare element keys.
98 /// </summary>
99 /// <remarks>
100 /// Comparer is initialized by constructor.
101 /// </remarks>
102 /// <seealso cref="CnmMemoryCache{TKey,TValue}"/>
103 public readonly IEqualityComparer<TKey> Comparer;
104  
105 /// <summary>
106 /// Expiration time.
107 /// </summary>
108 private TimeSpan m_expirationTime = DefaultExpirationTime;
109  
110 /// <summary>
111 /// Generation bucket count.
112 /// </summary>
113 private int m_generationBucketCount;
114  
115 /// <summary>
116 /// Generation entry count.
117 /// </summary>
118 private int m_generationElementCount;
119  
120 /// <summary>
121 /// Generation max size.
122 /// </summary>
123 private long m_generationMaxSize;
124  
125 /// <summary>
126 /// Maximal allowed count of elements.
127 /// </summary>
128 private int m_maxCount;
129  
130 /// <summary>
131 /// Maximal allowed total size of elements.
132 /// </summary>
133 private long m_maxElementSize;
134  
135 /// <summary>
136 /// Maximal size.
137 /// </summary>
138 private long m_maxSize;
139  
140 /// <summary>
141 /// New generation.
142 /// </summary>
143 private IGeneration m_newGeneration;
144  
145 /// <summary>
146 /// Old generation.
147 /// </summary>
148 private IGeneration m_oldGeneration;
149  
150 /// <summary>
151 /// Operations between time check.
152 /// </summary>
153 private int m_operationsBetweenTimeChecks = DefaultOperationsBetweenTimeChecks;
154  
155 /// <summary>
156 /// Synchronization root object, should always be private and exists always
157 /// </summary>
158 private readonly object m_syncRoot = new object();
159  
160 /// <summary>
161 /// Version of cache.
162 /// </summary>
163 /// <remarks>
164 /// <para>
165 /// Updated every time when cache has been changed (element removed, expired, added, replaced).
166 /// </para>
167 /// </remarks>
168 private int m_version;
169  
170 /// <summary>
171 /// Initializes a new instance of the <see cref="CnmMemoryCache{TKey,TValue}"/> class.
172 /// </summary>
173 public CnmMemoryCache()
174 : this(DefaultMaxSize)
175 {
176 }
177  
178 /// <summary>
179 /// Initializes a new instance of the <see cref="CnmMemoryCache{TKey,TValue}"/> class.
180 /// </summary>
181 /// <param name="maximalSize">
182 /// Maximal cache size.
183 /// </param>
184 public CnmMemoryCache(long maximalSize)
185 : this(maximalSize, DefaultMaxCount)
186 {
187 }
188  
189 /// <summary>
190 /// Initializes a new instance of the <see cref="CnmMemoryCache{TKey,TValue}"/> class.
191 /// </summary>
192 /// <param name="maximalSize">
193 /// Maximal cache size.
194 /// </param>
195 /// <param name="maximalCount">
196 /// Maximal element count.
197 /// </param>
198 public CnmMemoryCache(long maximalSize, int maximalCount)
199 : this(maximalSize, maximalCount, DefaultExpirationTime)
200 {
201 }
202  
203 /// <summary>
204 /// Initializes a new instance of the <see cref="CnmMemoryCache{TKey,TValue}"/> class.
205 /// </summary>
206 /// <param name="maximalSize">
207 /// Maximal cache size.
208 /// </param>
209 /// <param name="maximalCount">
210 /// Maximal element count.
211 /// </param>
212 /// <param name="expirationTime">
213 /// Elements expiration time.
214 /// </param>
215 public CnmMemoryCache(long maximalSize, int maximalCount, TimeSpan expirationTime)
216 : this(maximalSize, maximalCount, expirationTime, EqualityComparer<TKey>.Default)
217 {
218 }
219  
220 /// <summary>
221 /// Initializes a new instance of the <see cref="CnmMemoryCache{TKey,TValue}"/> class.
222 /// </summary>
223 /// <param name="maximalSize">
224 /// Maximal cache size.
225 /// </param>
226 /// <param name="maximalCount">
227 /// Maximal element count.
228 /// </param>
229 /// <param name="expirationTime">
230 /// Elements expiration time.
231 /// </param>
232 /// <param name="comparer">
233 /// Comparer used for comparing elements.
234 /// </param>
235 /// <exception cref="ArgumentNullException">
236 /// <see cref="comparer"/>is <see langword="null"/> reference.
237 /// </exception>
238 public CnmMemoryCache(long maximalSize,
239 int maximalCount,
240 TimeSpan expirationTime,
241 IEqualityComparer<TKey> comparer)
242 {
243 if (comparer == null)
244 throw new ArgumentNullException("comparer");
245  
246 if (expirationTime < MinExpirationTime)
247 expirationTime = MinExpirationTime;
248 if (maximalCount < 8)
249 maximalCount = 8;
250 if (maximalSize < 8)
251 maximalSize = 8;
252 if (maximalCount > maximalSize)
253 maximalCount = (int) maximalSize;
254  
255 Comparer = comparer;
256 m_expirationTime = expirationTime;
257 m_maxSize = maximalSize;
258 m_maxCount = maximalCount;
259  
260 Initialize();
261 }
262  
263 /// <summary>
264 /// Add element to new generation.
265 /// </summary>
266 /// <param name="bucketIndex">
267 /// The bucket index.
268 /// </param>
269 /// <param name="key">
270 /// The element's key.
271 /// </param>
272 /// <param name="value">
273 /// The element's value.
274 /// </param>
275 /// <param name="size">
276 /// The element's size.
277 /// </param>
278 protected virtual void AddToNewGeneration(int bucketIndex, TKey key, TValue value, long size)
279 {
280 // Add to newest generation
281 if (!m_newGeneration.Set(bucketIndex, key, value, size))
282 {
283 // Failed to add new generation
284 RecycleGenerations();
285 m_newGeneration.Set(bucketIndex, key, value, size);
286 }
287  
288 m_version++;
289 }
290  
291 /// <summary>
292 /// <para>
293 /// Get keys bucket index.
294 /// </para>
295 /// </summary>
296 /// <param name="key">
297 /// <para>
298 /// Key which bucket index is being retrieved.
299 /// </para>
300 /// </param>
301 /// <returns>
302 /// <para>
303 /// Bucket index.
304 /// </para>
305 /// </returns>
306 /// <remarks>
307 /// <para>
308 /// Method uses <see cref="Comparer"/> to calculate <see cref="key"/> hash code.
309 /// </para>
310 /// <para>
311 /// Bucket index is remainder when element key's hash value is divided by bucket count.
312 /// </para>
313 /// <para>
314 /// For example: key's hash is 72, bucket count is 5, element's bucket index is 72 % 5 = 2.
315 /// </para>
316 /// </remarks>
317 protected virtual int GetBucketIndex(TKey key)
318 {
319 return (Comparer.GetHashCode(key) & 0x7FFFFFFF) % m_generationBucketCount;
320 }
321  
322 /// <summary>
323 /// Purge generation from the cache.
324 /// </summary>
325 /// <param name="generation">
326 /// The generation that is purged.
327 /// </param>
328 protected virtual void PurgeGeneration(IGeneration generation)
329 {
330 generation.Clear();
331 m_version++;
332 }
333  
334 /// <summary>
335 /// check expired.
336 /// </summary>
337 private void CheckExpired()
338 {
339 // Do this only one in every m_operationsBetweenTimeChecks
340 // Fetching time is using several millisecons - it is better not to do all time.
341 m_operationsBetweenTimeChecks--;
342 if (m_operationsBetweenTimeChecks <= 0)
343 PurgeExpired();
344 }
345  
346 /// <summary>
347 /// Initialize cache.
348 /// </summary>
349 private void Initialize()
350 {
351 m_version++;
352  
353 m_generationMaxSize = MaxSize / 2;
354 MaxElementSize = MaxSize / 8;
355 m_generationElementCount = MaxCount / 2;
356  
357 // Buckets need to be prime number to get better spread of hash values
358 m_generationBucketCount = PrimeNumberHelper.GetPrime(m_generationElementCount);
359  
360 m_newGeneration = new HashGeneration(this);
361 m_oldGeneration = new HashGeneration(this);
362 m_oldGeneration.MakeOld();
363 }
364  
365 /// <summary>
366 /// Recycle generations.
367 /// </summary>
368 private void RecycleGenerations()
369 {
370 // Rotate old generation to new generation, new generation to old generation
371 IGeneration temp = m_newGeneration;
372 m_newGeneration = m_oldGeneration;
373 m_newGeneration.Clear();
374 m_oldGeneration = temp;
375 m_oldGeneration.MakeOld();
376 }
377  
378 #region Nested type: Enumerator
379  
380 /// <summary>
381 /// Key and value pair enumerator.
382 /// </summary>
383 private class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
384 {
385 /// <summary>
386 /// Current enumerator.
387 /// </summary>
388 private int m_currentEnumerator = -1;
389  
390 /// <summary>
391 /// Enumerators to different generations.
392 /// </summary>
393 private readonly IEnumerator<KeyValuePair<TKey, TValue>>[] m_generationEnumerators =
394 new IEnumerator<KeyValuePair<TKey, TValue>>[2];
395  
396 /// <summary>
397 /// Initializes a new instance of the <see cref="Enumerator"/> class.
398 /// </summary>
399 /// <param name="cache">
400 /// The cache.
401 /// </param>
402 public Enumerator(CnmMemoryCache<TKey, TValue> cache)
403 {
404 m_generationEnumerators[ 0 ] = cache.m_newGeneration.GetEnumerator();
405 m_generationEnumerators[ 1 ] = cache.m_oldGeneration.GetEnumerator();
406 }
407  
408 #region IEnumerator<KeyValuePair<TKey,TValue>> Members
409  
410 /// <summary>
411 /// Gets the element in the collection at the current position of the enumerator.
412 /// </summary>
413 /// <returns>
414 /// The element in the collection at the current position of the enumerator.
415 /// </returns>
416 /// <exception cref="InvalidOperationException">
417 /// The enumerator has reach end of collection or <see cref="MoveNext"/> is not called.
418 /// </exception>
419 public KeyValuePair<TKey, TValue> Current
420 {
421 get
422 {
423 if (m_currentEnumerator == -1 || m_currentEnumerator >= m_generationEnumerators.Length)
424 throw new InvalidOperationException();
425  
426 return m_generationEnumerators[ m_currentEnumerator ].Current;
427 }
428 }
429  
430 /// <summary>
431 /// Gets the current element in the collection.
432 /// </summary>
433 /// <returns>
434 /// The current element in the collection.
435 /// </returns>
436 /// <exception cref="T:System.InvalidOperationException">
437 /// The enumerator is positioned before the first element of the collection or after the last element.
438 /// </exception><filterpriority>2</filterpriority>
439 object IEnumerator.Current
440 {
441 get { return Current; }
442 }
443  
444 /// <summary>
445 /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
446 /// </summary>
447 /// <filterpriority>2</filterpriority>
448 public void Dispose()
449 {
450 }
451  
452 /// <summary>
453 /// Advances the enumerator to the next element of the collection.
454 /// </summary>
455 /// <returns>
456 /// <see langword="true"/>if the enumerator was successfully advanced to the next element; <see langword="false"/> if the enumerator has passed the end of the collection.
457 /// </returns>
458 /// <exception cref="T:System.InvalidOperationException">
459 /// The collection was modified after the enumerator was created.
460 /// </exception>
461 /// <filterpriority>2</filterpriority>
462 public bool MoveNext()
463 {
464 if (m_currentEnumerator == -1)
465 m_currentEnumerator = 0;
466  
467 while (m_currentEnumerator < m_generationEnumerators.Length)
468 {
469 if (m_generationEnumerators[ m_currentEnumerator ].MoveNext())
470 return true;
471  
472 m_currentEnumerator++;
473 }
474  
475 return false;
476 }
477  
478 /// <summary>
479 /// Sets the enumerator to its initial position, which is before the first element in the collection.
480 /// </summary>
481 /// <exception cref="T:System.InvalidOperationException">
482 /// The collection was modified after the enumerator was created.
483 /// </exception>
484 /// <filterpriority>2</filterpriority>
485 public void Reset()
486 {
487 foreach (IEnumerator<KeyValuePair<TKey, TValue>> enumerator in m_generationEnumerators)
488 {
489 enumerator.Reset();
490 }
491  
492 m_currentEnumerator = -1;
493 }
494  
495 #endregion
496 }
497  
498 #endregion
499  
500 #region Nested type: HashGeneration
501  
502 /// <summary>
503 /// Hash generation class
504 /// </summary>
505 /// <remarks>
506 /// <para>
507 /// Current implementation is based to separated chaining with move-to-front heuristics. Hash generations have fixed
508 /// amount of buckets and it is never rehashed.
509 /// </para>
510 /// <para>
511 /// Read more about hash tables from <a href="http://en.wikipedia.org/wiki/Hash_table">Wiki article</a>.
512 /// </para>
513 /// </remarks>
514 /// <seealso href="http://en.wikipedia.org/wiki/Hash_table"/>
515 private class HashGeneration : IGeneration
516 {
517 /// <summary>
518 /// Value indicating whether generation was accessed since last time check.
519 /// </summary>
520 private bool m_accessedSinceLastTimeCheck;
521  
522 /// <summary>
523 /// Index of first element's in element chain.
524 /// </summary>
525 /// <value>
526 /// -1 if there is no element in bucket; otherwise first element's index in the element chain.
527 /// </value>
528 /// <remarks>
529 /// Bucket index is remainder when element key's hash value is divided by bucket count.
530 /// For example: key's hash is 72, bucket count is 5, element's bucket index is 72 % 5 = 2.
531 /// </remarks>
532 private readonly int[] m_buckets;
533  
534 /// <summary>
535 /// Cache object.
536 /// </summary>
537 private readonly CnmMemoryCache<TKey, TValue> m_cache;
538  
539 /// <summary>
540 /// Generation's element array.
541 /// </summary>
542 /// <seealso cref="Element"/>
543 private readonly Element[] m_elements;
544  
545 /// <summary>
546 /// Generation's expiration time.
547 /// </summary>
548 private DateTime m_expirationTime1;
549  
550 /// <summary>
551 /// Index to first free element.
552 /// </summary>
553 private int m_firstFreeElement;
554  
555 /// <summary>
556 /// Free element count.
557 /// </summary>
558 /// <remarks>
559 /// When generation is cleared or constructed, this is NOT set to element count.
560 /// This is only tracking elements that are removed and are currently free.
561 /// </remarks>
562 private int m_freeCount;
563  
564 /// <summary>
565 /// Is this generation "new generation".
566 /// </summary>
567 private bool m_newGeneration;
568  
569 /// <summary>
570 /// Next unused entry.
571 /// </summary>
572 private int m_nextUnusedElement;
573  
574 /// <summary>
575 /// Size of data stored to generation.
576 /// </summary>
577 private long m_size;
578  
579 /// <summary>
580 /// Initializes a new instance of the <see cref="HashGeneration"/> class.
581 /// </summary>
582 /// <param name="cache">
583 /// The cache.
584 /// </param>
585 public HashGeneration(CnmMemoryCache<TKey, TValue> cache)
586 {
587 m_cache = cache;
588 m_elements = new Element[m_cache.m_generationElementCount];
589 m_buckets = new int[m_cache.m_generationBucketCount];
590 Clear();
591 }
592  
593 /// <summary>
594 /// Find element's index
595 /// </summary>
596 /// <param name="bucketIndex">
597 /// The element's bucket index.
598 /// </param>
599 /// <param name="key">
600 /// The element's key.
601 /// </param>
602 /// <param name="moveToFront">
603 /// Move element to front of elements.
604 /// </param>
605 /// <param name="previousIndex">
606 /// The previous element's index.
607 /// </param>
608 /// <returns>
609 /// Element's index, if found from the generation; -1 otherwise (if element is not found the generation).
610 /// </returns>
611 private int FindElementIndex(int bucketIndex, TKey key, bool moveToFront, out int previousIndex)
612 {
613 previousIndex = -1;
614 int elementIndex = m_buckets[ bucketIndex ];
615 while (elementIndex >= 0)
616 {
617 if (m_cache.Comparer.Equals(key, m_elements[ elementIndex ].Key))
618 {
619 // Found match
620 if (moveToFront && previousIndex >= 0)
621 {
622 // Move entry to front
623 m_elements[ previousIndex ].Next = m_elements[ elementIndex ].Next;
624 m_elements[ elementIndex ].Next = m_buckets[ bucketIndex ];
625 m_buckets[ bucketIndex ] = elementIndex;
626 previousIndex = 0;
627 }
628  
629 return elementIndex;
630 }
631  
632 previousIndex = elementIndex;
633 elementIndex = m_elements[ elementIndex ].Next;
634 }
635  
636 return -1;
637 }
638  
639 /// <summary>
640 /// Remove element front the generation.
641 /// </summary>
642 /// <param name="bucketIndex">
643 /// The bucket index.
644 /// </param>
645 /// <param name="entryIndex">
646 /// The element index.
647 /// </param>
648 /// <param name="previousIndex">
649 /// The element's previous index.
650 /// </param>
651 private void RemoveElement(int bucketIndex, int entryIndex, int previousIndex)
652 {
653 if (previousIndex >= 0)
654 m_elements[ previousIndex ].Next = m_elements[ entryIndex ].Next;
655 else
656 m_buckets[ bucketIndex ] = m_elements[ entryIndex ].Next;
657  
658 Size -= m_elements[ entryIndex ].Size;
659 m_elements[ entryIndex ].Value = default(TValue);
660 m_elements[ entryIndex ].Key = default(TKey);
661  
662 // Add element to free elements list
663 m_elements[ entryIndex ].Next = m_firstFreeElement;
664 m_firstFreeElement = entryIndex;
665 m_freeCount++;
666 }
667  
668 #region Nested type: Element
669  
670 /// <summary>
671 /// Element that stores key, next element in chain, size and value.
672 /// </summary>
673 private struct Element
674 {
675 /// <summary>
676 /// Element's key.
677 /// </summary>
678 public TKey Key;
679  
680 /// <summary>
681 /// Next element in chain.
682 /// </summary>
683 /// <remarks>
684 /// When element have value (something is stored to it), this is index of
685 /// next element with same bucket index. When element is free, this
686 /// is index of next element in free element's list.
687 /// </remarks>
688 public int Next;
689  
690 /// <summary>
691 /// Size of element.
692 /// </summary>
693 /// <value>
694 /// 0 if element is free; otherwise larger than 0.
695 /// </value>
696 public long Size;
697  
698 /// <summary>
699 /// Element's value.
700 /// </summary>
701 /// <remarks>
702 /// It is possible that this value is <see langword="null"/> even when element
703 /// have value - element's value is then <see langword="null"/> reference.
704 /// </remarks>
705 public TValue Value;
706  
707 /// <summary>
708 /// Gets a value indicating whether element is free or have value.
709 /// </summary>
710 /// <value>
711 /// <see langword="true"/> when element is free; otherwise <see langword="false"/>.
712 /// </value>
713 public bool IsFree
714 {
715 get { return Size == 0; }
716 }
717 }
718  
719 #endregion
720  
721 #region Nested type: Enumerator
722  
723 /// <summary>
724 /// Key value pair enumerator for <see cref="HashGeneration"/> object.
725 /// </summary>
726 private class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
727 {
728 /// <summary>
729 /// Current element.
730 /// </summary>
731 private KeyValuePair<TKey, TValue> m_current;
732  
733 /// <summary>
734 /// Current index.
735 /// </summary>
736 private int m_currentIndex;
737  
738 /// <summary>
739 /// Generation that is being enumerated.
740 /// </summary>
741 private readonly HashGeneration m_generation;
742  
743 /// <summary>
744 /// Cache version.
745 /// </summary>
746 /// <remarks>
747 /// When cache is change, version number is changed.
748 /// </remarks>
749 /// <seealso cref="CnmMemoryCache{TKey,TValue}.m_version"/>
750 private readonly int m_version;
751  
752 /// <summary>
753 /// Initializes a new instance of the <see cref="Enumerator"/> class.
754 /// </summary>
755 /// <param name="generation">
756 /// The generation.
757 /// </param>
758 public Enumerator(HashGeneration generation)
759 {
760 m_generation = generation;
761 m_version = m_generation.m_cache.m_version;
762 }
763  
764 #region IEnumerator<KeyValuePair<TKey,TValue>> Members
765  
766 /// <summary>
767 /// Gets the element in the collection at the current position of the enumerator.
768 /// </summary>
769 /// <returns>
770 /// The element in the collection at the current position of the enumerator.
771 /// </returns>
772 /// <exception cref="InvalidOperationException">
773 /// The enumerator has reach end of collection or <see cref="MoveNext"/> is not called.
774 /// </exception>
775 public KeyValuePair<TKey, TValue> Current
776 {
777 get
778 {
779 if (m_currentIndex == 0 || m_currentIndex >= m_generation.Count)
780 throw new InvalidOperationException();
781  
782 return m_current;
783 }
784 }
785  
786 /// <summary>
787 /// Gets the current element in the collection.
788 /// </summary>
789 /// <returns>
790 /// The current element in the collection.
791 /// </returns>
792 /// <exception cref="InvalidOperationException">
793 /// The enumerator is positioned before the first element of the collection or after the last element.
794 /// </exception><filterpriority>2</filterpriority>
795 object IEnumerator.Current
796 {
797 get { return Current; }
798 }
799  
800 /// <summary>
801 /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
802 /// </summary>
803 /// <filterpriority>2</filterpriority>
804 public void Dispose()
805 {
806 }
807  
808 /// <summary>
809 /// Advances the enumerator to the next element of the collection.
810 /// </summary>
811 /// <returns>
812 /// true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the end of the collection.
813 /// </returns>
814 /// <exception cref="InvalidOperationException">
815 /// The collection was modified after the enumerator was created.
816 /// </exception>
817 public bool MoveNext()
818 {
819 if (m_version != m_generation.m_cache.m_version)
820 throw new InvalidOperationException();
821  
822 while (m_currentIndex < m_generation.Count)
823 {
824 if (m_generation.m_elements[ m_currentIndex ].IsFree)
825 {
826 m_currentIndex++;
827 continue;
828 }
829  
830 m_current = new KeyValuePair<TKey, TValue>(m_generation.m_elements[ m_currentIndex ].Key,
831 m_generation.m_elements[ m_currentIndex ].Value);
832 m_currentIndex++;
833 return true;
834 }
835  
836 m_current = new KeyValuePair<TKey, TValue>();
837 return false;
838 }
839  
840 /// <summary>
841 /// Sets the enumerator to its initial position, which is before the first element in the collection.
842 /// </summary>
843 /// <exception cref="InvalidOperationException">
844 /// The collection was modified after the enumerator was created.
845 /// </exception>
846 /// <filterpriority>2</filterpriority>
847 public void Reset()
848 {
849 if (m_version != m_generation.m_cache.m_version)
850 throw new InvalidOperationException();
851  
852 m_currentIndex = 0;
853 }
854  
855 #endregion
856 }
857  
858 #endregion
859  
860 #region IGeneration Members
861  
862 /// <summary>
863 /// Gets or sets a value indicating whether generation was accessed since last time check.
864 /// </summary>
865 public bool AccessedSinceLastTimeCheck
866 {
867 get { return m_accessedSinceLastTimeCheck; }
868  
869 set { m_accessedSinceLastTimeCheck = value; }
870 }
871  
872 /// <summary>
873 /// Gets element count in generation.
874 /// </summary>
875 public int Count
876 {
877 get { return m_nextUnusedElement - m_freeCount; }
878 }
879  
880 /// <summary>
881 /// Gets or sets generation's expiration time.
882 /// </summary>
883 public DateTime ExpirationTime
884 {
885 get { return m_expirationTime1; }
886  
887 set { m_expirationTime1 = value; }
888 }
889  
890 /// <summary>
891 /// Gets or sets size of data stored to generation.
892 /// </summary>
893 public long Size
894 {
895 get { return m_size; }
896  
897 private set { m_size = value; }
898 }
899  
900 /// <summary>
901 /// Clear all elements from the generation and make generation new again.
902 /// </summary>
903 /// <remarks>
904 /// When generation is new, it is allowed to add new elements to it and
905 /// <see cref="IGeneration.TryGetValue"/>doesn't remove elements from it.
906 /// </remarks>
907 /// <seealso cref="IGeneration.MakeOld"/>
908 public void Clear()
909 {
910 for (int i = m_buckets.Length - 1 ; i >= 0 ; i--)
911 {
912 m_buckets[ i ] = -1;
913 }
914  
915 Array.Clear(m_elements, 0, m_elements.Length);
916 Size = 0;
917 m_firstFreeElement = -1;
918 m_freeCount = 0;
919 m_nextUnusedElement = 0;
920 m_newGeneration = true;
921 ExpirationTime = DateTime.MaxValue;
922 }
923  
924 /// <summary>
925 /// Determines whether the <see cref="IGeneration"/> contains an element with the specific key.
926 /// </summary>
927 /// <param name="bucketIndex">
928 /// The bucket index for the <see cref="key"/> to locate in <see cref="IGeneration"/>.
929 /// </param>
930 /// <param name="key">
931 /// The key to locate in the <see cref="IGeneration"/>.
932 /// </param>
933 /// <returns>
934 /// <see langword="true"/>if the <see cref="IGeneration"/> contains an element with the <see cref="key"/>;
935 /// otherwise <see langword="false"/>.
936 /// </returns>
937 public bool Contains(int bucketIndex, TKey key)
938 {
939 int previousIndex;
940 if (FindElementIndex(bucketIndex, key, true, out previousIndex) == -1)
941 return false;
942  
943 AccessedSinceLastTimeCheck = true;
944 return true;
945 }
946  
947 /// <summary>
948 /// Returns an enumerator that iterates through the elements stored <see cref="HashGeneration"/>.
949 /// </summary>
950 /// <returns>
951 /// A <see cref="IEnumerator"/> that can be used to iterate through the <see cref="HashGeneration"/>.
952 /// </returns>
953 /// <filterpriority>1</filterpriority>
954 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
955 {
956 return new Enumerator(this);
957 }
958  
959 /// <summary>
960 /// Make from generation old generation.
961 /// </summary>
962 /// <remarks>
963 /// When generation is old, <see cref="IGeneration.TryGetValue"/> hit removes element from the generation.
964 /// </remarks>
965 /// <seealso cref="IGeneration.Clear"/>
966 public void MakeOld()
967 {
968 m_newGeneration = false;
969 }
970  
971 /// <summary>
972 /// Remove element associated with the key from the generation.
973 /// </summary>
974 /// <param name="bucketIndex">
975 /// The element's bucket index.
976 /// </param>
977 /// <param name="key">
978 /// The element's key.
979 /// </param>
980 /// <returns>
981 /// <see langword="true"/>, if remove was successful; otherwise <see langword="false"/>.
982 /// </returns>
983 public bool Remove(int bucketIndex, TKey key)
984 {
985 int previousIndex;
986 int entryIndex = FindElementIndex(bucketIndex, key, false, out previousIndex);
987 if (entryIndex != -1)
988 {
989 RemoveElement(bucketIndex, entryIndex, previousIndex);
990 AccessedSinceLastTimeCheck = true;
991 return true;
992 }
993  
994 return false;
995 }
996  
997 /// <summary>
998 /// Set or add element to generation.
999 /// </summary>
1000 /// <param name="bucketIndex">
1001 /// The element's bucket index.
1002 /// </param>
1003 /// <param name="key">
1004 /// The element's key.
1005 /// </param>
1006 /// <param name="value">
1007 /// The element's value.
1008 /// </param>
1009 /// <param name="size">
1010 /// The element's size.
1011 /// </param>
1012 /// <returns>
1013 /// <see langword="true"/>, if setting or adding was successful; otherwise <see langword="false"/>.
1014 /// </returns>
1015 /// <remarks>
1016 /// <para>
1017 /// If element was already existing in generation and new element size fits to collection limits,
1018 /// then it's value is replaced with new one and size information is updated. If element didn't
1019 /// exists in generation before, then generation must have empty space for a new element and
1020 /// size must fit generation's limits, before element is added to generation.
1021 /// </para>
1022 /// </remarks>
1023 public bool Set(int bucketIndex, TKey key, TValue value, long size)
1024 {
1025 Debug.Assert(m_newGeneration, "It is possible to insert new elements only to newest generation.");
1026 Debug.Assert(size > 0, "New element size should be more than 0.");
1027  
1028 int previousIndex;
1029 int elementIndex = FindElementIndex(bucketIndex, key, true, out previousIndex);
1030 if (elementIndex == -1)
1031 {
1032 // New key
1033 if (Size + size > m_cache.m_generationMaxSize ||
1034 (m_nextUnusedElement == m_cache.m_generationElementCount && m_freeCount == 0))
1035 {
1036 // Generation is full
1037 return false;
1038 }
1039  
1040 // Increase size of generation
1041 Size += size;
1042  
1043 // Get first free entry and update free entry list
1044 if (m_firstFreeElement != -1)
1045 {
1046 // There was entry that was removed
1047 elementIndex = m_firstFreeElement;
1048 m_firstFreeElement = m_elements[ elementIndex ].Next;
1049 m_freeCount--;
1050 }
1051 else
1052 {
1053 // No entries removed so far - just take a last one
1054 elementIndex = m_nextUnusedElement;
1055 m_nextUnusedElement++;
1056 }
1057  
1058 Debug.Assert(m_elements[ elementIndex ].IsFree, "Allocated element is not free.");
1059  
1060 // Move new entry to front
1061 m_elements[ elementIndex ].Next = m_buckets[ bucketIndex ];
1062 m_buckets[ bucketIndex ] = elementIndex;
1063  
1064 // Set key and update count
1065 m_elements[ elementIndex ].Key = key;
1066 }
1067 else
1068 {
1069 // Existing key
1070 if (Size - m_elements[ elementIndex ].Size + size > m_cache.m_generationMaxSize)
1071 {
1072 // Generation is full
1073 // Remove existing element, because generation is going to be recycled to
1074 // old generation and element is stored to new generation
1075 RemoveElement(bucketIndex, elementIndex, previousIndex);
1076 return false;
1077 }
1078  
1079 // Update generation's size
1080 Size = Size - m_elements[ elementIndex ].Size + size;
1081 }
1082  
1083 // Finally set value and size
1084 m_elements[ elementIndex ].Value = value;
1085 m_elements[ elementIndex ].Size = size;
1086  
1087 // Success - key was inserterted to generation
1088 AccessedSinceLastTimeCheck = true;
1089 return true;
1090 }
1091  
1092 /// <summary>
1093 /// Try to get element associated with key.
1094 /// </summary>
1095 /// <param name="bucketIndex">
1096 /// The element's bucket index.
1097 /// </param>
1098 /// <param name="key">
1099 /// The element's key.
1100 /// </param>
1101 /// <param name="value">
1102 /// The element's value.
1103 /// </param>
1104 /// <param name="size">
1105 /// The element's size.
1106 /// </param>
1107 /// <returns>
1108 /// <see langword="true"/>, if element was successful retrieved; otherwise <see langword="false"/>.
1109 /// </returns>
1110 /// <remarks>
1111 /// <para>
1112 /// If element is not found from generation then <paramref name="value"/> and <paramref name="size"/>
1113 /// are set to default value (default(TValue) and 0).
1114 /// </para>
1115 /// </remarks>
1116 public bool TryGetValue(int bucketIndex, TKey key, out TValue value, out long size)
1117 {
1118 // Find entry index,
1119 int previousIndex;
1120 int elementIndex = FindElementIndex(bucketIndex, key, m_newGeneration, out previousIndex);
1121 if (elementIndex == -1)
1122 {
1123 value = default(TValue);
1124 size = 0;
1125 return false;
1126 }
1127  
1128 value = m_elements[ elementIndex ].Value;
1129 size = m_elements[ elementIndex ].Size;
1130  
1131 if (!m_newGeneration)
1132 {
1133 // Old generation - remove element, because it is moved to new generation
1134 RemoveElement(bucketIndex, elementIndex, previousIndex);
1135 }
1136  
1137 AccessedSinceLastTimeCheck = true;
1138 return true;
1139 }
1140  
1141 /// <summary>
1142 /// Returns an enumerator that iterates through a collection.
1143 /// </summary>
1144 /// <returns>
1145 /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
1146 /// </returns>
1147 /// <filterpriority>2</filterpriority>
1148 IEnumerator IEnumerable.GetEnumerator()
1149 {
1150 return GetEnumerator();
1151 }
1152  
1153 #endregion
1154 }
1155  
1156 #endregion
1157  
1158 #region Nested type: IGeneration
1159  
1160 /// <summary>
1161 /// Cache element generation interface
1162 /// </summary>
1163 /// <remarks>
1164 /// <para>
1165 /// Generation can hold limited count of elements and limited size of data.
1166 /// </para>
1167 /// <para>
1168 /// There are two kind generations: "new generation" and "old generation(s)". All new elements
1169 /// are added to "new generation".
1170 /// </para>
1171 /// </remarks>
1172 protected interface IGeneration : IEnumerable<KeyValuePair<TKey, TValue>>
1173 {
1174 /// <summary>
1175 /// Gets or sets a value indicating whether generation was accessed since last time check.
1176 /// </summary>
1177 bool AccessedSinceLastTimeCheck { get; set; }
1178  
1179 /// <summary>
1180 /// Gets element count in generation.
1181 /// </summary>
1182 int Count { get; }
1183  
1184 /// <summary>
1185 /// Gets or sets generation's expiration time.
1186 /// </summary>
1187 DateTime ExpirationTime { get; set; }
1188  
1189 /// <summary>
1190 /// Gets size of data stored to generation.
1191 /// </summary>
1192 long Size { get; }
1193  
1194 /// <summary>
1195 /// Clear all elements from the generation and make generation new again.
1196 /// </summary>
1197 /// <remarks>
1198 /// When generation is new, it is allowed to add new elements to it and
1199 /// <see cref="TryGetValue"/>doesn't remove elements from it.
1200 /// </remarks>
1201 /// <seealso cref="MakeOld"/>
1202 void Clear();
1203  
1204 /// <summary>
1205 /// Determines whether the <see cref="IGeneration"/> contains an element with the specific key.
1206 /// </summary>
1207 /// <param name="bucketIndex">
1208 /// The bucket index for the <see cref="key"/> to locate in <see cref="IGeneration"/>.
1209 /// </param>
1210 /// <param name="key">
1211 /// The key to locate in the <see cref="IGeneration"/>.
1212 /// </param>
1213 /// <returns>
1214 /// <see langword="true"/>if the <see cref="IGeneration"/> contains an element with the <see cref="key"/>;
1215 /// otherwise <see langword="false"/>.
1216 /// </returns>
1217 bool Contains(int bucketIndex, TKey key);
1218  
1219 /// <summary>
1220 /// Make from generation old generation.
1221 /// </summary>
1222 /// <remarks>
1223 /// When generation is old, <see cref="TryGetValue"/> hit removes element from the generation.
1224 /// </remarks>
1225 /// <seealso cref="Clear"/>
1226 void MakeOld();
1227  
1228 /// <summary>
1229 /// Remove element associated with the key from the generation.
1230 /// </summary>
1231 /// <param name="bucketIndex">
1232 /// The element's bucket index.
1233 /// </param>
1234 /// <param name="key">
1235 /// The element's key.
1236 /// </param>
1237 /// <returns>
1238 /// <see langword="true"/>, if remove was successful; otherwise <see langword="false"/>.
1239 /// </returns>
1240 bool Remove(int bucketIndex, TKey key);
1241  
1242 /// <summary>
1243 /// Set or add element to generation.
1244 /// </summary>
1245 /// <param name="bucketIndex">
1246 /// The element's bucket index.
1247 /// </param>
1248 /// <param name="key">
1249 /// The element's key.
1250 /// </param>
1251 /// <param name="value">
1252 /// The element's value.
1253 /// </param>
1254 /// <param name="size">
1255 /// The element's size.
1256 /// </param>
1257 /// <returns>
1258 /// <see langword="true"/>, if setting or adding was successful; otherwise <see langword="false"/>.
1259 /// </returns>
1260 /// <remarks>
1261 /// <para>
1262 /// If element was already existing in generation and new element size fits to collection limits,
1263 /// then it's value is replaced with new one and size information is updated. If element didn't
1264 /// exists in generation before, then generation must have empty space for a new element and
1265 /// size must fit generation's limits, before element is added to generation.
1266 /// </para>
1267 /// </remarks>
1268 bool Set(int bucketIndex, TKey key, TValue value, long size);
1269  
1270 /// <summary>
1271 /// Try to get element associated with key.
1272 /// </summary>
1273 /// <param name="bucketIndex">
1274 /// The element's bucket index.
1275 /// </param>
1276 /// <param name="key">
1277 /// The element's key.
1278 /// </param>
1279 /// <param name="value">
1280 /// The element's value.
1281 /// </param>
1282 /// <param name="size">
1283 /// The element's size.
1284 /// </param>
1285 /// <returns>
1286 /// <see langword="true"/>, if element was successful retrieved; otherwise <see langword="false"/>.
1287 /// </returns>
1288 /// <remarks>
1289 /// <para>
1290 /// If element is not found from generation then <paramref name="value"/> and <paramref name="size"/>
1291 /// are set to default value (default(TValue) and 0).
1292 /// </para>
1293 /// </remarks>
1294 bool TryGetValue(int bucketIndex, TKey key, out TValue value, out long size);
1295 }
1296  
1297 #endregion
1298  
1299 #region ICnmCache<TKey,TValue> Members
1300  
1301 /// <summary>
1302 /// Gets current count of elements stored to <see cref="ICnmCache{TKey,TValue}"/>.
1303 /// </summary>
1304 /// <remarks>
1305 /// <para>
1306 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting element count,
1307 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1308 /// </para>
1309 /// </remarks>
1310 /// <seealso cref="ICnmCache{TKey,TValue}.MaxCount"/>
1311 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1312 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1313 /// <seealso cref="ICnmCache{TKey,TValue}.IsTimeLimited"/>
1314 public int Count
1315 {
1316 get { return m_newGeneration.Count + m_oldGeneration.Count; }
1317 }
1318  
1319 /// <summary>
1320 /// Gets or sets elements expiration time.
1321 /// </summary>
1322 /// <value>
1323 /// Elements expiration time.
1324 /// </value>
1325 /// <remarks>
1326 /// <para>
1327 /// When element has been stored in <see cref="ICnmCache{TKey,TValue}"/> longer than <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/>
1328 /// and it is not accessed through <see cref="ICnmCache{TKey,TValue}.TryGetValue"/> method or element's value is
1329 /// not replaced by <see cref="ICnmCache{TKey,TValue}.Set"/> method, then it is automatically removed from the
1330 /// <see cref="ICnmCache{TKey,TValue}"/>.
1331 /// </para>
1332 /// <para>
1333 /// It is possible that <see cref="ICnmCache{TKey,TValue}"/> implementation removes element before it's expiration time,
1334 /// because total size or count of elements stored to cache is larger than <see cref="ICnmCache{TKey,TValue}.MaxSize"/> or <see cref="ICnmCache{TKey,TValue}.MaxCount"/>.
1335 /// </para>
1336 /// <para>
1337 /// It is also possible that element stays in cache longer than <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/>.
1338 /// </para>
1339 /// <para>
1340 /// Calling <see cref="ICnmCache{TKey,TValue}.PurgeExpired"/> try to remove all elements that are expired.
1341 /// </para>
1342 /// <para>
1343 /// To disable time limit in cache, set <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/> to <see cref="DateTime.MaxValue"/>.
1344 /// </para>
1345 /// </remarks>
1346 /// <seealso cref="ICnmCache{TKey,TValue}.IsTimeLimited"/>
1347 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1348 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1349 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1350 /// <seealso cref="ICnmCache{TKey,TValue}.Count"/>
1351 /// <seealso cref="ICnmCache{TKey,TValue}.MaxCount"/>
1352 /// <seealso cref="ICnmCache{TKey,TValue}.MaxSize"/>
1353 /// <seealso cref="ICnmCache{TKey,TValue}.Size"/>
1354 public TimeSpan ExpirationTime
1355 {
1356 get { return m_expirationTime; }
1357  
1358 set
1359 {
1360 if (value < MinExpirationTime)
1361 value = MinExpirationTime;
1362  
1363 if (m_expirationTime == value)
1364 return;
1365  
1366 m_newGeneration.ExpirationTime = (m_newGeneration.ExpirationTime - m_expirationTime) + value;
1367 m_oldGeneration.ExpirationTime = (m_oldGeneration.ExpirationTime - m_expirationTime) + value;
1368 m_expirationTime = value;
1369  
1370 PurgeExpired();
1371 }
1372 }
1373  
1374 /// <summary>
1375 /// Gets a value indicating whether <see cref="ICnmCache{TKey,TValue}"/> is limiting count of elements.
1376 /// </summary>
1377 /// <value>
1378 /// <see langword="true"/> if the <see cref="ICnmCache{TKey,TValue}"/> count of elements is limited;
1379 /// otherwise, <see langword="false"/>.
1380 /// </value>
1381 /// <remarks>
1382 /// <para>
1383 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting element count,
1384 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1385 /// </para>
1386 /// </remarks>
1387 /// <seealso cref="ICnmCache{TKey,TValue}.Count"/>
1388 /// <seealso cref="ICnmCache{TKey,TValue}.MaxCount"/>
1389 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1390 /// <seealso cref="ICnmCache{TKey,TValue}.IsTimeLimited"/>
1391 public bool IsCountLimited
1392 {
1393 get { return true; }
1394 }
1395  
1396 /// <summary>
1397 /// Gets a value indicating whether <see cref="ICnmCache{TKey,TValue}"/> is limiting size of elements.
1398 /// </summary>
1399 /// <value>
1400 /// <see langword="true"/> if the <see cref="ICnmCache{TKey,TValue}"/> total size of elements is limited;
1401 /// otherwise, <see langword="false"/>.
1402 /// </value>
1403 /// <remarks>
1404 /// <para>
1405 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting total size of elements,
1406 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1407 /// </para>
1408 /// </remarks>
1409 /// <seealso cref="ICnmCache{TKey,TValue}.MaxElementSize"/>
1410 /// <seealso cref="ICnmCache{TKey,TValue}.Size"/>
1411 /// <seealso cref="ICnmCache{TKey,TValue}.MaxSize"/>
1412 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1413 /// <seealso cref="ICnmCache{TKey,TValue}.IsTimeLimited"/>
1414 public bool IsSizeLimited
1415 {
1416 get { return true; }
1417 }
1418  
1419 /// <summary>
1420 /// Gets a value indicating whether or not access to the <see cref="ICnmCache{TKey,TValue}"/> is synchronized (thread safe).
1421 /// </summary>
1422 /// <value>
1423 /// <see langword="true"/> if access to the <see cref="ICnmCache{TKey,TValue}"/> is synchronized (thread safe);
1424 /// otherwise, <see langword="false"/>.
1425 /// </value>
1426 /// <remarks>
1427 /// <para>
1428 /// To get synchronized (thread safe) access to <see cref="ICnmCache{TKey,TValue}"/> object, use
1429 /// <see cref="CnmSynchronizedCache{TKey,TValue}.Synchronized"/> in <see cref="CnmSynchronizedCache{TKey,TValue}"/> class
1430 /// to retrieve synchronized wrapper for <see cref="ICnmCache{TKey,TValue}"/> object.
1431 /// </para>
1432 /// </remarks>
1433 /// <seealso cref="ICnmCache{TKey,TValue}.SyncRoot"/>
1434 /// <seealso cref="CnmSynchronizedCache{TKey,TValue}"/>
1435 public bool IsSynchronized
1436 {
1437 get { return false; }
1438 }
1439  
1440 /// <summary>
1441 /// Gets a value indicating whether elements stored to <see cref="ICnmCache{TKey,TValue}"/> have limited inactivity time.
1442 /// </summary>
1443 /// <value>
1444 /// <see langword="true"/> if the <see cref="ICnmCache{TKey,TValue}"/> has a fixed total size of elements;
1445 /// otherwise, <see langword="false"/>.
1446 /// </value>
1447 /// <remarks>
1448 /// If <see cref="ICnmCache{TKey,TValue}"/> have limited inactivity time and element is not accessed through <see cref="ICnmCache{TKey,TValue}.Set"/>
1449 /// or <see cref="ICnmCache{TKey,TValue}.TryGetValue"/> methods in <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/> , then element is automatically removed from
1450 /// the cache. Depending on implementation of the <see cref="ICnmCache{TKey,TValue}"/>, some of the elements may
1451 /// stay longer in cache.
1452 /// </remarks>
1453 /// <seealso cref="ICnmCache{TKey,TValue}.ExpirationTime"/>
1454 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1455 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1456 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1457 public bool IsTimeLimited
1458 {
1459 get { return ExpirationTime != TimeSpan.MaxValue; }
1460 }
1461  
1462 /// <summary>
1463 /// Gets or sets maximal allowed count of elements that can be stored to <see cref="ICnmCache{TKey,TValue}"/>.
1464 /// </summary>
1465 /// <value>
1466 /// <see cref="int.MaxValue"/>, if <see cref="ICnmCache{TKey,TValue}"/> is not limited by count of elements;
1467 /// otherwise maximal allowed count of elements.
1468 /// </value>
1469 /// <remarks>
1470 /// <para>
1471 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting element count,
1472 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1473 /// </para>
1474 /// </remarks>
1475 public int MaxCount
1476 {
1477 get { return m_maxCount; }
1478  
1479 set
1480 {
1481 if (value < 8)
1482 value = 8;
1483 if (m_maxCount == value)
1484 return;
1485  
1486 m_maxCount = value;
1487 Initialize();
1488 }
1489 }
1490  
1491 /// <summary>
1492 /// <para>Gets maximal allowed element size.</para>
1493 /// </summary>
1494 /// <value>
1495 /// Maximal allowed element size.
1496 /// </value>
1497 /// <remarks>
1498 /// <para>
1499 /// If element's size is larger than <see cref="ICnmCache{TKey,TValue}.MaxElementSize"/>, then element is
1500 /// not added to the <see cref="ICnmCache{TKey,TValue}"/>.
1501 /// </para>
1502 /// </remarks>
1503 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1504 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1505 /// <seealso cref="ICnmCache{TKey,TValue}.Size"/>
1506 /// <seealso cref="ICnmCache{TKey,TValue}.MaxSize"/>
1507 public long MaxElementSize
1508 {
1509 get { return m_maxElementSize; }
1510  
1511 private set { m_maxElementSize = value; }
1512 }
1513  
1514 /// <summary>
1515 /// Gets or sets maximal allowed total size for elements stored to <see cref="ICnmCache{TKey,TValue}"/>.
1516 /// </summary>
1517 /// <value>
1518 /// Maximal allowed total size for elements stored to <see cref="ICnmCache{TKey,TValue}"/>.
1519 /// </value>
1520 /// <remarks>
1521 /// <para>
1522 /// Normally size is total bytes used by elements in the cache. But it can be any other suitable unit of measure.
1523 /// </para>
1524 /// <para>
1525 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting total size of elements,
1526 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1527 /// </para>
1528 /// </remarks>
1529 /// <seealso cref="ICnmCache{TKey,TValue}.MaxElementSize"/>
1530 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1531 /// <seealso cref="ICnmCache{TKey,TValue}.Size"/>
1532 public long MaxSize
1533 {
1534 get { return m_maxSize; }
1535  
1536 set
1537 {
1538 if (value < 8)
1539 value = 8;
1540 if (m_maxSize == value)
1541 return;
1542  
1543 m_maxSize = value;
1544 Initialize();
1545 }
1546 }
1547  
1548 /// <summary>
1549 /// Gets total size of elements stored to <see cref="ICnmCache{TKey,TValue}"/>.
1550 /// </summary>
1551 /// <value>
1552 /// Total size of elements stored to <see cref="ICnmCache{TKey,TValue}"/>.
1553 /// </value>
1554 /// <remarks>
1555 /// <para>
1556 /// Normally bytes, but can be any suitable unit of measure.
1557 /// </para>
1558 /// <para>
1559 /// Element's size is given when element is added or replaced by <see cref="ICnmCache{TKey,TValue}.Set"/> method.
1560 /// </para>
1561 /// <para>
1562 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting total size of elements,
1563 /// <see cref="ICnmCache{TKey,TValue}"/> will remove less recently used elements until it can fit an new element.
1564 /// </para>
1565 /// </remarks>
1566 /// <seealso cref="ICnmCache{TKey,TValue}.MaxElementSize"/>
1567 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1568 /// <seealso cref="ICnmCache{TKey,TValue}.MaxSize"/>
1569 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1570 /// <seealso cref="ICnmCache{TKey,TValue}.ExpirationTime"/>
1571 public long Size
1572 {
1573 get { return m_newGeneration.Size + m_oldGeneration.Size; }
1574 }
1575  
1576 /// <summary>
1577 /// Gets an object that can be used to synchronize access to the <see cref="ICnmCache{TKey,TValue}"/>.
1578 /// </summary>
1579 /// <value>
1580 /// An object that can be used to synchronize access to the <see cref="ICnmCache{TKey,TValue}"/>.
1581 /// </value>
1582 /// <remarks>
1583 /// <para>
1584 /// To get synchronized (thread safe) access to <see cref="ICnmCache{TKey,TValue}"/>, use <see cref="CnmSynchronizedCache{TKey,TValue}"/>
1585 /// method <see cref="CnmSynchronizedCache{TKey,TValue}.Synchronized"/> to retrieve synchronized wrapper interface to
1586 /// <see cref="ICnmCache{TKey,TValue}"/>.
1587 /// </para>
1588 /// </remarks>
1589 /// <seealso cref="ICnmCache{TKey,TValue}.IsSynchronized"/>
1590 /// <seealso cref="CnmSynchronizedCache{TKey,TValue}"/>
1591 public object SyncRoot
1592 {
1593 get { return m_syncRoot; }
1594 }
1595  
1596 /// <summary>
1597 /// Removes all elements from the <see cref="ICnmCache{TKey,TValue}"/>.
1598 /// </summary>
1599 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1600 /// <seealso cref="ICnmCache{TKey,TValue}.Remove"/>
1601 /// <seealso cref="ICnmCache{TKey,TValue}.RemoveRange"/>
1602 /// <seealso cref="ICnmCache{TKey,TValue}.TryGetValue"/>
1603 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1604 public void Clear()
1605 {
1606 m_newGeneration.Clear();
1607 m_oldGeneration.Clear();
1608 m_oldGeneration.MakeOld();
1609 m_version++;
1610 }
1611  
1612 /// <summary>
1613 /// Returns an enumerator that iterates through the elements stored to <see cref="CnmMemoryCache{TKey,TValue}"/>.
1614 /// </summary>
1615 /// <returns>
1616 /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.
1617 /// </returns>
1618 /// <filterpriority>1</filterpriority>
1619 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
1620 {
1621 return new Enumerator(this);
1622 }
1623  
1624 /// <summary>
1625 /// Purge expired elements from the <see cref="ICnmCache{TKey,TValue}"/>.
1626 /// </summary>
1627 /// <remarks>
1628 /// <para>
1629 /// Element becomes expired when last access time to it has been longer time than <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/>.
1630 /// </para>
1631 /// <para>
1632 /// Depending on <see cref="ICnmCache{TKey,TValue}"/> implementation, some of expired elements
1633 /// may stay longer than <see cref="ICnmCache{TKey,TValue}.ExpirationTime"/> in the cache.
1634 /// </para>
1635 /// </remarks>
1636 /// <seealso cref="ICnmCache{TKey,TValue}.IsTimeLimited"/>
1637 /// <seealso cref="ICnmCache{TKey,TValue}.ExpirationTime"/>
1638 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1639 /// <seealso cref="ICnmCache{TKey,TValue}.Remove"/>
1640 /// <seealso cref="ICnmCache{TKey,TValue}.RemoveRange"/>
1641 /// <seealso cref="ICnmCache{TKey,TValue}.TryGetValue"/>
1642 /// <seealso cref="ICnmCache{TKey,TValue}.Clear"/>
1643 public void PurgeExpired()
1644 {
1645 m_operationsBetweenTimeChecks = DefaultOperationsBetweenTimeChecks;
1646  
1647 if (!IsTimeLimited)
1648 return;
1649  
1650 DateTime now = DateTime.Now;
1651 if (m_newGeneration.AccessedSinceLastTimeCheck)
1652 {
1653 // New generation has been accessed since last check
1654 // Update it's expiration time.
1655 m_newGeneration.ExpirationTime = now + ExpirationTime;
1656 m_newGeneration.AccessedSinceLastTimeCheck = false;
1657 }
1658 else if (m_newGeneration.ExpirationTime < now)
1659 {
1660 // New generation has been expired.
1661 // --> also old generation must be expired.
1662 PurgeGeneration(m_newGeneration);
1663 PurgeGeneration(m_oldGeneration);
1664 return;
1665 }
1666  
1667 if (m_oldGeneration.ExpirationTime < now)
1668 PurgeGeneration(m_oldGeneration);
1669 }
1670  
1671 /// <summary>
1672 /// Removes element associated with <paramref name="key"/> from the <see cref="ICnmCache{TKey,TValue}"/>.
1673 /// </summary>
1674 /// <param name="key">
1675 /// The key that is associated with element to remove from the <see cref="ICnmCache{TKey,TValue}"/>.
1676 /// </param>
1677 /// <exception cref="ArgumentNullException">
1678 /// <paramref name="key"/>is <see langword="null"/>.
1679 /// </exception>
1680 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1681 /// <seealso cref="ICnmCache{TKey,TValue}.RemoveRange"/>
1682 /// <seealso cref="ICnmCache{TKey,TValue}.TryGetValue"/>
1683 /// <seealso cref="ICnmCache{TKey,TValue}.Clear"/>
1684 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1685 public void Remove(TKey key)
1686 {
1687 if (key == null)
1688 throw new ArgumentNullException("key");
1689  
1690 int bucketIndex = GetBucketIndex(key);
1691 if (!m_newGeneration.Remove(bucketIndex, key))
1692 {
1693 if (!m_oldGeneration.Remove(bucketIndex, key))
1694 {
1695 CheckExpired();
1696 return;
1697 }
1698 }
1699  
1700 CheckExpired();
1701 m_version++;
1702 }
1703  
1704 /// <summary>
1705 /// Removes elements that are associated with one of <paramref name="keys"/> from the <see cref="ICnmCache{TKey,TValue}"/>.
1706 /// </summary>
1707 /// <param name="keys">
1708 /// The keys that are associated with elements to remove from the <see cref="ICnmCache{TKey,TValue}"/>.
1709 /// </param>
1710 /// <exception cref="ArgumentNullException">
1711 /// <paramref name="keys"/>is <see langword="null"/>.
1712 /// </exception>
1713 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1714 /// <seealso cref="ICnmCache{TKey,TValue}.Remove"/>
1715 /// <seealso cref="ICnmCache{TKey,TValue}.TryGetValue"/>
1716 /// <seealso cref="ICnmCache{TKey,TValue}.Clear"/>
1717 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1718 public void RemoveRange(IEnumerable<TKey> keys)
1719 {
1720 if (keys == null)
1721 throw new ArgumentNullException("keys");
1722  
1723 foreach (TKey key in keys)
1724 {
1725 if (key == null)
1726 continue;
1727  
1728 int bucketIndex = GetBucketIndex(key);
1729 if (!m_newGeneration.Remove(bucketIndex, key))
1730 m_oldGeneration.Remove(bucketIndex, key);
1731 }
1732  
1733 CheckExpired();
1734 m_version++;
1735 }
1736  
1737 /// <summary>
1738 /// Add or replace an element with the provided <paramref name="key"/>, <paramref name="value"/> and <paramref name="size"/> to
1739 /// <see cref="ICnmCache{TKey,TValue}"/>.
1740 /// </summary>
1741 /// <param name="key">
1742 /// The object used as the key of the element. Can't be <see langword="null"/> reference.
1743 /// </param>
1744 /// <param name="value">
1745 /// The object used as the value of the element to add or replace. <see langword="null"/> is allowed.
1746 /// </param>
1747 /// <param name="size">
1748 /// The element's size. Normally bytes, but can be any suitable unit of measure.
1749 /// </param>
1750 /// <returns>
1751 /// <see langword="true"/>if element has been added successfully to the <see cref="ICnmCache{TKey,TValue}"/>;
1752 /// otherwise <see langword="false"/>.
1753 /// </returns>
1754 /// <exception cref="ArgumentNullException">
1755 /// <paramref name="key"/>is <see langword="null"/>.
1756 /// </exception>
1757 /// <exception cref="ArgumentOutOfRangeException">
1758 /// The element's <paramref name="size"/> is less than 0.
1759 /// </exception>
1760 /// <remarks>
1761 /// <para>
1762 /// If element's <paramref name="size"/> is larger than <see cref="ICnmCache{TKey,TValue}.MaxElementSize"/>, then element is
1763 /// not added to the <see cref="ICnmCache{TKey,TValue}"/>, however - possible older element is
1764 /// removed from the <see cref="ICnmCache{TKey,TValue}"/>.
1765 /// </para>
1766 /// <para>
1767 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting total size of elements,
1768 /// <see cref="ICnmCache{TKey,TValue}"/>will remove less recently used elements until it can fit an new element.
1769 /// </para>
1770 /// <para>
1771 /// When adding an new element to <see cref="ICnmCache{TKey,TValue}"/> that is limiting element count,
1772 /// <see cref="ICnmCache{TKey,TValue}"/>will remove less recently used elements until it can fit an new element.
1773 /// </para>
1774 /// </remarks>
1775 /// <seealso cref="ICnmCache{TKey,TValue}.IsSizeLimited"/>
1776 /// <seealso cref="ICnmCache{TKey,TValue}.IsCountLimited"/>
1777 /// <seealso cref="ICnmCache{TKey,TValue}.Remove"/>
1778 /// <seealso cref="ICnmCache{TKey,TValue}.RemoveRange"/>
1779 /// <seealso cref="ICnmCache{TKey,TValue}.TryGetValue"/>
1780 /// <seealso cref="ICnmCache{TKey,TValue}.Clear"/>
1781 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1782 public bool Set(TKey key, TValue value, long size)
1783 {
1784 if (key == null)
1785 throw new ArgumentNullException("key");
1786  
1787 if (size < 0)
1788 throw new ArgumentOutOfRangeException("size", size, "Value's size can't be less than 0.");
1789  
1790 if (size > MaxElementSize)
1791 {
1792 // Entry size is too big to fit cache - ignore it
1793 Remove(key);
1794 return false;
1795 }
1796  
1797 if (size == 0)
1798 size = 1;
1799  
1800 int bucketIndex = GetBucketIndex(key);
1801 m_oldGeneration.Remove(bucketIndex, key);
1802 AddToNewGeneration(bucketIndex, key, value, size);
1803 CheckExpired();
1804  
1805 return true;
1806 }
1807  
1808 /// <summary>
1809 /// Gets the <paramref name="value"/> associated with the specified <paramref name="key"/>.
1810 /// </summary>
1811 /// <returns>
1812 /// <see langword="true"/>if the <see cref="ICnmCache{TKey,TValue}"/> contains an element with
1813 /// the specified key; otherwise, <see langword="false"/>.
1814 /// </returns>
1815 /// <param name="key">
1816 /// The key whose <paramref name="value"/> to get.
1817 /// </param>
1818 /// <param name="value">
1819 /// When this method returns, the value associated with the specified <paramref name="key"/>,
1820 /// if the <paramref name="key"/> is found; otherwise, the
1821 /// default value for the type of the <paramref name="value"/> parameter. This parameter is passed uninitialized.
1822 /// </param>
1823 /// <exception cref="ArgumentNullException">
1824 /// <paramref name="key"/>is <see langword="null"/>.
1825 /// </exception>
1826 /// <seealso cref="ICnmCache{TKey,TValue}.Set"/>
1827 /// <seealso cref="ICnmCache{TKey,TValue}.Remove"/>
1828 /// <seealso cref="ICnmCache{TKey,TValue}.RemoveRange"/>
1829 /// <seealso cref="ICnmCache{TKey,TValue}.Clear"/>
1830 /// <seealso cref="ICnmCache{TKey,TValue}.PurgeExpired"/>
1831 public bool TryGetValue(TKey key, out TValue value)
1832 {
1833 if (key == null)
1834 throw new ArgumentNullException("key");
1835  
1836 int bucketIndex = GetBucketIndex(key);
1837 long size;
1838 if (m_newGeneration.TryGetValue(bucketIndex, key, out value, out size))
1839 {
1840 CheckExpired();
1841 return true;
1842 }
1843  
1844 if (m_oldGeneration.TryGetValue(bucketIndex, key, out value, out size))
1845 {
1846 // Move element to new generation
1847 AddToNewGeneration(bucketIndex, key, value, size);
1848 CheckExpired();
1849 return true;
1850 }
1851  
1852 CheckExpired();
1853 return false;
1854 }
1855  
1856 /// <summary>
1857 /// Returns an enumerator that iterates through a collection.
1858 /// </summary>
1859 /// <returns>
1860 /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
1861 /// </returns>
1862 /// <filterpriority>2</filterpriority>
1863 IEnumerator IEnumerable.GetEnumerator()
1864 {
1865 return GetEnumerator();
1866 }
1867  
1868 #endregion
1869 }
1870 }