author | Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com> |
Fri, 17 Sep 2010 08:32:10 +0300 | |
changeset 28 | b7da29130b0e |
parent 21 | 4633027730f5 |
permissions | -rw-r--r-- |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
1 |
/**************************************************************************** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
2 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
3 |
** Copyright (C) 2008-2010 Nokia Corporation and/or its subsidiary(-ies). |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
4 |
** All rights reserved. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
5 |
** Contact: Nokia Corporation (developer.feedback@nokia.com) |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
6 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
7 |
** This file is part of the HbCore module of the UI Extensions for Mobile. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
8 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
9 |
** GNU Lesser General Public License Usage |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
10 |
** This file may be used under the terms of the GNU Lesser General Public |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
11 |
** License version 2.1 as published by the Free Software Foundation and |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
12 |
** appearing in the file LICENSE.LGPL included in the packaging of this file. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
13 |
** Please review the following information to ensure the GNU Lesser General |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
14 |
** Public License version 2.1 requirements will be met: |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
15 |
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
16 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
17 |
** In addition, as a special exception, Nokia gives you certain additional |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
18 |
** rights. These rights are described in the Nokia Qt LGPL Exception |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
19 |
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
20 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
21 |
** If you have questions regarding the use of this file, please contact |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
22 |
** Nokia at developer.feedback@nokia.com. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
23 |
** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
24 |
****************************************************************************/ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
25 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
26 |
#include "hbsharedmemoryallocators_p.h" |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
27 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
28 |
#include <QSharedMemory> |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
29 |
#include <QDebug> |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
30 |
|
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
31 |
#define TO_PTR(x) ((char *)(toPointer(x))) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
32 |
#define TO_NODE_POINTER(x) ((TreeNode *)(toPointer(x))) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
33 |
#define TO_BLOCK_POINTER(x) ((MemoryBlock *)(toPointer(x))) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
34 |
#define TO_NODE_OFFSET(x) ((int)((char *)(x)-(char *)(chunk->data()))) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
35 |
#define TO_OFFSET(x) ((int)((char *)(x)-(char *)(chunk->data()))) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
36 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
37 |
// this identifier is used to check, if the splay tree is already |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
38 |
// initialized in given shared chunk |
28
b7da29130b0e
Revision: 201035
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
21
diff
changeset
|
39 |
const quint32 INITIALIZED_ALLOCATOR_IDENTIFIER = 0x53504C59; //'SPLY' |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
40 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
41 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
42 |
* HbSplayTreeAllocator::initialize |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
43 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
44 |
* Initializes splay tree and internal variables. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
45 |
* This can't fail if sharedChunk is valid. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
46 |
*/ |
6
c3690ec91ef8
Revision: 201023
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
3
diff
changeset
|
47 |
void HbSplayTreeAllocator::initialize(HbSharedMemoryWrapper *sharedChunk, |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
48 |
const quintptr offset, |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
49 |
HbSharedMemoryAllocator *mainAllocator) |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
50 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
51 |
Q_UNUSED(mainAllocator); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
52 |
chunk = sharedChunk; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
53 |
this->offset = offset; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
54 |
|
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
55 |
header = address<HeapHeader>(offset); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
56 |
if (header->identifier == INITIALIZED_ALLOCATOR_IDENTIFIER) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
57 |
return; // already initialized |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
58 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
59 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
60 |
memset(header, 0, sizeof(HeapHeader)); |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
61 |
header->freeBytes = chunk->size() - offset - sizeof(HeapHeader) - sizeof(MemoryBlock); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
62 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
63 |
// insert first memory block in chunk |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
64 |
MemoryBlock *block = reinterpret_cast<MemoryBlock*>(&header[1]); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
65 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
66 |
block->pointerNode.key = TO_OFFSET(block); |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
67 |
block->lengthNode.key = static_cast<quintptr>(header->freeBytes); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
68 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
69 |
insertLengthNode(&header->lengthNode, &block->lengthNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
70 |
insertNode(&header->pointerNode, &block->pointerNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
71 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
72 |
header->identifier = INITIALIZED_ALLOCATOR_IDENTIFIER; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
73 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
74 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
75 |
// Constructor |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
76 |
// |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
77 |
HbSplayTreeAllocator::HbSplayTreeAllocator() |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
78 |
: chunk(0), |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
79 |
offset(0) |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
80 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
81 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
82 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
83 |
// Destructor |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
84 |
// |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
85 |
HbSplayTreeAllocator::~HbSplayTreeAllocator() |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
86 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
87 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
88 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
89 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
90 |
* HbSplayTreeAllocator::toPointer |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
91 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
92 |
* Helper function for converting offset to pointer |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
93 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
94 |
void *HbSplayTreeAllocator::toPointer(quintptr offset) const |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
95 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
96 |
if (offset >= sizeof(HeapHeader)) { |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
97 |
unsigned char *base = static_cast<unsigned char*>(chunk->data()); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
98 |
return (&base[offset]); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
99 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
100 |
return 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
101 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
102 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
103 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
104 |
* HbSplayTreeAllocator::alloc |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
105 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
106 |
* Allocate size bytes from shared memory. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
107 |
* Returns offset of allocated memory in shared chunk |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
108 |
* or -1 if allocation failed. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
109 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
110 |
qptrdiff HbSplayTreeAllocator::alloc(int size) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
111 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
112 |
if (size <= 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
113 |
throw std::bad_alloc(); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
114 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
115 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
116 |
size = ALIGN(size); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
117 |
|
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
118 |
if (size > int(header->freeBytes - sizeof(MemoryBlock))) { |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
119 |
throw std::bad_alloc(); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
120 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
121 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
122 |
// splay the 'length' tree to obtain the best match |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
123 |
TreeNode *node = TO_NODE_POINTER(splay(&header->lengthNode, static_cast<quintptr>(size))); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
124 |
bool splayed = true; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
125 |
|
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
126 |
if (node && (node->key < static_cast<quintptr>(size))) { |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
127 |
splayed = false; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
128 |
node = TO_NODE_POINTER(node->rightNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
129 |
if (node) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
130 |
while (node->leftNode) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
131 |
node = TO_NODE_POINTER(node->leftNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
132 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
133 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
134 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
135 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
136 |
// no big enough nodes found, return error |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
137 |
if (!node) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
138 |
throw std::bad_alloc(); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
139 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
140 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
141 |
// 'length' node is the first attribute of the MemoryBlock, therefore every |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
142 |
// 'length' node is also a MemoryBlock. |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
143 |
MemoryBlock *block = reinterpret_cast<MemoryBlock*>(node); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
144 |
int totalSize = size + sizeof(MemoryBlock); |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
145 |
int remainingSize = int(node->key) - totalSize; |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
146 |
unsigned char *ptr = reinterpret_cast<unsigned char*>(&block[1]); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
147 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
148 |
// Remove current block from the trees |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
149 |
deleteLengthNode(&header->lengthNode, node, splayed); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
150 |
deleteNode(&header->pointerNode, &block->pointerNode, false); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
151 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
152 |
// If the block is larger than the requested size, split the block and |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
153 |
// insert the second block into the trees |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
154 |
MemoryBlock *secondBlock = reinterpret_cast<MemoryBlock*>(&ptr[size]); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
155 |
if (remainingSize >= ALIGN_SIZE |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
156 |
&& reinterpret_cast<unsigned char*>(secondBlock) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
157 |
< address<unsigned char>(chunk->size() - sizeof(MemoryBlock))) { |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
158 |
|
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
159 |
block->lengthNode.key = static_cast<quintptr>(size); |
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
160 |
secondBlock->lengthNode.key = static_cast<quintptr>(remainingSize); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
161 |
secondBlock->pointerNode.key = TO_NODE_OFFSET(secondBlock); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
162 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
163 |
// Insert the second block into the trees |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
164 |
insertLengthNode(&header->lengthNode, &secondBlock->lengthNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
165 |
insertNode(&header->pointerNode, &secondBlock->pointerNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
166 |
} else { |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
167 |
totalSize = int(node->key); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
168 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
169 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
170 |
// Adjust the allocation size |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
171 |
header->freeBytes -= totalSize; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
172 |
header->allocatedBytes += totalSize; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
173 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
174 |
// Clear attributes and return the pointer |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
175 |
block->lengthNode.leftNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
176 |
block->lengthNode.rightNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
177 |
block->pointerNode.leftNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
178 |
block->pointerNode.rightNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
179 |
block->next = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
180 |
block->prev = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
181 |
block->allocatorIdentifier = MAIN_ALLOCATOR_IDENTIFIER; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
182 |
|
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
183 |
return TO_OFFSET(ptr); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
184 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
185 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
186 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
187 |
* HbSplayTreeAllocator::allocatedSize |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
188 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
189 |
* Used for reallocation. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
190 |
* Returns actual allocated size for given offset. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
191 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
192 |
int HbSplayTreeAllocator::allocatedSize(qptrdiff offset) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
193 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
194 |
int size = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
195 |
if (offset > 0) { |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
196 |
char *srcPtr = TO_PTR(offset); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
197 |
MemoryBlock *block = reinterpret_cast<MemoryBlock*>(srcPtr - sizeof(MemoryBlock)); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
198 |
size = block->lengthNode.key; |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
199 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
200 |
return size; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
201 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
202 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
203 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
204 |
* HbSplayTreeAllocator::free |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
205 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
206 |
* Releases memory by pushing MemoryBlock's nodes back into the trees. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
207 |
* Also does adjacent free blocks merging. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
208 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
209 |
void HbSplayTreeAllocator::free(qptrdiff offset) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
210 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
211 |
if (offset <= 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
212 |
return; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
213 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
214 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
215 |
MemoryBlock *block = TO_BLOCK_POINTER(offset - sizeof(MemoryBlock)); |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
216 |
MemoryBlock *nextBlock = reinterpret_cast<MemoryBlock*>(reinterpret_cast<char*>(&block[1]) + block->lengthNode.key); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
217 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
218 |
// Adjust the free bytes |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
219 |
header->freeBytes += block->lengthNode.key; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
220 |
header->allocatedBytes -= block->lengthNode.key; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
221 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
222 |
TreeNode *node = 0; |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
223 |
quintptr predecessor = 0; |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
224 |
if (reinterpret_cast<char*>(nextBlock) > reinterpret_cast<char*>(chunk->data()) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
225 |
&& reinterpret_cast<char*>(nextBlock) < address<char>(chunk->size())) { |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
226 |
node = TO_NODE_POINTER(splay(&header->pointerNode, nextBlock->pointerNode.key)); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
227 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
228 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
229 |
if (node) { |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
230 |
// Find previous block |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
231 |
if (node->key < nextBlock->pointerNode.key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
232 |
predecessor = TO_NODE_OFFSET(node); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
233 |
} else if ((predecessor = node->leftNode) > 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
234 |
while (TO_NODE_POINTER(predecessor)->rightNode) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
235 |
predecessor = TO_NODE_POINTER(predecessor)->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
236 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
237 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
238 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
239 |
// See if the block can be merged with the sucessor |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
240 |
if (node->key == nextBlock->pointerNode.key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
241 |
// Remove the successor from both trees |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
242 |
deleteLengthNode(&header->lengthNode, &nextBlock->lengthNode, false); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
243 |
deleteNode(&header->pointerNode, &nextBlock->pointerNode, true); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
244 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
245 |
// Adjust the size |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
246 |
block->lengthNode.key += (nextBlock->lengthNode.key + sizeof(MemoryBlock)); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
247 |
header->freeBytes += sizeof(MemoryBlock); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
248 |
header->allocatedBytes -= sizeof(MemoryBlock); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
249 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
250 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
251 |
// See if the block can be merged with the predecessor |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
252 |
if (predecessor) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
253 |
MemoryBlock *b = TO_BLOCK_POINTER(TO_NODE_POINTER(predecessor)->key); |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
254 |
MemoryBlock *t = reinterpret_cast<MemoryBlock*>( |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
255 |
reinterpret_cast<unsigned char*>(&b[1]) + b->lengthNode.key); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
256 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
257 |
// Merge with the predecessor |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
258 |
if (t->pointerNode.key == block->pointerNode.key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
259 |
// Remove the predecessor from the 'length' tree |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
260 |
deleteLengthNode(&header->lengthNode, &b->lengthNode, false); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
261 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
262 |
// Adjust the size |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
263 |
b->lengthNode.key += block->lengthNode.key + sizeof(MemoryBlock); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
264 |
header->freeBytes += sizeof(MemoryBlock); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
265 |
header->allocatedBytes -= sizeof(MemoryBlock); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
266 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
267 |
// Re-insert the node in 'length' tree |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
268 |
insertLengthNode(&header->lengthNode, &b->lengthNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
269 |
block = 0; // We don't have to insert the node |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
270 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
271 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
272 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
273 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
274 |
// Insert the node |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
275 |
if (block) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
276 |
insertLengthNode(&header->lengthNode, &block->lengthNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
277 |
insertNode(&header->pointerNode, &block->pointerNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
278 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
279 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
280 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
281 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
282 |
* HbSplayTreeAllocator::splay |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
283 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
284 |
* Adjust the tree so that the best matching node goes to the top. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
285 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
286 |
quintptr HbSplayTreeAllocator::splay(quintptr *root, quintptr key) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
287 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
288 |
TreeNode *t = TO_NODE_POINTER(*root); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
289 |
if (!t) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
290 |
return 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
291 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
292 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
293 |
TreeNode n; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
294 |
n.key = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
295 |
n.leftNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
296 |
n.rightNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
297 |
TreeNode *left = &n; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
298 |
TreeNode *right = left; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
299 |
TreeNode *temp = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
300 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
301 |
for (;;) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
302 |
if (key < t->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
303 |
if (t->leftNode == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
304 |
break; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
305 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
306 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
307 |
// Rotate right |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
308 |
if (key < TO_NODE_POINTER(t->leftNode)->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
309 |
temp = TO_NODE_POINTER(t->leftNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
310 |
t->leftNode = temp->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
311 |
temp->rightNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
312 |
t = temp; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
313 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
314 |
if (t->leftNode == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
315 |
break; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
316 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
317 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
318 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
319 |
// Link right |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
320 |
right->leftNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
321 |
right = t; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
322 |
t = TO_NODE_POINTER(t->leftNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
323 |
} else if (key > t->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
324 |
if (t->rightNode == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
325 |
break; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
326 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
327 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
328 |
// Rotate left |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
329 |
if (key > TO_NODE_POINTER(t->rightNode)->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
330 |
temp = TO_NODE_POINTER(t->rightNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
331 |
t->rightNode = temp->leftNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
332 |
temp->leftNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
333 |
t = temp; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
334 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
335 |
if (t->rightNode == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
336 |
break; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
337 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
338 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
339 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
340 |
// Link left |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
341 |
left->rightNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
342 |
left = t; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
343 |
t = TO_NODE_POINTER(t->rightNode); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
344 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
345 |
break; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
346 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
347 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
348 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
349 |
// Re-create the node |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
350 |
left->rightNode = t->leftNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
351 |
right->leftNode = t->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
352 |
t->leftNode = n.rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
353 |
t->rightNode = n.leftNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
354 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
355 |
return (*root = TO_NODE_OFFSET(t)); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
356 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
357 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
358 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
359 |
* HbSplayTreeAllocator::deleteNode |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
360 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
361 |
* Delete a node from the tree. If 'splayed' is true, then the tree |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
362 |
* is assumed to be splayed with the correct key. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
363 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
364 |
void HbSplayTreeAllocator::deleteNode(quintptr *root, TreeNode *node, bool splayed) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
365 |
{ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
366 |
quintptr x = *root; |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
367 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
368 |
if (splayed) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
369 |
x = TO_NODE_OFFSET(node); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
370 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
371 |
x = splay(&x, node->key); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
372 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
373 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
374 |
if (TO_NODE_POINTER(x)->key == node->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
375 |
if (node->leftNode == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
376 |
x = node->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
377 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
378 |
x = splay(&node->leftNode, node->key); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
379 |
TO_NODE_POINTER(x)->rightNode = node->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
380 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
381 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
382 |
*root = x; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
383 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
384 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
385 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
386 |
* HbSplayTreeAllocator::insertNode |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
387 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
388 |
* Insert a new node into the tree. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
389 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
390 |
void HbSplayTreeAllocator::insertNode(quintptr *root, TreeNode *node) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
391 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
392 |
insertNode(root, node, TO_NODE_POINTER(splay(root, node->key))); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
393 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
394 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
395 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
396 |
* HbSplayTreeAllocator::insertNode |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
397 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
398 |
* Insert a new node into the tree. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
399 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
400 |
void HbSplayTreeAllocator::insertNode(quintptr *root, TreeNode *node, TreeNode *t) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
401 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
402 |
if (t == 0) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
403 |
node->leftNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
404 |
node->rightNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
405 |
} else if (node->key < t->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
406 |
node->leftNode = t->leftNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
407 |
node->rightNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
408 |
t->leftNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
409 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
410 |
node->rightNode = t->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
411 |
node->leftNode = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
412 |
t->rightNode = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
413 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
414 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
415 |
*root = TO_NODE_OFFSET(node); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
416 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
417 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
418 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
419 |
* HbSplayTreeAllocator::deleteLengthNode |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
420 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
421 |
* For length nodes, we must additionally check linked list for correct node. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
422 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
423 |
void HbSplayTreeAllocator::deleteLengthNode(quintptr *root, TreeNode *node, bool splayed) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
424 |
{ |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
425 |
MemoryBlock *block = reinterpret_cast<MemoryBlock*>(node); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
426 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
427 |
// If the node is not the first node in the linked list, |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
428 |
// simply de-link node from the linked list. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
429 |
if (block->prev) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
430 |
TO_BLOCK_POINTER(block->prev)->next = block->next; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
431 |
if (block->next) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
432 |
TO_BLOCK_POINTER (block->next)->prev = block->prev; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
433 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
434 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
435 |
// If the node is the first node of the linked list, then |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
436 |
// remove it from the tree and add the next node from the linked |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
437 |
// list to the tree. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
438 |
if (block->next) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
439 |
MemoryBlock *t = TO_BLOCK_POINTER(block->next); |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
440 |
quintptr x = *root; |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
441 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
442 |
if (splayed) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
443 |
x = TO_NODE_OFFSET(node); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
444 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
445 |
x = splay(&x, node->key); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
446 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
447 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
448 |
if (x && TO_NODE_POINTER(x)->key == node->key) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
449 |
t->lengthNode.leftNode = TO_NODE_POINTER(x)->leftNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
450 |
t->lengthNode.rightNode = TO_NODE_POINTER(x)->rightNode; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
451 |
t->prev = 0; |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
452 |
*root = static_cast<quintptr>(block->next); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
453 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
454 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
455 |
deleteNode(root, node, false); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
456 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
457 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
458 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
459 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
460 |
/** |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
461 |
* HbSplayTreeAllocator::insertLengthNode |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
462 |
* |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
463 |
* Many length nodes can have the same key. Therefore, we have to build |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
464 |
* linked list for the nodes with same key. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
465 |
*/ |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
466 |
void HbSplayTreeAllocator::insertLengthNode(quintptr *root, TreeNode *node) |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
467 |
{ |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
468 |
// Length TreeNode is the first entry in the MemoryBlock. Therefore, |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
469 |
// we can safely typecast TreeNode to a MemoryBlock. |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
470 |
MemoryBlock *t = TO_BLOCK_POINTER(splay(root, node->key)); |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
471 |
MemoryBlock *p = reinterpret_cast<MemoryBlock*>(node); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
472 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
473 |
if (!t || (t->lengthNode.key != node->key)) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
474 |
// Insert into the tree |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
475 |
p->prev = 0; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
476 |
p->next = 0; |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
477 |
insertNode(root, node, reinterpret_cast<TreeNode*>(t)); |
0
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
478 |
} else { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
479 |
// Link to the existing tree node |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
480 |
p->next = t->next; |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
481 |
p->prev = TO_NODE_OFFSET(t); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
482 |
t->next = TO_NODE_OFFSET(p); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
483 |
|
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
484 |
if (p->next) { |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
485 |
TO_BLOCK_POINTER(p->next)->prev = TO_NODE_OFFSET(p); |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
486 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
487 |
} |
16d8024aca5e
Revision: 201011
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
488 |
} |
1
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
489 |
|
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
490 |
/** |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
491 |
* HbSplayTreeAllocator::size |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
492 |
* |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
493 |
* Gets the total size as bytes used. |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
494 |
*/ |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
495 |
int HbSplayTreeAllocator::size() |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
496 |
{ |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
497 |
// splay the 'pointer' tree to obtain last pointer |
21
4633027730f5
Revision: 201031
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
6
diff
changeset
|
498 |
quintptr last_offset = static_cast<quintptr>(chunk->size()); |
6
c3690ec91ef8
Revision: 201023
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
3
diff
changeset
|
499 |
TreeNode *node = TO_NODE_POINTER(splay(&header->pointerNode, last_offset)); |
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
500 |
|
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
501 |
if (node) { |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
502 |
TreeNode *right = TO_NODE_POINTER(node->rightNode); |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
503 |
if (right) { |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
504 |
node = right; |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
505 |
} |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
506 |
MemoryBlock *block = reinterpret_cast<MemoryBlock*>(reinterpret_cast<char*>(node) |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
507 |
- sizeof(TreeNode)); |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
508 |
return TO_OFFSET(block) + sizeof(MemoryBlock) - 1; // not aligned, but actual last byte allocated.; |
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
509 |
} |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
510 |
return -1; |
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
511 |
} |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
512 |
|
1
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
513 |
int HbSplayTreeAllocator::freeBytes() |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
514 |
{ |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
515 |
return header->freeBytes; |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
516 |
} |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
517 |
|
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
518 |
int HbSplayTreeAllocator::allocatedBytes() |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
519 |
{ |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
520 |
return header->allocatedBytes; |
f7ac710697a9
Revision: 201015
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
0
diff
changeset
|
521 |
} |
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
522 |
|
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
523 |
#ifdef HB_THEME_SERVER_MEMORY_REPORT |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
524 |
void HbSplayTreeAllocator::writeReport(QTextStream &reportWriter) |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
525 |
{ |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
526 |
reportWriter << "***** (Main)HbSplayTreeAllocator report *****\n\n"; |
3
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
527 |
reportWriter << "Allocated memory (including memory allocated by multisegment allocator): " |
11d3954df52a
Revision: 201019
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
2
diff
changeset
|
528 |
<< header->allocatedBytes << " bytes\n"; |
2
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
529 |
reportWriter << "Free memory: " << header->freeBytes << " bytes\n"; |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
530 |
reportWriter << "Splaytree allocator is best fit allocator, so there is really no point to calculate fragmentation\n\n"; |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
531 |
} |
06ff229162e9
Revision: 201017
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
1
diff
changeset
|
532 |
#endif |