1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 #include "osclconfig_proc.h" 19 20 //Doubly-linked list implementation 21 22 #include "oscl_scheduler.h" 23 #include "oscl_error.h" 24 #include "oscl_assert.h" 25 26 #if (OSCL_DISABLE_INLINES) 27 //#include "oscl_aostatus.inl" 28 #endif 29 30 ////////////////////////////////// 31 // OsclDoubleLink 32 ////////////////////////////////// 33 InsertAfter(OsclDoubleLink * aLink)34void OsclDoubleLink::InsertAfter(OsclDoubleLink *aLink) 35 //add this item after aLink 36 { 37 iPrev = aLink; 38 if (aLink) 39 { 40 iNext = aLink->iNext; 41 aLink->iNext = this; 42 if (iNext) 43 iNext->iPrev = this; 44 } 45 } 46 InsertBefore(OsclDoubleLink * aLink)47void OsclDoubleLink::InsertBefore(OsclDoubleLink *aLink) 48 //add this item before aLink 49 { 50 iNext = aLink; 51 if (aLink) 52 { 53 iPrev = aLink->iPrev; 54 aLink->iPrev = this; 55 if (iPrev) 56 iPrev->iNext = this; 57 } 58 } 59 Remove()60void OsclDoubleLink::Remove() 61 //remove this item. 62 { 63 if (iNext) 64 { 65 iNext->iPrev = iPrev; 66 if (iPrev) 67 iPrev->iNext = iNext; 68 } 69 iNext = iPrev = NULL; 70 } 71 72 73 ////////////////////////////////// 74 // OsclDoubleListBase 75 ////////////////////////////////// OsclDoubleListBase()76OsclDoubleListBase::OsclDoubleListBase() 77 { 78 iOffset = (-1);//invalid. 79 iHead.iNext = iHead.iPrev = &iHead; 80 } 81 IsEmpty() const82bool OsclDoubleListBase::IsEmpty()const 83 { 84 return ((void*)iHead.iNext == (void*)&iHead); 85 } 86 SetOffset(int32 aOffset)87void OsclDoubleListBase::SetOffset(int32 aOffset) 88 //offset contains the offset into the TAny item of its TDblQueLinkBase item. 89 { 90 //offset should not be negative. 91 OSCL_ASSERT(aOffset >= 0); 92 93 //just save it for later. 94 iOffset = aOffset; 95 } 96 InsertHead(OsclAny * aPtr)97void OsclDoubleListBase::InsertHead(OsclAny* aPtr) 98 { 99 //offset must be set before calling this 100 OSCL_ASSERT(iOffset >= 0); 101 102 //find the item link 103 OsclDoubleLink * link = (OsclDoubleLink *)OsclPtrAdd(aPtr, iOffset); 104 if (IsEmpty()) 105 { 106 //make the head of the que point to this item link 107 iHead.iNext = link; 108 iHead.iPrev = link; 109 110 //make the item link point back to the head 111 link->iPrev = &iHead; 112 link->iNext = &iHead; 113 } 114 else 115 { 116 link->InsertBefore(iHead.iNext); 117 } 118 } 119 InsertTail(OsclAny * aPtr)120void OsclDoubleListBase::InsertTail(OsclAny* aPtr) 121 { 122 //offset must be set before calling this 123 OSCL_ASSERT(iOffset >= 0); 124 125 //find the item link 126 OsclDoubleLink * link = (OsclDoubleLink *)OsclPtrAdd(aPtr, iOffset); 127 128 if (IsEmpty()) 129 InsertHead(aPtr); 130 else 131 link->InsertAfter(iHead.iPrev); 132 } 133 Insert(OsclAny * aPtr)134void OsclDoubleListBase::Insert(OsclAny* aPtr) 135 //sorted queue insert. This inserts an item at the 136 //end of its priority group. 137 { 138 //offset must be set before calling this 139 OSCL_ASSERT(iOffset >= 0); 140 if (IsEmpty()) 141 InsertHead(aPtr); 142 else 143 { 144 //find the item link 145 OsclPriorityLink* link = (OsclPriorityLink*)OsclPtrAdd(aPtr, iOffset); 146 147 OsclPriorityLink* itemlink = (OsclPriorityLink*)iHead.iNext; 148 while (itemlink) 149 { 150 //add before first item with lower priority. 151 if (link->iPriority > itemlink->iPriority) 152 { 153 link->InsertBefore(itemlink); 154 return; 155 } 156 157 if (itemlink->iNext == &iHead) 158 break; 159 itemlink = (OsclPriorityLink*)itemlink->iNext; 160 } 161 //no lower pri items-- add to end. 162 link->InsertAfter(iHead.iPrev); 163 } 164 } 165