Qt 4.8
qmap.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include "qmap.h"
43 
44 #include <stdlib.h>
45 
46 #ifdef QT_QMAP_DEBUG
47 # include <qstring.h>
48 # include <qvector.h>
49 #endif
50 
52 
54  &shared_null,
55  { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
56  Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true, false, 0
57 };
58 
60 {
61  return createData(0);
62 }
63 
65 {
66  QMapData *d = new QMapData;
67  Q_CHECK_PTR(d);
68  Node *e = reinterpret_cast<Node *>(d);
69  e->backward = e;
70  e->forward[0] = e;
71  d->ref = 1;
72  d->topLevel = 0;
73  d->size = 0;
74  d->randomBits = 0;
75  d->insertInOrder = false;
76  d->sharable = true;
77  d->strictAlignment = alignment > 8;
78  d->reserved = 0;
79  return d;
80 }
81 
83 {
84  Node *e = reinterpret_cast<Node *>(this);
85  Node *cur = e->forward[0];
86  Node *prev;
87  while (cur != e) {
88  prev = cur;
89  cur = cur->forward[0];
90  if (strictAlignment)
91  qFreeAligned(reinterpret_cast<char *>(prev) - offset);
92  else
93  qFree(reinterpret_cast<char *>(prev) - offset);
94  }
95  delete this;
96 }
97 
98 QMapData::Node *QMapData::node_create(Node *update[], int offset)
99 {
100  return node_create(update, offset, 0);
101 }
102 
117 QMapData::Node *QMapData::node_create(Node *update[], int offset, int alignment)
118 {
119  int level = 0;
120  uint mask = (1 << Sparseness) - 1;
121 
122  while ((randomBits & mask) == mask && level < LastLevel) {
123  ++level;
124  mask <<= Sparseness;
125  }
126 
127  if (level > topLevel) {
128  Node *e = reinterpret_cast<Node *>(this);
129  level = ++topLevel;
130  e->forward[level] = e;
131  update[level] = e;
132  }
133 
134  ++randomBits;
135  if (level == 3 && !insertInOrder)
136  randomBits = qrand();
137 
138  void *concreteNode = strictAlignment ?
139  qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) :
140  qMalloc(offset + sizeof(Node) + level * sizeof(Node *));
141  Q_CHECK_PTR(concreteNode);
142 
143  Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);
144 
145  abstractNode->backward = update[0];
146  update[0]->forward[0]->backward = abstractNode;
147 
148  for (int i = level; i >= 0; i--) {
149  abstractNode->forward[i] = update[i]->forward[i];
150  update[i]->forward[i] = abstractNode;
151  update[i] = abstractNode;
152  }
153  ++size;
154  return abstractNode;
155 }
156 
157 void QMapData::node_delete(Node *update[], int offset, Node *node)
158 {
159  node->forward[0]->backward = node->backward;
160 
161  for (int i = 0; i <= topLevel; ++i) {
162  if (update[i]->forward[i] != node)
163  break;
164  update[i]->forward[i] = node->forward[i];
165  }
166  --size;
167  if (strictAlignment)
168  qFreeAligned(reinterpret_cast<char *>(node) - offset);
169  else
170  qFree(reinterpret_cast<char *>(node) - offset);
171 }
172 
173 #ifdef QT_QMAP_DEBUG
174 
175 uint QMapData::adjust_ptr(Node *node)
176 {
177  if (node == reinterpret_cast<Node *>(this)) {
178  return (uint)0xDEADBEEF;
179  } else {
180  return (uint)node;
181  }
182 }
183 
184 void QMapData::dump()
185 {
186  qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", int(ref), size, randomBits);
187 
188  QString preOutput;
189  QVector<QString> output(topLevel + 1);
190  Node *e = reinterpret_cast<Node *>(this);
191 
192  QString str;
193  str.sprintf(" %.8x", adjust_ptr(reinterpret_cast<Node *>(this)));
194  preOutput += str;
195 
196  Node *update[LastLevel + 1];
197  for (int i = 0; i <= topLevel; ++i) {
198  str.sprintf("%d: [%.8x] -", i, adjust_ptr(reinterpret_cast<Node *>(forward[i])));
199  output[i] += str;
200  update[i] = reinterpret_cast<Node *>(forward[i]);
201  }
202 
203  Node *node = reinterpret_cast<Node *>(forward[0]);
204  while (node != e) {
205  int level = 0;
206  while (level < topLevel && update[level + 1] == node)
207  ++level;
208 
209  str.sprintf(" %.8x", adjust_ptr(node));
210  preOutput += str;
211 
212  for (int i = 0; i <= level; ++i) {
213  str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i]));
214  output[i] += str;
215  update[i] = node->forward[i];
216  }
217  for (int j = level + 1; j <= topLevel; ++j)
218  output[j] += QLatin1String("---------------");
219  node = node->forward[0];
220  }
221 
222  qDebug("%s", preOutput.ascii());
223  for (int i = 0; i <= topLevel; ++i)
224  qDebug("%s", output[i].ascii());
225 }
226 #endif
227 
double d
Definition: qnumeric_p.h:62
void node_delete(Node *update[], int offset, Node *node)
Definition: qmap.cpp:157
QString & sprintf(const char *format,...)
Safely builds a formatted string from the format string cformat and an arbitrary list of arguments...
Definition: qstring.cpp:5567
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
Q_CORE_EXPORT void * qMallocAligned(size_t size, size_t alignment)
Definition: qmalloc.cpp:68
Q_CORE_EXPORT void qFree(void *ptr)
Definition: qmalloc.cpp:58
Node * node_create(Node *update[], int offset)
Definition: qmap.cpp:98
QLatin1String(DBUS_INTERFACE_DBUS))) Q_GLOBAL_STATIC_WITH_ARGS(QString
Q_CORE_EXPORT void * qMalloc(size_t size)
Definition: qmalloc.cpp:53
void continueFreeData(int offset)
Definition: qmap.cpp:82
int size
Definition: qmap.h:73
The QString class provides a Unicode character string.
Definition: qstring.h:83
Q_CORE_EXPORT int qrand()
uint randomBits
Definition: qmap.h:74
#define Q_BASIC_ATOMIC_INITIALIZER(a)
Definition: qbasicatomic.h:218
QBasicAtomicInt ref
Definition: qmap.h:71
int topLevel
Definition: qmap.h:72
Q_CORE_EXPORT void qDebug(const char *,...)
static QMapData * createData()
Definition: qmap.cpp:59
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
uint strictAlignment
Definition: qmap.h:77
uint sharable
Definition: qmap.h:76
QMapData * forward[QMapData::LastLevel+1]
Definition: qmap.h:70
unsigned int uint
Definition: qglobal.h:996
uint insertInOrder
Definition: qmap.h:75
Node * forward[1]
Definition: qmap.h:65
#define Q_CHECK_PTR(p)
Definition: qglobal.h:1853
Definition: qmap.h:61
static QString dump(const QByteArray &)
Node * backward
Definition: qmap.h:64
uint reserved
Definition: qmap.h:78
Q_CORE_EXPORT void qFreeAligned(void *ptr)
Definition: qmalloc.cpp:118
static QMapData shared_null
Definition: qmap.h:91