Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Base / MS / Internal / PriorityQueue.cs / 1305600 / PriorityQueue.cs
using System; using System.Collections.Generic; using System.Diagnostics; namespace System.Windows.Threading { internal class PriorityQueue{ public PriorityQueue() { // Build the collection of priority chains. _priorityChains = new SortedList >(); // NOTE: should be Priority _cacheReusableChains = new Stack >(10); _head = _tail = null; _count = 0; } // NOTE: not used // public int Count {get{return _count;}} public DispatcherPriority MaxPriority // NOTE: should be Priority { get { int count = _priorityChains.Count; if(count > 0) { return (DispatcherPriority) _priorityChains.Keys[count - 1]; } else { return DispatcherPriority.Invalid; // NOTE: should be Priority.Invalid; } } } public PriorityItem Enqueue(DispatcherPriority priority, T data) // NOTE: should be Priority { // Find the existing chain for this priority, or create a new one // if one does not exist. PriorityChain chain = GetChain(priority); // Wrap the item in a PriorityItem so we can put it in our // linked list. PriorityItem priorityItem = new PriorityItem (data); // Step 1: Append this to the end of the "sequential" linked list. InsertItemInSequentialChain(priorityItem, _tail); // Step 2: Append the item into the priority chain. InsertItemInPriorityChain(priorityItem, chain, chain.Tail); return priorityItem; } public T Dequeue() { // Get the max-priority chain. int count = _priorityChains.Count; if(count > 0) { PriorityChain chain = _priorityChains.Values[count - 1]; Debug.Assert(chain != null, "PriorityQueue.Dequeue: a chain should exist."); PriorityItem item = chain.Head; Debug.Assert(item != null, "PriorityQueue.Dequeue: a priority item should exist."); RemoveItem(item); return item.Data; } else { throw new InvalidOperationException(); } } public T Peek() { T data = default(T); // Get the max-priority chain. int count = _priorityChains.Count; if(count > 0) { PriorityChain chain = _priorityChains.Values[count - 1]; Debug.Assert(chain != null, "PriorityQueue.Peek: a chain should exist."); PriorityItem item = chain.Head; Debug.Assert(item != null, "PriorityQueue.Peek: a priority item should exist."); data = item.Data; } return data; } public void RemoveItem(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItem: invalid item."); Debug.Assert(item.Chain != null, "PriorityQueue.RemoveItem: a chain should exist."); PriorityChain chain = item.Chain; // Step 1: Remove the item from its priority chain. RemoveItemFromPriorityChain(item); // Step 2: Remove the item from the sequential chain. RemoveItemFromSequentialChain(item); // Note: we do not clean up empty chains on purpose to reduce churn. } public void ChangeItemPriority(PriorityItem item, DispatcherPriority priority) // NOTE: should be Priority { // Remove the item from its current priority and insert it into // the new priority chain. Note that this does not change the // sequential ordering. // Step 1: Remove the item from the priority chain. RemoveItemFromPriorityChain(item); // Step 2: Insert the item into the new priority chain. // Find the existing chain for this priority, or create a new one // if one does not exist. PriorityChain chain = GetChain(priority); InsertItemInPriorityChain(item, chain); } private PriorityChain GetChain(DispatcherPriority priority) // NOTE: should be Priority { PriorityChain chain = null; int count = _priorityChains.Count; if(count > 0) { if(priority == (DispatcherPriority) _priorityChains.Keys[0]) { chain = _priorityChains.Values[0]; } else if(priority == (DispatcherPriority) _priorityChains.Keys[count - 1]) { chain = _priorityChains.Values[count - 1]; } else if((priority > (DispatcherPriority) _priorityChains.Keys[0]) && (priority < (DispatcherPriority) _priorityChains.Keys[count - 1])) { _priorityChains.TryGetValue((int)priority, out chain); } } if(chain == null) { if(_cacheReusableChains.Count > 0) { chain = _cacheReusableChains.Pop(); chain.Priority = priority; } else { chain = new PriorityChain (priority); } _priorityChains.Add((int)priority, chain); } return chain; } private void InsertItemInPriorityChain(PriorityItem item, PriorityChain chain) { // Scan along the sequential chain, in the previous direction, // looking for an item that is already in the new chain. We will // insert ourselves after the item we found. We can short-circuit // this search if the new chain is empty. if(chain.Head == null) { Debug.Assert(chain.Tail == null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should be null."); InsertItemInPriorityChain(item, chain, null); } else { Debug.Assert(chain.Tail != null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should not be null."); PriorityItem after = null; // Search backwards along the sequential chain looking for an // item already in this list. for(after = item.SequentialPrev; after != null; after = after.SequentialPrev) { if(after.Chain == chain) { break; } } InsertItemInPriorityChain(item, chain, after); } } internal void InsertItemInPriorityChain(PriorityItem item, PriorityChain chain, PriorityItem after) { Debug.Assert(chain != null, "PriorityQueue.InsertItemInPriorityChain: a chain must be provided."); Debug.Assert(item.Chain == null && item.PriorityPrev == null && item.PriorityNext == null, "PriorityQueue.InsertItemInPriorityChain: item must not already be in a priority chain."); item.Chain = chain; if(after == null) { // Note: passing null for after means insert at the head. if(chain.Head != null) { Debug.Assert(chain.Tail != null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should not be null."); chain.Head.PriorityPrev = item; item.PriorityNext = chain.Head; chain.Head = item; } else { Debug.Assert(chain.Tail == null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should be null."); chain.Head = chain.Tail = item; } } else { item.PriorityPrev = after; if(after.PriorityNext != null) { item.PriorityNext = after.PriorityNext; after.PriorityNext.PriorityPrev = item; after.PriorityNext = item; } else { Debug.Assert(item.Chain.Tail == after, "PriorityQueue.InsertItemInPriorityChain: the chain's tail should be the item we are inserting after."); after.PriorityNext = item; chain.Tail = item; } } chain.Count++; } private void RemoveItemFromPriorityChain(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItemFromPriorityChain: invalid item."); Debug.Assert(item.Chain != null, "PriorityQueue.RemoveItemFromPriorityChain: a chain should exist."); // Step 1: Fix up the previous link if(item.PriorityPrev != null) { Debug.Assert(item.Chain.Head != item, "PriorityQueue.RemoveItemFromPriorityChain: the head should not point to this item."); item.PriorityPrev.PriorityNext = item.PriorityNext; } else { Debug.Assert(item.Chain.Head == item, "PriorityQueue.RemoveItemFromPriorityChain: the head should point to this item."); item.Chain.Head = item.PriorityNext; } // Step 2: Fix up the next link if(item.PriorityNext != null) { Debug.Assert(item.Chain.Tail != item, "PriorityQueue.RemoveItemFromPriorityChain: the tail should not point to this item."); item.PriorityNext.PriorityPrev = item.PriorityPrev; } else { Debug.Assert(item.Chain.Tail == item, "PriorityQueue.RemoveItemFromPriorityChain: the tail should point to this item."); item.Chain.Tail = item.PriorityPrev; } // Step 3: cleanup item.PriorityPrev = item.PriorityNext = null; item.Chain.Count--; if(item.Chain.Count == 0) { if(item.Chain.Priority == (DispatcherPriority) _priorityChains.Keys[_priorityChains.Count - 1]) { _priorityChains.RemoveAt(_priorityChains.Count - 1); } else { _priorityChains.Remove((int) item.Chain.Priority); } if(_cacheReusableChains.Count < 10) { item.Chain.Priority = DispatcherPriority.Invalid; // NOTE: should be Priority.Invalid _cacheReusableChains.Push(item.Chain); } } item.Chain = null; } internal void InsertItemInSequentialChain(PriorityItem item, PriorityItem after) { Debug.Assert(item.SequentialPrev == null && item.SequentialNext == null, "PriorityQueue.InsertItemInSequentialChain: item must not already be in the sequential chain."); if(after == null) { // Note: passing null for after means insert at the head. if(_head != null) { Debug.Assert(_tail != null, "PriorityQueue.InsertItemInSequentialChain: both the head and the tail should not be null."); _head.SequentialPrev = item; item.SequentialNext = _head; _head = item; } else { Debug.Assert(_tail == null, "PriorityQueue.InsertItemInSequentialChain: both the head and the tail should be null."); _head = _tail = item; } } else { item.SequentialPrev = after; if(after.SequentialNext != null) { item.SequentialNext = after.SequentialNext; after.SequentialNext.SequentialPrev = item; after.SequentialNext = item; } else { Debug.Assert(_tail == after, "PriorityQueue.InsertItemInSequentialChain: the tail should be the item we are inserting after."); after.SequentialNext = item; _tail = item; } } _count++; } private void RemoveItemFromSequentialChain(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItemFromSequentialChain: invalid item."); // Step 1: Fix up the previous link if(item.SequentialPrev != null) { Debug.Assert(_head != item, "PriorityQueue.RemoveItemFromSequentialChain: the head should not point to this item."); item.SequentialPrev.SequentialNext = item.SequentialNext; } else { Debug.Assert(_head == item, "PriorityQueue.RemoveItemFromSequentialChain: the head should point to this item."); _head = item.SequentialNext; } // Step 2: Fix up the next link if(item.SequentialNext != null) { Debug.Assert(_tail != item, "PriorityQueue.RemoveItemFromSequentialChain: the tail should not point to this item."); item.SequentialNext.SequentialPrev = item.SequentialPrev; } else { Debug.Assert(_tail == item, "PriorityQueue.RemoveItemFromSequentialChain: the tail should point to this item."); _tail = item.SequentialPrev; } // Step 3: cleanup item.SequentialPrev = item.SequentialNext = null; _count--; } // Priority chains... private SortedList > _priorityChains; // NOTE: should be Priority private Stack > _cacheReusableChains; // Sequential chain... private PriorityItem _head; private PriorityItem _tail; private int _count; } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- WebMessageEncoderFactory.cs
- sqlpipe.cs
- SignatureConfirmations.cs
- Gdiplus.cs
- DataServiceClientException.cs
- SqlComparer.cs
- GraphicsState.cs
- DrawingAttributesDefaultValueFactory.cs
- ProcessHost.cs
- DataPagerFieldCollection.cs
- CoreChannel.cs
- Config.cs
- EncoderNLS.cs
- ColorConvertedBitmap.cs
- XmlArrayItemAttribute.cs
- QueryReaderSettings.cs
- ControlBindingsCollection.cs
- OrElse.cs
- WinEventWrap.cs
- XmlRawWriterWrapper.cs
- StreamingContext.cs
- XmlSchemaInfo.cs
- ClientCultureInfo.cs
- FamilyCollection.cs
- DataError.cs
- MarginsConverter.cs
- ScriptReference.cs
- ContourSegment.cs
- NamedPipeHostedTransportConfiguration.cs
- AnimationStorage.cs
- InstanceNotReadyException.cs
- ConnectionManagementSection.cs
- WsdlInspector.cs
- ListControl.cs
- TextTreeRootTextBlock.cs
- XmlQueryRuntime.cs
- ExpressionVisitor.cs
- XPathMultyIterator.cs
- SqlInfoMessageEvent.cs
- PageCatalogPart.cs
- PnrpPeerResolver.cs
- EncryptedPackage.cs
- PathData.cs
- ProfileSettings.cs
- sqlpipe.cs
- HashRepartitionStream.cs
- AlternateViewCollection.cs
- HwndTarget.cs
- ControlParameter.cs
- PathGeometry.cs
- DecoderBestFitFallback.cs
- ExpressionList.cs
- LocatorGroup.cs
- FormViewRow.cs
- DoubleAnimationBase.cs
- OperationPerformanceCounters.cs
- DeleteIndexBinder.cs
- XmlRawWriter.cs
- XmlHierarchicalDataSourceView.cs
- SourceFileBuildProvider.cs
- ContextMenu.cs
- XmlValidatingReader.cs
- WithParamAction.cs
- LineInfo.cs
- BroadcastEventHelper.cs
- AuthenticationService.cs
- DropShadowEffect.cs
- UserValidatedEventArgs.cs
- ActiveXHost.cs
- TreeNodeBindingCollection.cs
- HtmlWindow.cs
- Comparer.cs
- CheckBoxPopupAdapter.cs
- XDRSchema.cs
- ArrangedElement.cs
- EntityContainer.cs
- XPathDocumentIterator.cs
- LookupNode.cs
- ForeignConstraint.cs
- PolicyLevel.cs
- SparseMemoryStream.cs
- Positioning.cs
- RectAnimationUsingKeyFrames.cs
- WindowsComboBox.cs
- SingleStorage.cs
- CommandID.cs
- ProviderUtil.cs
- MethodExpression.cs
- RegexMatchCollection.cs
- StylusSystemGestureEventArgs.cs
- SafeArrayRankMismatchException.cs
- graph.cs
- SettingsSection.cs
- ConfigXmlComment.cs
- DbModificationCommandTree.cs
- ActiveDesignSurfaceEvent.cs
- ChannelManagerHelpers.cs
- EntityContainerEntitySet.cs
- ApplicationSecurityInfo.cs
- FormViewUpdateEventArgs.cs