kernel/eka/kernel/smap.cpp
changeset 0 a41df078684a
equal deleted inserted replaced
-1:000000000000 0:a41df078684a
       
     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 	}