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 2037360 : CPLStringList::CPLStringList(char **papszListIn, int bTakeOwnership)
50 2037360 : : CPLStringList()
51 :
52 : {
53 2031760 : Assign(papszListIn, bTakeOwnership);
54 2029060 : }
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 14959 : CPLStringList::CPLStringList(CSLConstList papszListIn) : CPLStringList()
69 :
70 : {
71 14955 : Assign(CSLDuplicate(papszListIn));
72 14948 : }
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 33530 : CPLStringList::CPLStringList(const CPLStringList &oOther) : CPLStringList()
129 :
130 : {
131 33530 : operator=(oOther);
132 33530 : }
133 :
134 : /************************************************************************/
135 : /* CPLStringList() */
136 : /************************************************************************/
137 :
138 : //! Move constructor
139 3634860 : CPLStringList::CPLStringList(CPLStringList &&oOther) : CPLStringList()
140 :
141 : {
142 3629360 : operator=(std::move(oOther));
143 3626690 : }
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 287677 : CPLStringList &CPLStringList::operator=(const CPLStringList &oOther)
171 : {
172 287677 : if (this != &oOther)
173 : {
174 287676 : char **l_papszList = CSLDuplicate(oOther.papszList);
175 287676 : if (l_papszList)
176 : {
177 12373 : Assign(l_papszList, TRUE);
178 12373 : nAllocation = oOther.nCount > 0 ? oOther.nCount + 1 : 0;
179 12373 : nCount = oOther.nCount;
180 12373 : bIsSorted = oOther.bIsSorted;
181 : }
182 : }
183 :
184 287677 : return *this;
185 : }
186 :
187 : /************************************************************************/
188 : /* operator=() */
189 : /************************************************************************/
190 :
191 3632530 : CPLStringList &CPLStringList::operator=(CPLStringList &&oOther)
192 : {
193 3632530 : if (this != &oOther)
194 : {
195 3634450 : Clear();
196 3635960 : papszList = oOther.papszList;
197 3635960 : oOther.papszList = nullptr;
198 3635960 : nCount = oOther.nCount;
199 3635960 : oOther.nCount = 0;
200 3635960 : nAllocation = oOther.nAllocation;
201 3635960 : oOther.nAllocation = 0;
202 3635960 : bOwnList = oOther.bOwnList;
203 3635960 : oOther.bOwnList = false;
204 3635960 : bIsSorted = oOther.bIsSorted;
205 3635960 : oOther.bIsSorted = true;
206 : }
207 :
208 3634040 : return *this;
209 : }
210 :
211 : /************************************************************************/
212 : /* operator=() */
213 : /************************************************************************/
214 :
215 103505 : CPLStringList &CPLStringList::operator=(CSLConstList papszListIn)
216 : {
217 103505 : if (papszListIn != papszList)
218 : {
219 16674 : Assign(CSLDuplicate(papszListIn));
220 16674 : bIsSorted = false;
221 : }
222 :
223 103505 : return *this;
224 : }
225 :
226 : /************************************************************************/
227 : /* ~CPLStringList() */
228 : /************************************************************************/
229 :
230 25335200 : CPLStringList::~CPLStringList()
231 :
232 : {
233 12671400 : Clear();
234 12663800 : }
235 :
236 : /************************************************************************/
237 : /* Clear() */
238 : /************************************************************************/
239 :
240 : /**
241 : * Clear the string list.
242 : */
243 18890900 : CPLStringList &CPLStringList::Clear()
244 :
245 : {
246 18890900 : if (bOwnList)
247 : {
248 3440350 : CSLDestroy(papszList);
249 3435440 : papszList = nullptr;
250 :
251 3435440 : bOwnList = FALSE;
252 3435440 : nAllocation = 0;
253 3435440 : nCount = 0;
254 : }
255 :
256 18886000 : 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 2471590 : CPLStringList &CPLStringList::Assign(char **papszListIn, int bTakeOwnership)
275 :
276 : {
277 2471590 : Clear();
278 :
279 2470290 : papszList = papszListIn;
280 2470290 : bOwnList = CPL_TO_BOOL(bTakeOwnership);
281 :
282 2467970 : if (papszList == nullptr || *papszList == nullptr)
283 1882610 : nCount = 0;
284 : else
285 585360 : nCount = -1; // unknown
286 :
287 2467970 : nAllocation = 0;
288 2467970 : bIsSorted = FALSE;
289 :
290 2467970 : return *this;
291 : }
292 :
293 : /************************************************************************/
294 : /* Count() */
295 : /************************************************************************/
296 :
297 : /**
298 : * @return count of strings in the list, zero if empty.
299 : */
300 :
301 3534650 : int CPLStringList::Count() const
302 :
303 : {
304 3534650 : if (nCount == -1)
305 : {
306 554599 : if (papszList == nullptr)
307 : {
308 0 : nCount = 0;
309 0 : nAllocation = 0;
310 : }
311 : else
312 : {
313 554599 : nCount = CSLCount(papszList);
314 554599 : nAllocation = std::max(nCount + 1, nAllocation);
315 : }
316 : }
317 :
318 3534540 : 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 8312500 : bool CPLStringList::MakeOurOwnCopy()
329 :
330 : {
331 8312500 : if (bOwnList)
332 4670790 : return true;
333 :
334 3641710 : if (papszList == nullptr)
335 3641300 : return true;
336 :
337 407 : 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 11699000 : bool CPLStringList::EnsureAllocation(int nMaxList)
358 :
359 : {
360 11699000 : if (!bOwnList)
361 : {
362 2874740 : if (!MakeOurOwnCopy())
363 0 : return false;
364 : }
365 :
366 11698600 : 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 5936280 : if (nMaxList < 0 || nMaxList > std::numeric_limits<int>::max() - 1 ||
371 2968970 : static_cast<size_t>(nMaxList) >
372 2968970 : std::numeric_limits<size_t>::max() / sizeof(char *) - 1)
373 : {
374 0 : return false;
375 : }
376 2967930 : int nNewAllocation = nMaxList + 1;
377 2967930 : if (nNewAllocation <= (std::numeric_limits<int>::max() - 20) / 2 /
378 : static_cast<int>(sizeof(char *)))
379 2968220 : nNewAllocation = std::max(nNewAllocation * 2 + 20, nMaxList + 1);
380 2968130 : if (papszList == nullptr)
381 : {
382 2877590 : papszList = static_cast<char **>(
383 2877440 : VSI_CALLOC_VERBOSE(nNewAllocation, sizeof(char *)));
384 2877590 : bOwnList = true;
385 2877590 : nCount = 0;
386 2877590 : if (papszList == nullptr)
387 0 : return false;
388 : }
389 : else
390 : {
391 90697 : char **papszListNew = static_cast<char **>(VSI_REALLOC_VERBOSE(
392 : papszList, nNewAllocation * sizeof(char *)));
393 90697 : if (papszListNew == nullptr)
394 0 : return false;
395 90697 : papszList = papszListNew;
396 : }
397 2968290 : nAllocation = nNewAllocation;
398 : }
399 11698700 : 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 11691000 : CPLStringList &CPLStringList::AddStringDirectly(char *pszNewString)
416 :
417 : {
418 11691000 : if (nCount == -1)
419 664 : Count();
420 :
421 11691000 : if (!EnsureAllocation(nCount + 1))
422 : {
423 0 : VSIFree(pszNewString);
424 0 : return *this;
425 : }
426 :
427 11691300 : papszList[nCount++] = pszNewString;
428 11691300 : papszList[nCount] = nullptr;
429 :
430 11691300 : bIsSorted = false;
431 :
432 11691300 : 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 6434280 : CPLStringList &CPLStringList::AddString(const char *pszNewString)
448 :
449 : {
450 6434280 : char *pszDupString = VSI_STRDUP_VERBOSE(pszNewString);
451 6434040 : if (pszDupString == nullptr)
452 0 : return *this;
453 6434040 : 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 : /* push_back() */
475 : /************************************************************************/
476 :
477 : /**
478 : * Add a string to the list.
479 : *
480 : * A copy of the passed in string is made and inserted in the list.
481 : *
482 : * @param svStr the string to add to the list.
483 : *
484 : * @since 3.13
485 : */
486 :
487 92 : void CPLStringList::push_back(std::string_view svStr)
488 :
489 : {
490 : char *pszDupString =
491 92 : static_cast<char *>(VSI_MALLOC_VERBOSE(svStr.size() + 1));
492 92 : if (pszDupString == nullptr)
493 0 : return;
494 92 : memcpy(pszDupString, svStr.data(), svStr.size());
495 92 : pszDupString[svStr.size()] = 0;
496 92 : CPL_IGNORE_RET_VAL(AddStringDirectly(pszDupString));
497 : }
498 :
499 : /************************************************************************/
500 : /* AddNameValue() */
501 : /************************************************************************/
502 :
503 : /**
504 : * Add a name=value entry to the list.
505 : *
506 : * A key=value string is prepared and appended to the list. There is no
507 : * check for other values for the same key in the list.
508 : *
509 : * @param pszKey the key name to add.
510 : * @param pszValue the key value to add.
511 : */
512 :
513 5367180 : CPLStringList &CPLStringList::AddNameValue(const char *pszKey,
514 : const char *pszValue)
515 :
516 : {
517 5367180 : if (pszKey == nullptr || pszValue == nullptr)
518 144550 : return *this;
519 :
520 5222630 : if (!MakeOurOwnCopy())
521 0 : return *this;
522 :
523 : /* -------------------------------------------------------------------- */
524 : /* Format the line. */
525 : /* -------------------------------------------------------------------- */
526 10445700 : if (strlen(pszKey) >
527 10445600 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
528 5222700 : strlen(pszKey) + strlen(pszValue) >
529 5222700 : std::numeric_limits<size_t>::max() - 2)
530 : {
531 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
532 : "Too big strings in AddNameValue()");
533 0 : return *this;
534 : }
535 5222900 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
536 5222900 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
537 5222750 : if (pszLine == nullptr)
538 0 : return *this;
539 5222750 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
540 :
541 : /* -------------------------------------------------------------------- */
542 : /* If we don't need to keep the sort order things are pretty */
543 : /* straight forward. */
544 : /* -------------------------------------------------------------------- */
545 5222750 : if (!IsSorted())
546 5215450 : return AddStringDirectly(pszLine);
547 :
548 : /* -------------------------------------------------------------------- */
549 : /* Find the proper insertion point. */
550 : /* -------------------------------------------------------------------- */
551 7210 : CPLAssert(IsSorted());
552 7022 : const int iKey = FindSortedInsertionPoint(pszLine);
553 7022 : InsertStringDirectly(iKey, pszLine);
554 7022 : bIsSorted = true; // We have actually preserved sort order.
555 :
556 7022 : return *this;
557 : }
558 :
559 : /************************************************************************/
560 : /* SetNameValue() */
561 : /************************************************************************/
562 :
563 : /**
564 : * Set name=value entry in the list.
565 : *
566 : * Similar to AddNameValue(), except if there is already a value for
567 : * the key in the list it is replaced instead of adding a new entry to
568 : * the list. If pszValue is NULL any existing key entry is removed.
569 : *
570 : * @param pszKey the key name to add.
571 : * @param pszValue the key value to add.
572 : */
573 :
574 5446950 : CPLStringList &CPLStringList::SetNameValue(const char *pszKey,
575 : const char *pszValue)
576 :
577 : {
578 5446950 : int iKey = FindName(pszKey);
579 :
580 5446910 : if (iKey == -1)
581 5330550 : return AddNameValue(pszKey, pszValue);
582 :
583 116354 : Count();
584 115782 : if (!MakeOurOwnCopy())
585 0 : return *this;
586 :
587 115782 : CPLFree(papszList[iKey]);
588 115782 : if (pszValue == nullptr) // delete entry
589 : {
590 :
591 : // shift everything down by one.
592 558 : do
593 : {
594 2988 : papszList[iKey] = papszList[iKey + 1];
595 2988 : } while (papszList[iKey++] != nullptr);
596 :
597 2430 : nCount--;
598 : }
599 : else
600 : {
601 226704 : if (strlen(pszKey) >
602 226704 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
603 113352 : strlen(pszKey) + strlen(pszValue) >
604 113352 : std::numeric_limits<size_t>::max() - 2)
605 : {
606 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
607 : "Too big strings in AddNameValue()");
608 0 : return *this;
609 : }
610 113352 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
611 113352 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
612 113352 : if (pszLine == nullptr)
613 0 : return *this;
614 113352 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
615 :
616 113352 : papszList[iKey] = pszLine;
617 : }
618 :
619 115782 : return *this;
620 : }
621 :
622 : /************************************************************************/
623 : /* SetString() */
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 (will be copied)
631 : * @return a reference to the CPLStringList on which it was invoked.
632 : * @since 3.13
633 : */
634 6 : CPLStringList &CPLStringList::SetString(int pos, const char *pszString)
635 : {
636 6 : return SetStringDirectly(pos, VSI_STRDUP_VERBOSE(pszString));
637 : }
638 :
639 : /**
640 : * Replace a string within the list.
641 : *
642 : * @param pos 0-index position of the string to replace
643 : * @param osString value to be used (will be copied)
644 : * @return a reference to the CPLStringList on which it was invoked.
645 : * @since 3.13
646 : */
647 1 : CPLStringList &CPLStringList::SetString(int pos, const std::string &osString)
648 : {
649 1 : return SetString(pos, osString.c_str());
650 : }
651 :
652 : /**
653 : * Replace a string within the list.
654 : *
655 : * @param pos 0-index position of the string to replace
656 : * @param pszString value to be used (ownership is taken)
657 : * @return a reference to the CPLStringList on which it was invoked.
658 : * @since 3.13
659 : */
660 6 : CPLStringList &CPLStringList::SetStringDirectly(int pos, char *pszString)
661 : {
662 6 : if (!MakeOurOwnCopy())
663 0 : return *this;
664 :
665 6 : CPLFree(papszList[pos]);
666 6 : papszList[pos] = pszString;
667 :
668 6 : if (bIsSorted)
669 : {
670 8 : if (pos > 0 &&
671 2 : CPLCompareKeyValueString(papszList[pos], papszList[pos - 1]) == -1)
672 : {
673 0 : bIsSorted = false;
674 : }
675 11 : if (pos < Count() - 1 &&
676 5 : CPLCompareKeyValueString(papszList[pos], papszList[pos + 1]) == 1)
677 : {
678 3 : bIsSorted = false;
679 : }
680 : }
681 :
682 6 : return *this;
683 : }
684 :
685 : /************************************************************************/
686 : /* operator[] */
687 : /************************************************************************/
688 :
689 : /**
690 : * Fetch entry "i".
691 : *
692 : * Fetches the requested item in the list. Note that the returned string
693 : * remains owned by the CPLStringList. If "i" is out of range NULL is
694 : * returned.
695 : *
696 : * @param i the index of the list item to return.
697 : * @return selected entry in the list.
698 : */
699 1448040 : char *CPLStringList::operator[](int i)
700 :
701 : {
702 1448040 : if (nCount == -1)
703 280 : Count();
704 :
705 1448040 : if (i < 0 || i >= nCount)
706 50 : return nullptr;
707 :
708 1447990 : return papszList[i];
709 : }
710 :
711 701112 : const char *CPLStringList::operator[](int i) const
712 :
713 : {
714 701112 : if (nCount == -1)
715 671 : Count();
716 :
717 701112 : if (i < 0 || i >= nCount)
718 2 : return nullptr;
719 :
720 701110 : return papszList[i];
721 : }
722 :
723 : /************************************************************************/
724 : /* StealList() */
725 : /************************************************************************/
726 :
727 : /**
728 : * Seize ownership of underlying string array.
729 : *
730 : * This method is similar to List(), except that the returned list is
731 : * now owned by the caller and the CPLStringList is emptied.
732 : *
733 : * @return the C style string list.
734 : */
735 1615680 : char **CPLStringList::StealList()
736 :
737 : {
738 1615680 : char **papszRetList = papszList;
739 :
740 1615680 : bOwnList = false;
741 1615680 : papszList = nullptr;
742 1615680 : nCount = 0;
743 1615680 : nAllocation = 0;
744 :
745 1615680 : return papszRetList;
746 : }
747 :
748 : /* Case insensitive comparison function */
749 803902 : static int CPLCompareKeyValueString(const char *pszKVa, const char *pszKVb)
750 : {
751 803902 : const char *pszItera = pszKVa;
752 803902 : const char *pszIterb = pszKVb;
753 : while (true)
754 : {
755 5524850 : char cha = *pszItera;
756 5524850 : char chb = *pszIterb;
757 5524850 : if (cha == '=' || cha == '\0')
758 : {
759 4097 : if (chb == '=' || chb == '\0')
760 2 : return 0;
761 : else
762 4095 : return -1;
763 : }
764 5520760 : if (chb == '=' || chb == '\0')
765 : {
766 6730 : return 1;
767 : }
768 5514020 : if (cha >= 'a' && cha <= 'z')
769 516618 : cha -= ('a' - 'A');
770 5514020 : if (chb >= 'a' && chb <= 'z')
771 517704 : chb -= ('a' - 'A');
772 5514020 : if (cha < chb)
773 477108 : return -1;
774 5036920 : else if (cha > chb)
775 315967 : return 1;
776 4720950 : pszItera++;
777 4720950 : pszIterb++;
778 4720950 : }
779 : }
780 :
781 : /************************************************************************/
782 : /* Sort() */
783 : /************************************************************************/
784 :
785 : /**
786 : * Sort the entries in the list and mark list sorted.
787 : *
788 : * Note that once put into "sorted" mode, the CPLStringList will attempt to
789 : * keep things in sorted order through calls to AddString(),
790 : * AddStringDirectly(), AddNameValue(), SetNameValue(). Complete list
791 : * assignments (via Assign() and operator= will clear the sorting state.
792 : * When in sorted order FindName(), FetchNameValue() and FetchNameValueDef()
793 : * will do a binary search to find the key, substantially improve lookup
794 : * performance in large lists.
795 : */
796 :
797 99372 : CPLStringList &CPLStringList::Sort()
798 :
799 : {
800 99372 : Count();
801 99372 : if (!MakeOurOwnCopy())
802 0 : return *this;
803 :
804 99372 : if (nCount > 1)
805 : {
806 5776 : std::sort(papszList, papszList + nCount,
807 747954 : [](const char *a, const char *b)
808 747954 : { return CPLCompareKeyValueString(a, b) < 0; });
809 : }
810 99372 : bIsSorted = true;
811 :
812 99372 : return *this;
813 : }
814 :
815 : /************************************************************************/
816 : /* FindName() */
817 : /************************************************************************/
818 :
819 : /**
820 : * Get index of given name/value keyword.
821 : *
822 : * Note that this search is for a line in the form name=value or name:value.
823 : * Use FindString() or PartialFindString() for searches not based on name=value
824 : * pairs.
825 : *
826 : * @param pszKey the name to search for.
827 : *
828 : * @return the string list index of this name, or -1 on failure.
829 : */
830 :
831 18750100 : int CPLStringList::FindName(const char *pszKey) const
832 :
833 : {
834 18750100 : if (!IsSorted())
835 18726000 : return CSLFindName(papszList, pszKey);
836 :
837 : // If we are sorted, we can do an optimized binary search.
838 22193 : int iStart = 0;
839 22193 : int iEnd = nCount - 1;
840 22193 : size_t nKeyLen = strlen(pszKey);
841 :
842 57034 : while (iStart <= iEnd)
843 : {
844 42276 : const int iMiddle = (iEnd + iStart) / 2;
845 42276 : const char *pszMiddle = papszList[iMiddle];
846 :
847 42276 : if (EQUALN(pszMiddle, pszKey, nKeyLen) &&
848 7822 : (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':'))
849 7435 : return iMiddle;
850 :
851 34841 : if (CPLCompareKeyValueString(pszKey, pszMiddle) < 0)
852 9286 : iEnd = iMiddle - 1;
853 : else
854 25555 : iStart = iMiddle + 1;
855 : }
856 :
857 14758 : return -1;
858 : }
859 :
860 : /************************************************************************/
861 : /* FetchBool() */
862 : /************************************************************************/
863 : /**
864 : *
865 : * Check for boolean key value.
866 : *
867 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
868 : * with the given name, and if it can be interpreted as being TRUE. If
869 : * the key appears without any "=Value" portion it will be considered true.
870 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
871 : * if the key appears in the list it will be considered TRUE. If the key
872 : * doesn't appear at all, the indicated default value will be returned.
873 : *
874 : * @param pszKey the key value to look for (case insensitive).
875 : * @param bDefault the value to return if the key isn't found at all.
876 : *
877 : * @return true or false
878 : */
879 :
880 13809 : bool CPLStringList::FetchBool(const char *pszKey, bool bDefault) const
881 :
882 : {
883 13809 : const char *pszValue = FetchNameValue(pszKey);
884 :
885 13809 : if (pszValue == nullptr)
886 13562 : return bDefault;
887 :
888 247 : return CPLTestBool(pszValue);
889 : }
890 :
891 : /************************************************************************/
892 : /* FetchBoolean() */
893 : /************************************************************************/
894 : /**
895 : *
896 : * DEPRECATED: Check for boolean key value.
897 : *
898 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
899 : * with the given name, and if it can be interpreted as being TRUE. If
900 : * the key appears without any "=Value" portion it will be considered true.
901 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
902 : * if the key appears in the list it will be considered TRUE. If the key
903 : * doesn't appear at all, the indicated default value will be returned.
904 : *
905 : * @param pszKey the key value to look for (case insensitive).
906 : * @param bDefault the value to return if the key isn't found at all.
907 : *
908 : * @return TRUE or FALSE
909 : */
910 :
911 2997 : int CPLStringList::FetchBoolean(const char *pszKey, int bDefault) const
912 :
913 : {
914 2997 : return FetchBool(pszKey, CPL_TO_BOOL(bDefault)) ? TRUE : FALSE;
915 : }
916 :
917 : /************************************************************************/
918 : /* FetchNameValue() */
919 : /************************************************************************/
920 :
921 : /**
922 : * Fetch value associated with this key name.
923 : *
924 : * If this list sorted, a fast binary search is done, otherwise a linear
925 : * scan is done. Name lookup is case insensitive.
926 : *
927 : * @param pszName the key name to search for.
928 : *
929 : * @return the corresponding value or NULL if not found. The returned string
930 : * should not be modified and points into internal object state that may
931 : * change on future calls.
932 : */
933 :
934 13312400 : const char *CPLStringList::FetchNameValue(const char *pszName) const
935 :
936 : {
937 13312400 : const int iKey = FindName(pszName);
938 :
939 13321600 : if (iKey == -1)
940 4765150 : return nullptr;
941 :
942 8556440 : CPLAssert(papszList[iKey][strlen(pszName)] == '=' ||
943 : papszList[iKey][strlen(pszName)] == ':');
944 :
945 8556440 : return papszList[iKey] + strlen(pszName) + 1;
946 : }
947 :
948 : /************************************************************************/
949 : /* FetchNameValueDef() */
950 : /************************************************************************/
951 :
952 : /**
953 : * Fetch value associated with this key name.
954 : *
955 : * If this list sorted, a fast binary search is done, otherwise a linear
956 : * scan is done. Name lookup is case insensitive.
957 : *
958 : * @param pszName the key name to search for.
959 : * @param pszDefault the default value returned if the named entry isn't found.
960 : *
961 : * @return the corresponding value or the passed default if not found.
962 : */
963 :
964 38965 : const char *CPLStringList::FetchNameValueDef(const char *pszName,
965 : const char *pszDefault) const
966 :
967 : {
968 38965 : const char *pszValue = FetchNameValue(pszName);
969 38965 : if (pszValue == nullptr)
970 27509 : return pszDefault;
971 :
972 11456 : return pszValue;
973 : }
974 :
975 : /************************************************************************/
976 : /* InsertString() */
977 : /************************************************************************/
978 :
979 : /**
980 : * \fn CPLStringList *CPLStringList::InsertString( int nInsertAtLineNo,
981 : * const char *pszNewLine );
982 : *
983 : * \brief Insert into the list at identified location.
984 : *
985 : * This method will insert a string into the list at the identified
986 : * location. The insertion point must be within or at the end of the list.
987 : * The following entries are pushed down to make space.
988 : *
989 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
990 : * @param pszNewLine to the line to insert. This string will be copied.
991 : */
992 :
993 : /************************************************************************/
994 : /* InsertStringDirectly() */
995 : /************************************************************************/
996 :
997 : /**
998 : * Insert into the list at identified location.
999 : *
1000 : * This method will insert a string into the list at the identified
1001 : * location. The insertion point must be within or at the end of the list.
1002 : * The following entries are pushed down to make space.
1003 : *
1004 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
1005 : * @param pszNewLine to the line to insert, the ownership of this string
1006 : * will be taken over the by the object. It must have been allocated on the
1007 : * heap.
1008 : */
1009 :
1010 7415 : CPLStringList &CPLStringList::InsertStringDirectly(int nInsertAtLineNo,
1011 : char *pszNewLine)
1012 :
1013 : {
1014 7415 : if (nCount == -1)
1015 27 : Count();
1016 :
1017 7415 : if (!EnsureAllocation(nCount + 1))
1018 : {
1019 0 : VSIFree(pszNewLine);
1020 0 : return *this;
1021 : }
1022 :
1023 7415 : if (nInsertAtLineNo < 0 || nInsertAtLineNo > nCount)
1024 : {
1025 0 : CPLError(CE_Failure, CPLE_AppDefined,
1026 : "CPLStringList::InsertString() requested beyond list end.");
1027 0 : return *this;
1028 : }
1029 :
1030 7415 : bIsSorted = false;
1031 :
1032 23757 : for (int i = nCount; i > nInsertAtLineNo; i--)
1033 16342 : papszList[i] = papszList[i - 1];
1034 :
1035 7415 : papszList[nInsertAtLineNo] = pszNewLine;
1036 7415 : papszList[++nCount] = nullptr;
1037 :
1038 7415 : return *this;
1039 : }
1040 :
1041 : /************************************************************************/
1042 : /* RemoveStrings() */
1043 : /************************************************************************/
1044 :
1045 : /**
1046 : * Remove strings inside a CPLStringList.
1047 : *
1048 : * @param nFirstLineToDelete the 0-based index of the first string to
1049 : * remove. If this value is -1 or is larger than the actual
1050 : * number of strings in list then the nNumToRemove last strings are
1051 : * removed.
1052 : * @param nNumToRemove the number of strings to remove
1053 : *
1054 : * @return a reference to the CPLStringList on which it was invoked.
1055 : * @since 3.13
1056 : */
1057 1 : CPLStringList &CPLStringList::RemoveStrings(int nFirstLineToDelete,
1058 : int nNumToRemove)
1059 : {
1060 1 : if (!MakeOurOwnCopy())
1061 0 : return *this;
1062 :
1063 1 : papszList =
1064 1 : CSLRemoveStrings(papszList, nFirstLineToDelete, nNumToRemove, nullptr);
1065 1 : nCount = -1;
1066 1 : return *this;
1067 : }
1068 :
1069 : /************************************************************************/
1070 : /* FindSortedInsertionPoint() */
1071 : /* */
1072 : /* Find the location at which the indicated line should be */
1073 : /* inserted in order to keep things in sorted order. */
1074 : /************************************************************************/
1075 :
1076 7022 : int CPLStringList::FindSortedInsertionPoint(const char *pszLine)
1077 :
1078 : {
1079 7022 : CPLAssert(IsSorted());
1080 :
1081 7022 : int iStart = 0;
1082 7022 : int iEnd = nCount - 1;
1083 :
1084 22351 : while (iStart <= iEnd)
1085 : {
1086 15329 : const int iMiddle = (iEnd + iStart) / 2;
1087 15329 : const char *pszMiddle = papszList[iMiddle];
1088 :
1089 15329 : if (CPLCompareKeyValueString(pszLine, pszMiddle) < 0)
1090 2385 : iEnd = iMiddle - 1;
1091 : else
1092 12944 : iStart = iMiddle + 1;
1093 : }
1094 :
1095 7022 : iEnd++;
1096 7022 : CPLAssert(iEnd >= 0 && iEnd <= nCount);
1097 7022 : CPLAssert(iEnd == 0 ||
1098 : CPLCompareKeyValueString(pszLine, papszList[iEnd - 1]) >= 0);
1099 7022 : CPLAssert(iEnd == nCount ||
1100 : CPLCompareKeyValueString(pszLine, papszList[iEnd]) <= 0);
1101 :
1102 7022 : return iEnd;
1103 : }
1104 :
1105 : namespace cpl
1106 : {
1107 :
1108 : /************************************************************************/
1109 : /* CSLIterator::operator==(const CSLIterator &other) */
1110 : /************************************************************************/
1111 :
1112 : /*! @cond Doxygen_Suppress */
1113 22057400 : bool CSLIterator::operator==(const CSLIterator &other) const
1114 : {
1115 22057400 : if (!m_bAtEnd && other.m_bAtEnd)
1116 : {
1117 22057500 : return m_papszList == nullptr || *m_papszList == nullptr;
1118 : }
1119 0 : if (!m_bAtEnd && !other.m_bAtEnd)
1120 : {
1121 0 : return m_papszList == other.m_papszList;
1122 : }
1123 0 : if (m_bAtEnd && other.m_bAtEnd)
1124 : {
1125 0 : return true;
1126 : }
1127 0 : return false;
1128 : }
1129 :
1130 : /*! @endcond */
1131 :
1132 : /************************************************************************/
1133 : /* CSLNameValueIterator::operator*() */
1134 : /************************************************************************/
1135 :
1136 : /*! @cond Doxygen_Suppress */
1137 7423 : CSLNameValueIterator::value_type CSLNameValueIterator::operator*()
1138 : {
1139 7423 : if (m_papszList)
1140 : {
1141 7424 : while (*m_papszList)
1142 : {
1143 7424 : char *pszKey = nullptr;
1144 7424 : const char *pszValue = CPLParseNameValue(*m_papszList, &pszKey);
1145 7424 : if (pszKey)
1146 : {
1147 7421 : m_osKey = pszKey;
1148 7421 : CPLFree(pszKey);
1149 7421 : return {m_osKey.c_str(), pszValue};
1150 : }
1151 3 : else if (m_bReturnNullKeyIfNotNameValue)
1152 : {
1153 2 : return {nullptr, *m_papszList};
1154 : }
1155 : // Skip entries that are not name=value pairs.
1156 1 : ++m_papszList;
1157 : }
1158 : }
1159 : // Should not happen
1160 0 : CPLAssert(false);
1161 : return {"", ""};
1162 : }
1163 :
1164 : /*! @endcond */
1165 :
1166 : /************************************************************************/
1167 : /* CSLNameValueIteratorWrapper::end() */
1168 : /************************************************************************/
1169 :
1170 : /*! @cond Doxygen_Suppress */
1171 13291 : CSLNameValueIterator CSLNameValueIteratorWrapper::end() const
1172 : {
1173 13291 : int nCount = CSLCount(m_papszList);
1174 13291 : if (!m_bReturnNullKeyIfNotNameValue)
1175 : {
1176 13194 : while (nCount > 0 && strchr(m_papszList[nCount - 1], '=') == nullptr)
1177 12 : --nCount;
1178 : }
1179 13291 : return CSLNameValueIterator{m_papszList + nCount,
1180 13291 : m_bReturnNullKeyIfNotNameValue};
1181 : }
1182 :
1183 : /*! @endcond */
1184 :
1185 : } // namespace cpl
|
