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 * @author Carsten Pfeiffer <pfeiffer@kde.org>
86 * @internal
87 */
88class KCOMPLETION_EXPORT KCompTreeNode : public QChar
89{
90public:
91 KCompTreeNode()
92 : QChar()
93 , m_next(nullptr)
94 , m_weight(0)
95 {
96 }
97
98 explicit KCompTreeNode(const QChar &ch, uint weight = 0)
99 : QChar(ch)
100 , m_next(nullptr)
101 , m_weight(weight)
102 {
103 }
104
105 ~KCompTreeNode()
106 {
107 // delete all children
108 KCompTreeNode *cur = m_children.begin();
109 while (cur) {
110 KCompTreeNode *next = cur->m_next;
111 delete m_children.remove(item: cur);
112 cur = next;
113 }
114 }
115
116 KCompTreeNode(const KCompTreeNode &) = delete;
117 KCompTreeNode &operator=(const KCompTreeNode &) = delete;
118
119 void *operator new(size_t s)
120 {
121 Q_ASSERT(m_alloc);
122 return m_alloc->allocate(size: s);
123 }
124
125 void operator delete(void *s)
126 {
127 Q_ASSERT(m_alloc);
128 m_alloc->deallocate(ptr: s);
129 }
130
131 // Returns a child of this node matching ch, if available.
132 // Otherwise, returns 0L
133 KCompTreeNode *find(const QChar &ch) const
134 {
135 KCompTreeNode *cur = m_children.begin();
136 while (cur && (*cur != ch)) {
137 cur = cur->m_next;
138 }
139 return cur;
140 }
141
142 // Adds a child-node "ch" to this node. If such a node is already existent,
143 // it will not be created. Returns the new/existing node.
144 inline KCompTreeNode *insert(const QChar &ch, bool sorted);
145
146 // Iteratively removes a string from the tree. The nicer recursive
147 // version apparently was a little memory hungry (see #56757)
148 inline void remove(const QString &str);
149
150 int childrenCount() const
151 {
152 return m_children.count();
153 }
154
155 void confirm()
156 {
157 m_weight++;
158 }
159
160 void confirm(uint w)
161 {
162 m_weight += w;
163 }
164
165 void decline()
166 {
167 m_weight--;
168 }
169
170 uint weight() const
171 {
172 return m_weight;
173 }
174
175 const KCompTreeChildren *children() const
176 {
177 return &m_children;
178 }
179
180 const KCompTreeNode *childAt(int index) const
181 {
182 return m_children.at(index);
183 }
184
185 const KCompTreeNode *firstChild() const
186 {
187 return m_children.begin();
188 }
189
190 const KCompTreeNode *lastChild() const
191 {
192 return m_children.end();
193 }
194
195 /* We want to handle a list of KCompTreeNodes on our own, to not
196 need to use QValueList<>. And to make it even faster we don't
197 use an accessor, but just a public member. */
198 KCompTreeNode *m_next;
199
200 /**
201 * Custom allocator used for all KCompTreeNode instances
202 */
203 static QSharedPointer<KZoneAllocator> allocator()
204 {
205 return m_alloc;
206 }
207
208private:
209 uint m_weight;
210 KCompTreeChildren m_children;
211 static QSharedPointer<KZoneAllocator> m_alloc;
212};
213
214KCompTreeNode *KCompTreeNode::insert(const QChar &ch, bool sorted)
215{
216 KCompTreeNode *child = find(ch);
217 if (!child) {
218 child = new KCompTreeNode(ch);
219
220 // FIXME, first (slow) sorted insertion implementation
221 if (sorted) {
222 KCompTreeNode *prev = nullptr;
223 KCompTreeNode *cur = m_children.begin();
224 while (cur) {
225 if (ch > *cur) {
226 prev = cur;
227 cur = cur->m_next;
228 } else {
229 break;
230 }
231 }
232 if (prev) {
233 m_children.insert(after: prev, item: child);
234 } else {
235 m_children.prepend(item: child);
236 }
237 }
238
239 else {
240 m_children.append(item: child);
241 }
242 }
243
244 // implicit weighting: the more often an item is inserted, the higher
245 // priority it gets.
246 child->confirm();
247
248 return child;
249}
250
251void KCompTreeNode::remove(const QString &str)
252{
253 QString string = str;
254 string += QChar(0x0);
255
256 QList<KCompTreeNode *> deletables(string.length() + 1);
257
258 KCompTreeNode *child = nullptr;
259 KCompTreeNode *parent = this;
260 deletables.replace(i: 0, t: parent);
261
262 int i = 0;
263 for (; i < string.length(); i++) {
264 child = parent->find(ch: string.at(i));
265 if (child) {
266 deletables.replace(i: i + 1, t: child);
267 } else {
268 break;
269 }
270
271 parent = child;
272 }
273
274 for (; i >= 1; i--) {
275 parent = deletables.at(i: i - 1);
276 child = deletables.at(i);
277 if (child->m_children.count() == 0) {
278 delete parent->m_children.remove(item: child);
279 }
280 }
281}
282
283KCompTreeNode *KCompTreeChildren::at(uint index) const
284{
285 KCompTreeNode *cur = m_first;
286 while (index-- && cur) {
287 cur = cur->m_next;
288 }
289 return cur;
290}
291
292void KCompTreeChildren::append(KCompTreeNode *item)
293{
294 m_count++;
295 if (!m_last) {
296 m_last = item;
297 m_last->m_next = nullptr;
298 m_first = item;
299 return;
300 }
301 m_last->m_next = item;
302 item->m_next = nullptr;
303 m_last = item;
304}
305
306void KCompTreeChildren::prepend(KCompTreeNode *item)
307{
308 m_count++;
309 if (!m_last) {
310 m_last = item;
311 m_last->m_next = nullptr;
312 m_first = item;
313 return;
314 }
315 item->m_next = m_first;
316 m_first = item;
317}
318
319void KCompTreeChildren::insert(KCompTreeNode *after, KCompTreeNode *item)
320{
321 if (!after) {
322 append(item);
323 return;
324 }
325
326 m_count++;
327
328 item->m_next = after->m_next;
329 after->m_next = item;
330
331 if (after == m_last) {
332 m_last = item;
333 }
334}
335
336KCompTreeNode *KCompTreeChildren::remove(KCompTreeNode *item)
337{
338 if (!m_first || !item) {
339 return nullptr;
340 }
341 KCompTreeNode *cur = nullptr;
342
343 if (item == m_first) {
344 m_first = m_first->m_next;
345 } else {
346 cur = m_first;
347 while (cur && cur->m_next != item) {
348 cur = cur->m_next;
349 }
350 if (!cur) {
351 return nullptr;
352 }
353 cur->m_next = item->m_next;
354 }
355 if (item == m_last) {
356 m_last = cur;
357 }
358 m_count--;
359 return item;
360}
361
362#endif // KCOMPTREENODE_P_H
363

source code of kcompletion/src/kcomptreenode_p.h