1/*
2 This file is part of the KDE libraries
3 SPDX-FileCopyrightText: 1999 Carsten Pfeiffer <pfeiffer@kde.org>
4
5 SPDX-License-Identifier: LGPL-2.0-or-later
6*/
7
8#ifndef KCOMPTREENODE_P_H
9#define KCOMPTREENODE_P_H
10
11#include "kcompletion_export.h"
12
13#include <QSharedPointer>
14#include <kzoneallocator_p.h>
15
16class KCompTreeNode;
17
18class KCOMPLETION_EXPORT KCompTreeChildren
19{
20public:
21 KCompTreeChildren()
22 : m_first(nullptr)
23 , m_last(nullptr)
24 , m_count(0)
25 {
26 }
27
28 KCompTreeNode *begin() const
29 {
30 return m_first;
31 }
32
33 KCompTreeNode *end() const
34 {
35 return m_last;
36 }
37
38 inline KCompTreeNode *at(uint index) const;
39 inline void append(KCompTreeNode *item);
40 inline void prepend(KCompTreeNode *item);
41 inline void insert(KCompTreeNode *after, KCompTreeNode *item);
42 inline KCompTreeNode *remove(KCompTreeNode *item);
43
44 uint count() const
45 {
46 return m_count;
47 }
48
49private:
50 KCompTreeNode *m_first;
51 KCompTreeNode *m_last;
52 uint m_count;
53};
54
55/*!
56 * A helper class for KCompletion. Implements a tree of QChar.
57 * Every node is a QChar and has a list of children, which are Nodes as well.
58 *
59 * QChar( 0x0 ) is used as the delimiter of a string; the last child of each
60 * inserted string is 0x0.
61 *
62 * The tree looks like this (containing the items "kde", "kde-ui",
63 * "kde-core" and "pfeiffer". Every item is delimited with QChar( 0x0 )
64 *
65 * some_root_node
66 * / \
67 * k p
68 * | |
69 * d f
70 * | |
71 * e e
72 * /| |
73 * 0x0 - i
74 * / \ |
75 * u c f
76 * | | |
77 * i o f
78 * | | |
79 * 0x0 r e
80 * | |
81 * e r
82 * | |
83 * 0x0 0x0
84 *
85 * \internal
86 */
87class KCOMPLETION_EXPORT KCompTreeNode : public QChar
88{
89public:
90 KCompTreeNode()
91 : QChar()
92 , m_next(nullptr)
93 , m_weight(0)
94 {
95 }
96
97 explicit KCompTreeNode(const QChar &ch, uint weight = 0)
98 : QChar(ch)
99 , m_next(nullptr)
100 , m_weight(weight)
101 {
102 }
103
104 ~KCompTreeNode()
105 {
106 // delete all children
107 KCompTreeNode *cur = m_children.begin();
108 while (cur) {
109 KCompTreeNode *next = cur->m_next;
110 delete m_children.remove(item: cur);
111 cur = next;
112 }
113 }
114
115 KCompTreeNode(const KCompTreeNode &) = delete;
116 KCompTreeNode &operator=(const KCompTreeNode &) = delete;
117
118 void *operator new(size_t s)
119 {
120 Q_ASSERT(m_alloc);
121 return m_alloc->allocate(size: s);
122 }
123
124 void operator delete(void *s)
125 {
126 Q_ASSERT(m_alloc);
127 m_alloc->deallocate(ptr: s);
128 }
129
130 // Returns a child of this node matching ch, if available.
131 // Otherwise, returns 0L
132 KCompTreeNode *find(const QChar &ch) const
133 {
134 KCompTreeNode *cur = m_children.begin();
135 while (cur && (*cur != ch)) {
136 cur = cur->m_next;
137 }
138 return cur;
139 }
140
141 // Adds a child-node "ch" to this node. If such a node is already existent,
142 // it will not be created. Returns the new/existing node.
143 inline KCompTreeNode *insert(const QChar &ch, bool sorted);
144
145 // Iteratively removes a string from the tree. The nicer recursive
146 // version apparently was a little memory hungry (see #56757)
147 inline void remove(const QString &str);
148
149 int childrenCount() const
150 {
151 return m_children.count();
152 }
153
154 void confirm()
155 {
156 m_weight++;
157 }
158
159 void confirm(uint w)
160 {
161 m_weight += w;
162 }
163
164 void decline()
165 {
166 m_weight--;
167 }
168
169 uint weight() const
170 {
171 return m_weight;
172 }
173
174 const KCompTreeChildren *children() const
175 {
176 return &m_children;
177 }
178
179 const KCompTreeNode *childAt(int index) const
180 {
181 return m_children.at(index);
182 }
183
184 const KCompTreeNode *firstChild() const
185 {
186 return m_children.begin();
187 }
188
189 const KCompTreeNode *lastChild() const
190 {
191 return m_children.end();
192 }
193
194 /* We want to handle a list of KCompTreeNodes on our own, to not
195 need to use QValueList<>. And to make it even faster we don't
196 use an accessor, but just a public member. */
197 KCompTreeNode *m_next;
198
199 /*!
200 * Custom allocator used for all KCompTreeNode instances
201 */
202 static QSharedPointer<KZoneAllocator> allocator()
203 {
204 return m_alloc;
205 }
206
207private:
208 uint m_weight;
209 KCompTreeChildren m_children;
210 static QSharedPointer<KZoneAllocator> m_alloc;
211};
212
213KCompTreeNode *KCompTreeNode::insert(const QChar &ch, bool sorted)
214{
215 KCompTreeNode *child = find(ch);
216 if (!child) {
217 child = new KCompTreeNode(ch);
218
219 // FIXME, first (slow) sorted insertion implementation
220 if (sorted) {
221 KCompTreeNode *prev = nullptr;
222 KCompTreeNode *cur = m_children.begin();
223 while (cur) {
224 if (ch > *cur) {
225 prev = cur;
226 cur = cur->m_next;
227 } else {
228 break;
229 }
230 }
231 if (prev) {
232 m_children.insert(after: prev, item: child);
233 } else {
234 m_children.prepend(item: child);
235 }
236 }
237
238 else {
239 m_children.append(item: child);
240 }
241 }
242
243 // implicit weighting: the more often an item is inserted, the higher
244 // priority it gets.
245 child->confirm();
246
247 return child;
248}
249
250void KCompTreeNode::remove(const QString &str)
251{
252 QString string = str;
253 string += QChar(0x0);
254
255 QList<KCompTreeNode *> deletables(string.length() + 1);
256
257 KCompTreeNode *child = nullptr;
258 KCompTreeNode *parent = this;
259 deletables.replace(i: 0, t: parent);
260
261 int i = 0;
262 for (; i < string.length(); i++) {
263 child = parent->find(ch: string.at(i));
264 if (child) {
265 deletables.replace(i: i + 1, t: child);
266 } else {
267 break;
268 }
269
270 parent = child;
271 }
272
273 for (; i >= 1; i--) {
274 parent = deletables.at(i: i - 1);
275 child = deletables.at(i);
276 if (child->m_children.count() == 0) {
277 delete parent->m_children.remove(item: child);
278 }
279 }
280}
281
282KCompTreeNode *KCompTreeChildren::at(uint index) const
283{
284 KCompTreeNode *cur = m_first;
285 while (index-- && cur) {
286 cur = cur->m_next;
287 }
288 return cur;
289}
290
291void KCompTreeChildren::append(KCompTreeNode *item)
292{
293 m_count++;
294 if (!m_last) {
295 m_last = item;
296 m_last->m_next = nullptr;
297 m_first = item;
298 return;
299 }
300 m_last->m_next = item;
301 item->m_next = nullptr;
302 m_last = item;
303}
304
305void KCompTreeChildren::prepend(KCompTreeNode *item)
306{
307 m_count++;
308 if (!m_last) {
309 m_last = item;
310 m_last->m_next = nullptr;
311 m_first = item;
312 return;
313 }
314 item->m_next = m_first;
315 m_first = item;
316}
317
318void KCompTreeChildren::insert(KCompTreeNode *after, KCompTreeNode *item)
319{
320 if (!after) {
321 append(item);
322 return;
323 }
324
325 m_count++;
326
327 item->m_next = after->m_next;
328 after->m_next = item;
329
330 if (after == m_last) {
331 m_last = item;
332 }
333}
334
335KCompTreeNode *KCompTreeChildren::remove(KCompTreeNode *item)
336{
337 if (!m_first || !item) {
338 return nullptr;
339 }
340 KCompTreeNode *cur = nullptr;
341
342 if (item == m_first) {
343 m_first = m_first->m_next;
344 } else {
345 cur = m_first;
346 while (cur && cur->m_next != item) {
347 cur = cur->m_next;
348 }
349 if (!cur) {
350 return nullptr;
351 }
352 cur->m_next = item->m_next;
353 }
354 if (item == m_last) {
355 m_last = cur;
356 }
357 m_count--;
358 return item;
359}
360
361#endif // KCOMPTREENODE_P_H
362

source code of kcompletion/src/kcomptreenode_p.h