| changeset 3 | 41300fa6a67c |
| parent 0 | 1918ee327afb |
| child 4 | 3b1da2848fc7 |
| 2:56cd8111b7f7 | 3:41300fa6a67c |
|---|---|
51 QT_BEGIN_NAMESPACE |
51 QT_BEGIN_NAMESPACE |
52 |
52 |
53 QMapData QMapData::shared_null = { |
53 QMapData QMapData::shared_null = { |
54 &shared_null, |
54 &shared_null, |
55 { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, |
55 { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, |
56 Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true |
56 Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true, false, 0 |
57 }; |
57 }; |
58 |
58 |
59 QMapData *QMapData::createData() |
59 QMapData *QMapData::createData() |
60 { |
|
61 return createData(0); |
|
62 } |
|
63 |
|
64 QMapData *QMapData::createData(int alignment) |
|
60 { |
65 { |
61 QMapData *d = new QMapData; |
66 QMapData *d = new QMapData; |
62 Q_CHECK_PTR(d); |
67 Q_CHECK_PTR(d); |
63 Node *e = reinterpret_cast<Node *>(d); |
68 Node *e = reinterpret_cast<Node *>(d); |
64 e->backward = e; |
69 e->backward = e; |
67 d->topLevel = 0; |
72 d->topLevel = 0; |
68 d->size = 0; |
73 d->size = 0; |
69 d->randomBits = 0; |
74 d->randomBits = 0; |
70 d->insertInOrder = false; |
75 d->insertInOrder = false; |
71 d->sharable = true; |
76 d->sharable = true; |
77 d->strictAlignment = alignment > 8; |
|
78 d->reserved = 0; |
|
72 return d; |
79 return d; |
73 } |
80 } |
74 |
81 |
75 void QMapData::continueFreeData(int offset) |
82 void QMapData::continueFreeData(int offset) |
76 { |
83 { |
78 Node *cur = e->forward[0]; |
85 Node *cur = e->forward[0]; |
79 Node *prev; |
86 Node *prev; |
80 while (cur != e) { |
87 while (cur != e) { |
81 prev = cur; |
88 prev = cur; |
82 cur = cur->forward[0]; |
89 cur = cur->forward[0]; |
83 qFree(reinterpret_cast<char *>(prev) - offset); |
90 if (strictAlignment) |
91 qFreeAligned(reinterpret_cast<char *>(prev) - offset); |
|
92 else |
|
93 qFree(reinterpret_cast<char *>(prev) - offset); |
|
84 } |
94 } |
85 delete this; |
95 delete this; |
96 } |
|
97 |
|
98 QMapData::Node *QMapData::node_create(Node *update[], int offset) |
|
99 { |
|
100 return node_create(update, offset, 0); |
|
86 } |
101 } |
87 |
102 |
88 /*! |
103 /*! |
89 Creates a new node inside the data structure. |
104 Creates a new node inside the data structure. |
90 |
105 |
92 should be inserted. Because of the strange skip list data structure there |
107 should be inserted. Because of the strange skip list data structure there |
93 could be several pointers to this node on different levels. |
108 could be several pointers to this node on different levels. |
94 \a offset is an amount of bytes that needs to reserved just before the |
109 \a offset is an amount of bytes that needs to reserved just before the |
95 QMapData::Node structure. |
110 QMapData::Node structure. |
96 |
111 |
112 \a alignment dictates the alignment for the data. |
|
113 |
|
97 \internal |
114 \internal |
98 \since 4.6 |
115 \since 4.6 |
99 */ |
116 */ |
100 QMapData::Node *QMapData::node_create(Node *update[], int offset) |
117 QMapData::Node *QMapData::node_create(Node *update[], int offset, int alignment) |
101 { |
118 { |
102 int level = 0; |
119 int level = 0; |
103 uint mask = (1 << Sparseness) - 1; |
120 uint mask = (1 << Sparseness) - 1; |
104 |
121 |
105 while ((randomBits & mask) == mask && level < LastLevel) { |
122 while ((randomBits & mask) == mask && level < LastLevel) { |
116 |
133 |
117 ++randomBits; |
134 ++randomBits; |
118 if (level == 3 && !insertInOrder) |
135 if (level == 3 && !insertInOrder) |
119 randomBits = qrand(); |
136 randomBits = qrand(); |
120 |
137 |
121 void *concreteNode = qMalloc(offset + sizeof(Node) + level * sizeof(Node *)); |
138 void *concreteNode = strictAlignment ? |
139 qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) : |
|
140 qMalloc(offset + sizeof(Node) + level * sizeof(Node *)); |
|
122 Q_CHECK_PTR(concreteNode); |
141 Q_CHECK_PTR(concreteNode); |
123 |
142 |
124 Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset); |
143 Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset); |
125 |
144 |
126 abstractNode->backward = update[0]; |
145 abstractNode->backward = update[0]; |
143 if (update[i]->forward[i] != node) |
162 if (update[i]->forward[i] != node) |
144 break; |
163 break; |
145 update[i]->forward[i] = node->forward[i]; |
164 update[i]->forward[i] = node->forward[i]; |
146 } |
165 } |
147 --size; |
166 --size; |
148 qFree(reinterpret_cast<char *>(node) - offset); |
167 if (strictAlignment) |
168 qFreeAligned(reinterpret_cast<char *>(node) - offset); |
|
169 else |
|
170 qFree(reinterpret_cast<char *>(node) - offset); |
|
149 } |
171 } |
150 |
172 |
151 #ifdef QT_QMAP_DEBUG |
173 #ifdef QT_QMAP_DEBUG |
152 |
174 |
153 uint QMapData::adjust_ptr(Node *node) |
175 uint QMapData::adjust_ptr(Node *node) |