|
1 // Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of the License "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // e32\kernel\smap.cpp |
|
15 |
|
16 #include <kernel/kern_priv.h> |
|
17 #include "smap.h" |
|
18 |
|
19 |
|
20 /** |
|
21 SMap uses a binary search to perform quick lookups (finds) whilst Add and |
|
22 Remove and Iterating is happening concurrently. This container is optimised |
|
23 for fast lookups. |
|
24 |
|
25 Add, Remove and Iterator check that the caller has the heavyweight (slow) mutex lock |
|
26 held. |
|
27 |
|
28 Find methods take the fast lock whilst performing look ups. |
|
29 */ |
|
30 |
|
31 SMap::SMap(NFastMutex* aFastLock, DMutex* aSlowLock) |
|
32 : iCount(0), iList(0), iFastLock(aFastLock), iSlowLock(aSlowLock) |
|
33 {} |
|
34 |
|
35 SMap::~SMap() |
|
36 { |
|
37 Kern::Free(iList); |
|
38 } |
|
39 |
|
40 /** |
|
41 Add checks that the caller has the heavyweight mutex held, determines the |
|
42 entry point in the array for the new entry and performs a copy and swap |
|
43 with a newly-allocated array. |
|
44 */ |
|
45 TInt SMap::Add(TUint aKey, TAny* aObject) |
|
46 { |
|
47 __NK_ASSERT_DEBUG(aObject); |
|
48 __ASSERT_MUTEX(iSlowLock); |
|
49 |
|
50 __ASSERT_CRITICAL; |
|
51 |
|
52 #ifdef _DEBUG |
|
53 if (K::CheckForSimulatedAllocFail()) |
|
54 { |
|
55 __KTRACE_OPT(KMMU,Kern::Printf("SMap::Add returns simulated OOM %d",KErrNoMemory)); |
|
56 return KErrNoMemory; |
|
57 } |
|
58 #endif |
|
59 TEntry* newlist = (TEntry*)Kern::Alloc(sizeof(TEntry)*(iCount + 1)); |
|
60 |
|
61 if (!newlist) |
|
62 return KErrNoMemory; |
|
63 |
|
64 // find list insertion point... |
|
65 TUint i = FindIndex(aKey); |
|
66 TEntry* entry = newlist + i; |
|
67 |
|
68 // make room... |
|
69 if (i) |
|
70 { |
|
71 TUint moveSize = i * sizeof(TEntry); |
|
72 wordmove(newlist, iList, moveSize); |
|
73 } |
|
74 |
|
75 TUint moveSize = (iCount - i) * sizeof(TEntry); |
|
76 wordmove(entry + 1, iList + i,moveSize); |
|
77 |
|
78 #ifdef _DEBUG |
|
79 if (iList) |
|
80 K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newlist); |
|
81 #endif |
|
82 |
|
83 // copy in new entry... |
|
84 entry->iKey = aKey; |
|
85 entry->iObj = aObject; |
|
86 TEntry* cleanup = iList; |
|
87 |
|
88 FastLock(); |
|
89 // swap |
|
90 ++iCount; |
|
91 iList = newlist; |
|
92 FastUnlock(); |
|
93 |
|
94 Kern::Free(cleanup); |
|
95 return KErrNone; |
|
96 } |
|
97 |
|
98 /** |
|
99 Remove checks that the caller has the heavyweight mutex held, determines the |
|
100 entry point in the array for the entry to be removed. It shuffles the entries |
|
101 left flashing the fast lock so as not to prevent 'finds' from being blocked. |
|
102 */ |
|
103 TAny* SMap::Remove(TUint aKey) |
|
104 { |
|
105 __ASSERT_CRITICAL; |
|
106 __ASSERT_MUTEX(iSlowLock); |
|
107 |
|
108 // search for it... |
|
109 TUint i = FindIndex(aKey); |
|
110 TEntry* entry = iList + i - 1; |
|
111 |
|
112 if (!i || entry->iKey != aKey) |
|
113 { |
|
114 // not found... |
|
115 return NULL; |
|
116 } |
|
117 |
|
118 // get objects... |
|
119 TAny* result = entry->iObj; |
|
120 __NK_ASSERT_DEBUG(result); |
|
121 |
|
122 FastLock(); |
|
123 if (iCount > 1) |
|
124 { |
|
125 // the shuffle the entries a maximum of 4 at a time |
|
126 // in the existing memory flashing the lock, so as not to hold it too |
|
127 // long |
|
128 // Note Add and Remove cannot be performed while shuffling the |
|
129 // entries, but fast lookups can |
|
130 while (i < iCount) |
|
131 { |
|
132 TInt entries = Min((TInt)(iCount - i), 4); |
|
133 wordmove(&iList[i-1], &iList[i], entries * sizeof(TEntry)); |
|
134 i += entries; |
|
135 NKern::FMFlash(iFastLock); |
|
136 } |
|
137 } |
|
138 |
|
139 --iCount; |
|
140 FastUnlock(); |
|
141 return result; |
|
142 } |
|
143 |
|
144 /** |
|
145 FindIndex returns the index into an array of entries for a given key, by |
|
146 performing a binary search. |
|
147 |
|
148 @returns Zero if entry not found, otherwise returns 1 + index into |
|
149 the array of entries |
|
150 */ |
|
151 TUint SMap::FindIndex(TUint aKey) |
|
152 { |
|
153 TEntry* list = iList; |
|
154 |
|
155 TUint l = 0; |
|
156 TUint r = iCount; |
|
157 TUint m; |
|
158 |
|
159 while (l < r) |
|
160 { |
|
161 m = (l + r) >> 1; |
|
162 TUint32 x = list[m].iKey; |
|
163 if (x <= aKey) |
|
164 l = m + 1; |
|
165 else |
|
166 r = m; |
|
167 } |
|
168 |
|
169 return r; |
|
170 } |
|
171 |
|
172 /** |
|
173 Find returns a pointer to the data (TAny) corresponding to the lookup key |
|
174 |
|
175 @returns Returns NULL if entry not found, otherwise a pointer to the |
|
176 data corresponding to the key |
|
177 */ |
|
178 TAny* SMap::Find(TUint aKey) |
|
179 { |
|
180 __NK_ASSERT_DEBUG(iFastLock->HeldByCurrentThread()); |
|
181 |
|
182 TUint i = FindIndex(aKey); |
|
183 |
|
184 if (i == 0) |
|
185 return NULL; |
|
186 |
|
187 TEntry* entry = iList + i; |
|
188 |
|
189 --entry; |
|
190 |
|
191 if (aKey != entry->iKey) |
|
192 return NULL; |
|
193 |
|
194 TAny* result = entry->iObj; |
|
195 __NK_ASSERT_DEBUG(result); |
|
196 return result; |
|
197 } |
|
198 |
|
199 void SMap::TIterator::Reset() |
|
200 { |
|
201 iPos = 0; |
|
202 } |
|
203 |
|
204 SMap::TEntry* SMap::TIterator::Next() |
|
205 { |
|
206 __ASSERT_MUTEX(iMap.iSlowLock); |
|
207 |
|
208 if (iPos < iMap.iCount) |
|
209 return &iMap.iList[iPos++]; |
|
210 |
|
211 return NULL; |
|
212 } |