Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL
4 : * Purpose: CPLStringList implementation.
5 : * Author: Frank Warmerdam, warmerdam@pobox.com
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2011, Frank Warmerdam <warmerdam@pobox.com>
9 : * Copyright (c) 2011, Even Rouault <even dot rouault at spatialys.com>
10 : *
11 : * SPDX-License-Identifier: MIT
12 : ****************************************************************************/
13 :
14 : #include "cpl_port.h"
15 : #include "cpl_string.h"
16 :
17 : #include <cstddef>
18 : #include <cstdio>
19 : #include <cstdlib>
20 : #include <cstring>
21 :
22 : #include <algorithm>
23 : #include <limits>
24 : #include <string>
25 :
26 : #include "cpl_conv.h"
27 : #include "cpl_error.h"
28 :
29 : static int CPLCompareKeyValueString(const char *pszKVa, const char *pszKVb);
30 :
31 : /************************************************************************/
32 : /* CPLStringList() */
33 : /************************************************************************/
34 :
35 : CPLStringList::CPLStringList() = default;
36 :
37 : /************************************************************************/
38 : /* CPLStringList() */
39 : /************************************************************************/
40 :
41 : /**
42 : * CPLStringList constructor.
43 : *
44 : * @param papszListIn the NULL terminated list of strings to consume.
45 : * @param bTakeOwnership TRUE if the CPLStringList should take ownership
46 : * of the list of strings which implies responsibility to free them.
47 : */
48 :
49 2030380 : CPLStringList::CPLStringList(char **papszListIn, int bTakeOwnership)
50 2030380 : : CPLStringList()
51 :
52 : {
53 2023780 : Assign(papszListIn, bTakeOwnership);
54 2012070 : }
55 :
56 : /************************************************************************/
57 : /* CPLStringList() */
58 : /************************************************************************/
59 :
60 : /**
61 : * CPLStringList constructor.
62 : *
63 : * The input list is copied.
64 : *
65 : * @param papszListIn the NULL terminated list of strings to ingest.
66 : */
67 :
68 14912 : CPLStringList::CPLStringList(CSLConstList papszListIn) : CPLStringList()
69 :
70 : {
71 14899 : Assign(CSLDuplicate(papszListIn));
72 14903 : }
73 :
74 : /************************************************************************/
75 : /* CPLStringList() */
76 : /************************************************************************/
77 :
78 : /**
79 : * CPLStringList constructor.
80 : *
81 : * The input list is copied.
82 : *
83 : * @param aosList input list.
84 : *
85 : * @since GDAL 3.9
86 : */
87 4109 : CPLStringList::CPLStringList(const std::vector<std::string> &aosList)
88 : {
89 4109 : if (!aosList.empty())
90 : {
91 627 : bOwnList = true;
92 627 : papszList = static_cast<char **>(
93 627 : VSI_CALLOC_VERBOSE(aosList.size() + 1, sizeof(char *)));
94 627 : nCount = static_cast<int>(aosList.size());
95 3922 : for (int i = 0; i < nCount; ++i)
96 : {
97 3295 : papszList[i] = VSI_STRDUP_VERBOSE(aosList[i].c_str());
98 : }
99 : }
100 4109 : }
101 :
102 : /************************************************************************/
103 : /* CPLStringList() */
104 : /************************************************************************/
105 :
106 : /**
107 : * CPLStringList constructor.
108 : *
109 : * The input list is copied.
110 : *
111 : * @param oInitList input list.
112 : *
113 : * @since GDAL 3.9
114 : */
115 3 : CPLStringList::CPLStringList(std::initializer_list<const char *> oInitList)
116 : {
117 9 : for (const char *pszStr : oInitList)
118 : {
119 6 : AddString(pszStr);
120 : }
121 3 : }
122 :
123 : /************************************************************************/
124 : /* CPLStringList() */
125 : /************************************************************************/
126 :
127 : //! Copy constructor
128 33485 : CPLStringList::CPLStringList(const CPLStringList &oOther) : CPLStringList()
129 :
130 : {
131 33485 : operator=(oOther);
132 33485 : }
133 :
134 : /************************************************************************/
135 : /* CPLStringList() */
136 : /************************************************************************/
137 :
138 : //! Move constructor
139 3622600 : CPLStringList::CPLStringList(CPLStringList &&oOther) : CPLStringList()
140 :
141 : {
142 3614630 : operator=(std::move(oOther));
143 3621940 : }
144 :
145 : /************************************************************************/
146 : /* BoundToConstList() */
147 : /************************************************************************/
148 :
149 : /**
150 : * Return a CPLStringList that wraps the passed list.
151 : *
152 : * The input list is *NOT* copied and must be kept alive while the
153 : * return CPLStringList is used.
154 : *
155 : * @param papszListIn a NULL terminated list of strings to wrap into the CPLStringList
156 : * @since GDAL 3.9
157 : */
158 :
159 : /* static */
160 94 : const CPLStringList CPLStringList::BoundToConstList(CSLConstList papszListIn)
161 : {
162 : return CPLStringList(const_cast<char **>(papszListIn),
163 94 : /* bTakeOwnership= */ false);
164 : }
165 :
166 : /************************************************************************/
167 : /* operator=() */
168 : /************************************************************************/
169 :
170 287563 : CPLStringList &CPLStringList::operator=(const CPLStringList &oOther)
171 : {
172 287563 : if (this != &oOther)
173 : {
174 287562 : char **l_papszList = CSLDuplicate(oOther.papszList);
175 287562 : if (l_papszList)
176 : {
177 12336 : Assign(l_papszList, TRUE);
178 12336 : nAllocation = oOther.nCount > 0 ? oOther.nCount + 1 : 0;
179 12336 : nCount = oOther.nCount;
180 12336 : bIsSorted = oOther.bIsSorted;
181 : }
182 : }
183 :
184 287563 : return *this;
185 : }
186 :
187 : /************************************************************************/
188 : /* operator=() */
189 : /************************************************************************/
190 :
191 3623030 : CPLStringList &CPLStringList::operator=(CPLStringList &&oOther)
192 : {
193 3623030 : if (this != &oOther)
194 : {
195 3625720 : Clear();
196 3629210 : papszList = oOther.papszList;
197 3629210 : oOther.papszList = nullptr;
198 3629210 : nCount = oOther.nCount;
199 3629210 : oOther.nCount = 0;
200 3629210 : nAllocation = oOther.nAllocation;
201 3629210 : oOther.nAllocation = 0;
202 3629210 : bOwnList = oOther.bOwnList;
203 3629210 : oOther.bOwnList = false;
204 3629210 : bIsSorted = oOther.bIsSorted;
205 3629210 : oOther.bIsSorted = true;
206 : }
207 :
208 3626520 : return *this;
209 : }
210 :
211 : /************************************************************************/
212 : /* operator=() */
213 : /************************************************************************/
214 :
215 103221 : CPLStringList &CPLStringList::operator=(CSLConstList papszListIn)
216 : {
217 103221 : if (papszListIn != papszList)
218 : {
219 16521 : Assign(CSLDuplicate(papszListIn));
220 16521 : bIsSorted = false;
221 : }
222 :
223 103221 : return *this;
224 : }
225 :
226 : /************************************************************************/
227 : /* ~CPLStringList() */
228 : /************************************************************************/
229 :
230 25286200 : CPLStringList::~CPLStringList()
231 :
232 : {
233 12648700 : Clear();
234 12637500 : }
235 :
236 : /************************************************************************/
237 : /* Clear() */
238 : /************************************************************************/
239 :
240 : /**
241 : * Clear the string list.
242 : */
243 18852200 : CPLStringList &CPLStringList::Clear()
244 :
245 : {
246 18852200 : if (bOwnList)
247 : {
248 3429890 : CSLDestroy(papszList);
249 3428060 : papszList = nullptr;
250 :
251 3428060 : bOwnList = FALSE;
252 3428060 : nAllocation = 0;
253 3428060 : nCount = 0;
254 : }
255 :
256 18850300 : return *this;
257 : }
258 :
259 : /************************************************************************/
260 : /* Assign() */
261 : /************************************************************************/
262 :
263 : /**
264 : * Assign a list of strings.
265 : *
266 : *
267 : * @param papszListIn the NULL terminated list of strings to consume.
268 : * @param bTakeOwnership TRUE if the CPLStringList should take ownership
269 : * of the list of strings which implies responsibility to free them.
270 : *
271 : * @return a reference to the CPLStringList on which it was invoked.
272 : */
273 :
274 2465170 : CPLStringList &CPLStringList::Assign(char **papszListIn, int bTakeOwnership)
275 :
276 : {
277 2465170 : Clear();
278 :
279 2461620 : papszList = papszListIn;
280 2461620 : bOwnList = CPL_TO_BOOL(bTakeOwnership);
281 :
282 2451160 : if (papszList == nullptr || *papszList == nullptr)
283 1868710 : nCount = 0;
284 : else
285 582455 : nCount = -1; // unknown
286 :
287 2451160 : nAllocation = 0;
288 2451160 : bIsSorted = FALSE;
289 :
290 2451160 : return *this;
291 : }
292 :
293 : /************************************************************************/
294 : /* Count() */
295 : /************************************************************************/
296 :
297 : /**
298 : * @return count of strings in the list, zero if empty.
299 : */
300 :
301 3532060 : int CPLStringList::Count() const
302 :
303 : {
304 3532060 : if (nCount == -1)
305 : {
306 551903 : if (papszList == nullptr)
307 : {
308 0 : nCount = 0;
309 0 : nAllocation = 0;
310 : }
311 : else
312 : {
313 551903 : nCount = CSLCount(papszList);
314 551903 : nAllocation = std::max(nCount + 1, nAllocation);
315 : }
316 : }
317 :
318 3532040 : return nCount;
319 : }
320 :
321 : /************************************************************************/
322 : /* MakeOurOwnCopy() */
323 : /* */
324 : /* If we don't own the list, a copy is made which we own. */
325 : /* Necessary if we are going to modify the list. */
326 : /************************************************************************/
327 :
328 8308550 : bool CPLStringList::MakeOurOwnCopy()
329 :
330 : {
331 8308550 : if (bOwnList)
332 4670410 : return true;
333 :
334 3638140 : if (papszList == nullptr)
335 3637920 : return true;
336 :
337 211 : Count();
338 90 : char **papszListNew = CSLDuplicate(papszList);
339 90 : if (papszListNew == nullptr)
340 : {
341 0 : return false;
342 : }
343 90 : papszList = papszListNew;
344 90 : bOwnList = true;
345 90 : nAllocation = nCount + 1;
346 90 : return true;
347 : }
348 :
349 : /************************************************************************/
350 : /* EnsureAllocation() */
351 : /* */
352 : /* Ensure we have enough room allocated for at least the */
353 : /* requested number of strings (so nAllocation will be at least */
354 : /* one more than the target) */
355 : /************************************************************************/
356 :
357 11694900 : bool CPLStringList::EnsureAllocation(int nMaxList)
358 :
359 : {
360 11694900 : if (!bOwnList)
361 : {
362 2871430 : if (!MakeOurOwnCopy())
363 0 : return false;
364 : }
365 :
366 11694800 : if (papszList == nullptr || nAllocation <= nMaxList)
367 : {
368 : // we need to be able to store nMaxList+1 as an int,
369 : // and allocate (nMaxList+1) * sizeof(char*) bytes
370 5930110 : if (nMaxList < 0 || nMaxList > std::numeric_limits<int>::max() - 1 ||
371 2965110 : static_cast<size_t>(nMaxList) >
372 2965110 : std::numeric_limits<size_t>::max() / sizeof(char *) - 1)
373 : {
374 0 : return false;
375 : }
376 2965030 : int nNewAllocation = nMaxList + 1;
377 2965030 : if (nNewAllocation <= (std::numeric_limits<int>::max() - 20) / 2 /
378 : static_cast<int>(sizeof(char *)))
379 2965120 : nNewAllocation = std::max(nNewAllocation * 2 + 20, nMaxList + 1);
380 2965060 : if (papszList == nullptr)
381 : {
382 2874410 : papszList = static_cast<char **>(
383 2874370 : VSI_CALLOC_VERBOSE(nNewAllocation, sizeof(char *)));
384 2874410 : bOwnList = true;
385 2874410 : nCount = 0;
386 2874410 : if (papszList == nullptr)
387 0 : return false;
388 : }
389 : else
390 : {
391 90691 : char **papszListNew = static_cast<char **>(VSI_REALLOC_VERBOSE(
392 : papszList, nNewAllocation * sizeof(char *)));
393 90691 : if (papszListNew == nullptr)
394 0 : return false;
395 90691 : papszList = papszListNew;
396 : }
397 2965100 : nAllocation = nNewAllocation;
398 : }
399 11694900 : return true;
400 : }
401 :
402 : /************************************************************************/
403 : /* AddStringDirectly() */
404 : /************************************************************************/
405 :
406 : /**
407 : * Add a string to the list.
408 : *
409 : * This method is similar to AddString(), but ownership of the
410 : * pszNewString is transferred to the CPLStringList class.
411 : *
412 : * @param pszNewString the string to add to the list.
413 : */
414 :
415 11687400 : CPLStringList &CPLStringList::AddStringDirectly(char *pszNewString)
416 :
417 : {
418 11687400 : if (nCount == -1)
419 663 : Count();
420 :
421 11687400 : if (!EnsureAllocation(nCount + 1))
422 : {
423 0 : VSIFree(pszNewString);
424 0 : return *this;
425 : }
426 :
427 11687500 : papszList[nCount++] = pszNewString;
428 11687500 : papszList[nCount] = nullptr;
429 :
430 11687500 : bIsSorted = false;
431 :
432 11687500 : return *this;
433 : }
434 :
435 : /************************************************************************/
436 : /* AddString() */
437 : /************************************************************************/
438 :
439 : /**
440 : * Add a string to the list.
441 : *
442 : * A copy of the passed in string is made and inserted in the list.
443 : *
444 : * @param pszNewString the string to add to the list.
445 : */
446 :
447 6431290 : CPLStringList &CPLStringList::AddString(const char *pszNewString)
448 :
449 : {
450 6431290 : char *pszDupString = VSI_STRDUP_VERBOSE(pszNewString);
451 6431280 : if (pszDupString == nullptr)
452 0 : return *this;
453 6431280 : return AddStringDirectly(pszDupString);
454 : }
455 :
456 : /************************************************************************/
457 : /* AddString() */
458 : /************************************************************************/
459 : /**
460 : * Add a string to the list.
461 : *
462 : * A copy of the passed in string is made and inserted in the list.
463 : *
464 : * @param newString the string to add to the list.
465 : * @return a reference to the CPLStringList on which it was invoked.
466 : */
467 :
468 26201 : CPLStringList &CPLStringList::AddString(const std::string &newString)
469 : {
470 26201 : return AddString(newString.c_str());
471 : }
472 :
473 : /************************************************************************/
474 : /* AddNameValue() */
475 : /************************************************************************/
476 :
477 : /**
478 : * Add a name=value entry to the list.
479 : *
480 : * A key=value string is prepared and appended to the list. There is no
481 : * check for other values for the same key in the list.
482 : *
483 : * @param pszKey the key name to add.
484 : * @param pszValue the key value to add.
485 : */
486 :
487 5366100 : CPLStringList &CPLStringList::AddNameValue(const char *pszKey,
488 : const char *pszValue)
489 :
490 : {
491 5366100 : if (pszKey == nullptr || pszValue == nullptr)
492 144224 : return *this;
493 :
494 5221870 : if (!MakeOurOwnCopy())
495 0 : return *this;
496 :
497 : /* -------------------------------------------------------------------- */
498 : /* Format the line. */
499 : /* -------------------------------------------------------------------- */
500 10443900 : if (strlen(pszKey) >
501 10443800 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
502 5221900 : strlen(pszKey) + strlen(pszValue) >
503 5221900 : std::numeric_limits<size_t>::max() - 2)
504 : {
505 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
506 : "Too big strings in AddNameValue()");
507 0 : return *this;
508 : }
509 5221960 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
510 5221960 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
511 5221960 : if (pszLine == nullptr)
512 0 : return *this;
513 5221960 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
514 :
515 : /* -------------------------------------------------------------------- */
516 : /* If we don't need to keep the sort order things are pretty */
517 : /* straight forward. */
518 : /* -------------------------------------------------------------------- */
519 5221960 : if (!IsSorted())
520 5214880 : return AddStringDirectly(pszLine);
521 :
522 : /* -------------------------------------------------------------------- */
523 : /* Find the proper insertion point. */
524 : /* -------------------------------------------------------------------- */
525 7043 : CPLAssert(IsSorted());
526 7006 : const int iKey = FindSortedInsertionPoint(pszLine);
527 7006 : InsertStringDirectly(iKey, pszLine);
528 7006 : bIsSorted = true; // We have actually preserved sort order.
529 :
530 7006 : return *this;
531 : }
532 :
533 : /************************************************************************/
534 : /* SetNameValue() */
535 : /************************************************************************/
536 :
537 : /**
538 : * Set name=value entry in the list.
539 : *
540 : * Similar to AddNameValue(), except if there is already a value for
541 : * the key in the list it is replaced instead of adding a new entry to
542 : * the list. If pszValue is NULL any existing key entry is removed.
543 : *
544 : * @param pszKey the key name to add.
545 : * @param pszValue the key value to add.
546 : */
547 :
548 5445830 : CPLStringList &CPLStringList::SetNameValue(const char *pszKey,
549 : const char *pszValue)
550 :
551 : {
552 5445830 : int iKey = FindName(pszKey);
553 :
554 5445850 : if (iKey == -1)
555 5330020 : return AddNameValue(pszKey, pszValue);
556 :
557 115832 : Count();
558 115746 : if (!MakeOurOwnCopy())
559 0 : return *this;
560 :
561 115746 : CPLFree(papszList[iKey]);
562 115746 : if (pszValue == nullptr) // delete entry
563 : {
564 :
565 : // shift everything down by one.
566 558 : do
567 : {
568 2954 : papszList[iKey] = papszList[iKey + 1];
569 2954 : } while (papszList[iKey++] != nullptr);
570 :
571 2396 : nCount--;
572 : }
573 : else
574 : {
575 226700 : if (strlen(pszKey) >
576 226700 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
577 113350 : strlen(pszKey) + strlen(pszValue) >
578 113350 : std::numeric_limits<size_t>::max() - 2)
579 : {
580 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
581 : "Too big strings in AddNameValue()");
582 0 : return *this;
583 : }
584 113350 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
585 113350 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
586 113350 : if (pszLine == nullptr)
587 0 : return *this;
588 113350 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
589 :
590 113350 : papszList[iKey] = pszLine;
591 : }
592 :
593 115746 : return *this;
594 : }
595 :
596 : /************************************************************************/
597 : /* SetString() */
598 : /************************************************************************/
599 :
600 : /**
601 : * Replace a string within the list.
602 : *
603 : * @param pos 0-index position of the string to replace
604 : * @param pszString value to be used (will be copied)
605 : * @return a reference to the CPLStringList on which it was invoked.
606 : * @since 3.13
607 : */
608 6 : CPLStringList &CPLStringList::SetString(int pos, const char *pszString)
609 : {
610 6 : return SetStringDirectly(pos, VSI_STRDUP_VERBOSE(pszString));
611 : }
612 :
613 : /**
614 : * Replace a string within the list.
615 : *
616 : * @param pos 0-index position of the string to replace
617 : * @param osString value to be used (will be copied)
618 : * @return a reference to the CPLStringList on which it was invoked.
619 : * @since 3.13
620 : */
621 1 : CPLStringList &CPLStringList::SetString(int pos, const std::string &osString)
622 : {
623 1 : return SetString(pos, osString.c_str());
624 : }
625 :
626 : /**
627 : * Replace a string within the list.
628 : *
629 : * @param pos 0-index position of the string to replace
630 : * @param pszString value to be used (ownership is taken)
631 : * @return a reference to the CPLStringList on which it was invoked.
632 : * @since 3.13
633 : */
634 6 : CPLStringList &CPLStringList::SetStringDirectly(int pos, char *pszString)
635 : {
636 6 : if (!MakeOurOwnCopy())
637 0 : return *this;
638 :
639 6 : CPLFree(papszList[pos]);
640 6 : papszList[pos] = pszString;
641 :
642 6 : if (bIsSorted)
643 : {
644 8 : if (pos > 0 &&
645 2 : CPLCompareKeyValueString(papszList[pos], papszList[pos - 1]) == -1)
646 : {
647 0 : bIsSorted = false;
648 : }
649 11 : if (pos < Count() - 1 &&
650 5 : CPLCompareKeyValueString(papszList[pos], papszList[pos + 1]) == 1)
651 : {
652 3 : bIsSorted = false;
653 : }
654 : }
655 :
656 6 : return *this;
657 : }
658 :
659 : /************************************************************************/
660 : /* operator[] */
661 : /************************************************************************/
662 :
663 : /**
664 : * Fetch entry "i".
665 : *
666 : * Fetches the requested item in the list. Note that the returned string
667 : * remains owned by the CPLStringList. If "i" is out of range NULL is
668 : * returned.
669 : *
670 : * @param i the index of the list item to return.
671 : * @return selected entry in the list.
672 : */
673 1445470 : char *CPLStringList::operator[](int i)
674 :
675 : {
676 1445470 : if (nCount == -1)
677 280 : Count();
678 :
679 1445470 : if (i < 0 || i >= nCount)
680 50 : return nullptr;
681 :
682 1445420 : return papszList[i];
683 : }
684 :
685 700956 : const char *CPLStringList::operator[](int i) const
686 :
687 : {
688 700956 : if (nCount == -1)
689 671 : Count();
690 :
691 700956 : if (i < 0 || i >= nCount)
692 2 : return nullptr;
693 :
694 700954 : return papszList[i];
695 : }
696 :
697 : /************************************************************************/
698 : /* StealList() */
699 : /************************************************************************/
700 :
701 : /**
702 : * Seize ownership of underlying string array.
703 : *
704 : * This method is similar to List(), except that the returned list is
705 : * now owned by the caller and the CPLStringList is emptied.
706 : *
707 : * @return the C style string list.
708 : */
709 1612980 : char **CPLStringList::StealList()
710 :
711 : {
712 1612980 : char **papszRetList = papszList;
713 :
714 1612980 : bOwnList = false;
715 1612980 : papszList = nullptr;
716 1612980 : nCount = 0;
717 1612980 : nAllocation = 0;
718 :
719 1612980 : return papszRetList;
720 : }
721 :
722 : /* Case insensitive comparison function */
723 802912 : static int CPLCompareKeyValueString(const char *pszKVa, const char *pszKVb)
724 : {
725 802912 : const char *pszItera = pszKVa;
726 802912 : const char *pszIterb = pszKVb;
727 : while (true)
728 : {
729 5518010 : char cha = *pszItera;
730 5518010 : char chb = *pszIterb;
731 5518010 : if (cha == '=' || cha == '\0')
732 : {
733 4095 : if (chb == '=' || chb == '\0')
734 2 : return 0;
735 : else
736 4093 : return -1;
737 : }
738 5513920 : if (chb == '=' || chb == '\0')
739 : {
740 6705 : return 1;
741 : }
742 5507210 : if (cha >= 'a' && cha <= 'z')
743 516618 : cha -= ('a' - 'A');
744 5507210 : if (chb >= 'a' && chb <= 'z')
745 517704 : chb -= ('a' - 'A');
746 5507210 : if (cha < chb)
747 476547 : return -1;
748 5030670 : else if (cha > chb)
749 315565 : return 1;
750 4715100 : pszItera++;
751 4715100 : pszIterb++;
752 4715100 : }
753 : }
754 :
755 : /************************************************************************/
756 : /* Sort() */
757 : /************************************************************************/
758 :
759 : /**
760 : * Sort the entries in the list and mark list sorted.
761 : *
762 : * Note that once put into "sorted" mode, the CPLStringList will attempt to
763 : * keep things in sorted order through calls to AddString(),
764 : * AddStringDirectly(), AddNameValue(), SetNameValue(). Complete list
765 : * assignments (via Assign() and operator= will clear the sorting state.
766 : * When in sorted order FindName(), FetchNameValue() and FetchNameValueDef()
767 : * will do a binary search to find the key, substantially improve lookup
768 : * performance in large lists.
769 : */
770 :
771 99343 : CPLStringList &CPLStringList::Sort()
772 :
773 : {
774 99343 : Count();
775 99343 : if (!MakeOurOwnCopy())
776 0 : return *this;
777 :
778 99343 : if (nCount > 1)
779 : {
780 5772 : std::sort(papszList, papszList + nCount,
781 747078 : [](const char *a, const char *b)
782 747078 : { return CPLCompareKeyValueString(a, b) < 0; });
783 : }
784 99343 : bIsSorted = true;
785 :
786 99343 : return *this;
787 : }
788 :
789 : /************************************************************************/
790 : /* FindName() */
791 : /************************************************************************/
792 :
793 : /**
794 : * Get index of given name/value keyword.
795 : *
796 : * Note that this search is for a line in the form name=value or name:value.
797 : * Use FindString() or PartialFindString() for searches not based on name=value
798 : * pairs.
799 : *
800 : * @param pszKey the name to search for.
801 : *
802 : * @return the string list index of this name, or -1 on failure.
803 : */
804 :
805 18714100 : int CPLStringList::FindName(const char *pszKey) const
806 :
807 : {
808 18714100 : if (!IsSorted())
809 18685400 : return CSLFindName(papszList, pszKey);
810 :
811 : // If we are sorted, we can do an optimized binary search.
812 22173 : int iStart = 0;
813 22173 : int iEnd = nCount - 1;
814 22173 : size_t nKeyLen = strlen(pszKey);
815 :
816 56964 : while (iStart <= iEnd)
817 : {
818 42226 : const int iMiddle = (iEnd + iStart) / 2;
819 42226 : const char *pszMiddle = papszList[iMiddle];
820 :
821 42226 : if (EQUALN(pszMiddle, pszKey, nKeyLen) &&
822 7822 : (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':'))
823 7435 : return iMiddle;
824 :
825 34791 : if (CPLCompareKeyValueString(pszKey, pszMiddle) < 0)
826 9282 : iEnd = iMiddle - 1;
827 : else
828 25509 : iStart = iMiddle + 1;
829 : }
830 :
831 14738 : return -1;
832 : }
833 :
834 : /************************************************************************/
835 : /* FetchBool() */
836 : /************************************************************************/
837 : /**
838 : *
839 : * Check for boolean key value.
840 : *
841 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
842 : * with the given name, and if it can be interpreted as being TRUE. If
843 : * the key appears without any "=Value" portion it will be considered true.
844 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
845 : * if the key appears in the list it will be considered TRUE. If the key
846 : * doesn't appear at all, the indicated default value will be returned.
847 : *
848 : * @param pszKey the key value to look for (case insensitive).
849 : * @param bDefault the value to return if the key isn't found at all.
850 : *
851 : * @return true or false
852 : */
853 :
854 13809 : bool CPLStringList::FetchBool(const char *pszKey, bool bDefault) const
855 :
856 : {
857 13809 : const char *pszValue = FetchNameValue(pszKey);
858 :
859 13807 : if (pszValue == nullptr)
860 13560 : return bDefault;
861 :
862 247 : return CPLTestBool(pszValue);
863 : }
864 :
865 : /************************************************************************/
866 : /* FetchBoolean() */
867 : /************************************************************************/
868 : /**
869 : *
870 : * DEPRECATED: Check for boolean key value.
871 : *
872 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
873 : * with the given name, and if it can be interpreted as being TRUE. If
874 : * the key appears without any "=Value" portion it will be considered true.
875 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
876 : * if the key appears in the list it will be considered TRUE. If the key
877 : * doesn't appear at all, the indicated default value will be returned.
878 : *
879 : * @param pszKey the key value to look for (case insensitive).
880 : * @param bDefault the value to return if the key isn't found at all.
881 : *
882 : * @return TRUE or FALSE
883 : */
884 :
885 2997 : int CPLStringList::FetchBoolean(const char *pszKey, int bDefault) const
886 :
887 : {
888 2997 : return FetchBool(pszKey, CPL_TO_BOOL(bDefault)) ? TRUE : FALSE;
889 : }
890 :
891 : /************************************************************************/
892 : /* FetchNameValue() */
893 : /************************************************************************/
894 :
895 : /**
896 : * Fetch value associated with this key name.
897 : *
898 : * If this list sorted, a fast binary search is done, otherwise a linear
899 : * scan is done. Name lookup is case insensitive.
900 : *
901 : * @param pszName the key name to search for.
902 : *
903 : * @return the corresponding value or NULL if not found. The returned string
904 : * should not be modified and points into internal object state that may
905 : * change on future calls.
906 : */
907 :
908 13267200 : const char *CPLStringList::FetchNameValue(const char *pszName) const
909 :
910 : {
911 13267200 : const int iKey = FindName(pszName);
912 :
913 13273600 : if (iKey == -1)
914 4745510 : return nullptr;
915 :
916 8528040 : CPLAssert(papszList[iKey][strlen(pszName)] == '=' ||
917 : papszList[iKey][strlen(pszName)] == ':');
918 :
919 8528040 : return papszList[iKey] + strlen(pszName) + 1;
920 : }
921 :
922 : /************************************************************************/
923 : /* FetchNameValueDef() */
924 : /************************************************************************/
925 :
926 : /**
927 : * Fetch value associated with this key name.
928 : *
929 : * If this list sorted, a fast binary search is done, otherwise a linear
930 : * scan is done. Name lookup is case insensitive.
931 : *
932 : * @param pszName the key name to search for.
933 : * @param pszDefault the default value returned if the named entry isn't found.
934 : *
935 : * @return the corresponding value or the passed default if not found.
936 : */
937 :
938 38825 : const char *CPLStringList::FetchNameValueDef(const char *pszName,
939 : const char *pszDefault) const
940 :
941 : {
942 38825 : const char *pszValue = FetchNameValue(pszName);
943 38825 : if (pszValue == nullptr)
944 27376 : return pszDefault;
945 :
946 11449 : return pszValue;
947 : }
948 :
949 : /************************************************************************/
950 : /* InsertString() */
951 : /************************************************************************/
952 :
953 : /**
954 : * \fn CPLStringList *CPLStringList::InsertString( int nInsertAtLineNo,
955 : * const char *pszNewLine );
956 : *
957 : * \brief Insert into the list at identified location.
958 : *
959 : * This method will insert a string into the list at the identified
960 : * location. The insertion point must be within or at the end of the list.
961 : * The following entries are pushed down to make space.
962 : *
963 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
964 : * @param pszNewLine to the line to insert. This string will be copied.
965 : */
966 :
967 : /************************************************************************/
968 : /* InsertStringDirectly() */
969 : /************************************************************************/
970 :
971 : /**
972 : * Insert into the list at identified location.
973 : *
974 : * This method will insert a string into the list at the identified
975 : * location. The insertion point must be within or at the end of the list.
976 : * The following entries are pushed down to make space.
977 : *
978 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
979 : * @param pszNewLine to the line to insert, the ownership of this string
980 : * will be taken over the by the object. It must have been allocated on the
981 : * heap.
982 : */
983 :
984 7399 : CPLStringList &CPLStringList::InsertStringDirectly(int nInsertAtLineNo,
985 : char *pszNewLine)
986 :
987 : {
988 7399 : if (nCount == -1)
989 27 : Count();
990 :
991 7399 : if (!EnsureAllocation(nCount + 1))
992 : {
993 0 : VSIFree(pszNewLine);
994 0 : return *this;
995 : }
996 :
997 7399 : if (nInsertAtLineNo < 0 || nInsertAtLineNo > nCount)
998 : {
999 0 : CPLError(CE_Failure, CPLE_AppDefined,
1000 : "CPLStringList::InsertString() requested beyond list end.");
1001 0 : return *this;
1002 : }
1003 :
1004 7399 : bIsSorted = false;
1005 :
1006 23733 : for (int i = nCount; i > nInsertAtLineNo; i--)
1007 16334 : papszList[i] = papszList[i - 1];
1008 :
1009 7399 : papszList[nInsertAtLineNo] = pszNewLine;
1010 7399 : papszList[++nCount] = nullptr;
1011 :
1012 7399 : return *this;
1013 : }
1014 :
1015 : /************************************************************************/
1016 : /* RemoveStrings() */
1017 : /************************************************************************/
1018 :
1019 : /**
1020 : * Remove strings inside a CPLStringList.
1021 : *
1022 : * @param nFirstLineToDelete the 0-based index of the first string to
1023 : * remove. If this value is -1 or is larger than the actual
1024 : * number of strings in list then the nNumToRemove last strings are
1025 : * removed.
1026 : * @param nNumToRemove the number of strings to remove
1027 : *
1028 : * @return a reference to the CPLStringList on which it was invoked.
1029 : * @since 3.13
1030 : */
1031 1 : CPLStringList &CPLStringList::RemoveStrings(int nFirstLineToDelete,
1032 : int nNumToRemove)
1033 : {
1034 1 : if (!MakeOurOwnCopy())
1035 0 : return *this;
1036 :
1037 1 : papszList =
1038 1 : CSLRemoveStrings(papszList, nFirstLineToDelete, nNumToRemove, nullptr);
1039 1 : nCount = -1;
1040 1 : return *this;
1041 : }
1042 :
1043 : /************************************************************************/
1044 : /* FindSortedInsertionPoint() */
1045 : /* */
1046 : /* Find the location at which the indicated line should be */
1047 : /* inserted in order to keep things in sorted order. */
1048 : /************************************************************************/
1049 :
1050 7006 : int CPLStringList::FindSortedInsertionPoint(const char *pszLine)
1051 :
1052 : {
1053 7006 : CPLAssert(IsSorted());
1054 :
1055 7006 : int iStart = 0;
1056 7006 : int iEnd = nCount - 1;
1057 :
1058 22289 : while (iStart <= iEnd)
1059 : {
1060 15283 : const int iMiddle = (iEnd + iStart) / 2;
1061 15283 : const char *pszMiddle = papszList[iMiddle];
1062 :
1063 15283 : if (CPLCompareKeyValueString(pszLine, pszMiddle) < 0)
1064 2381 : iEnd = iMiddle - 1;
1065 : else
1066 12902 : iStart = iMiddle + 1;
1067 : }
1068 :
1069 7006 : iEnd++;
1070 7006 : CPLAssert(iEnd >= 0 && iEnd <= nCount);
1071 7006 : CPLAssert(iEnd == 0 ||
1072 : CPLCompareKeyValueString(pszLine, papszList[iEnd - 1]) >= 0);
1073 7006 : CPLAssert(iEnd == nCount ||
1074 : CPLCompareKeyValueString(pszLine, papszList[iEnd]) <= 0);
1075 :
1076 7006 : return iEnd;
1077 : }
1078 :
1079 : namespace cpl
1080 : {
1081 :
1082 : /************************************************************************/
1083 : /* CSLIterator::operator==(const CSLIterator &other) */
1084 : /************************************************************************/
1085 :
1086 : /*! @cond Doxygen_Suppress */
1087 22048900 : bool CSLIterator::operator==(const CSLIterator &other) const
1088 : {
1089 22048900 : if (!m_bAtEnd && other.m_bAtEnd)
1090 : {
1091 22047900 : return m_papszList == nullptr || *m_papszList == nullptr;
1092 : }
1093 902 : if (!m_bAtEnd && !other.m_bAtEnd)
1094 : {
1095 0 : return m_papszList == other.m_papszList;
1096 : }
1097 902 : if (m_bAtEnd && other.m_bAtEnd)
1098 : {
1099 0 : return true;
1100 : }
1101 902 : return false;
1102 : }
1103 :
1104 : /*! @endcond */
1105 :
1106 : /************************************************************************/
1107 : /* CSLNameValueIterator::operator*() */
1108 : /************************************************************************/
1109 :
1110 : /*! @cond Doxygen_Suppress */
1111 7251 : CSLNameValueIterator::value_type CSLNameValueIterator::operator*()
1112 : {
1113 7251 : if (m_papszList)
1114 : {
1115 7252 : while (*m_papszList)
1116 : {
1117 7252 : char *pszKey = nullptr;
1118 7252 : const char *pszValue = CPLParseNameValue(*m_papszList, &pszKey);
1119 7252 : if (pszKey)
1120 : {
1121 7249 : m_osKey = pszKey;
1122 7249 : CPLFree(pszKey);
1123 7249 : return {m_osKey.c_str(), pszValue};
1124 : }
1125 3 : else if (m_bReturnNullKeyIfNotNameValue)
1126 : {
1127 2 : return {nullptr, *m_papszList};
1128 : }
1129 : // Skip entries that are not name=value pairs.
1130 1 : ++m_papszList;
1131 : }
1132 : }
1133 : // Should not happen
1134 0 : CPLAssert(false);
1135 : return {"", ""};
1136 : }
1137 :
1138 : /*! @endcond */
1139 :
1140 : /************************************************************************/
1141 : /* CSLNameValueIteratorWrapper::end() */
1142 : /************************************************************************/
1143 :
1144 : /*! @cond Doxygen_Suppress */
1145 13137 : CSLNameValueIterator CSLNameValueIteratorWrapper::end() const
1146 : {
1147 13137 : int nCount = CSLCount(m_papszList);
1148 13137 : if (!m_bReturnNullKeyIfNotNameValue)
1149 : {
1150 13040 : while (nCount > 0 && strchr(m_papszList[nCount - 1], '=') == nullptr)
1151 12 : --nCount;
1152 : }
1153 13137 : return CSLNameValueIterator{m_papszList + nCount,
1154 13137 : m_bReturnNullKeyIfNotNameValue};
1155 : }
1156 :
1157 : /*! @endcond */
1158 :
1159 : } // namespace cpl
|
