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 3653330 : CPLStringList::CPLStringList(char **papszListIn, int bTakeOwnership)
50 3653330 : : CPLStringList()
51 :
52 : {
53 3642450 : Assign(papszListIn, bTakeOwnership);
54 3640550 : }
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 18737 : CPLStringList::CPLStringList(CSLConstList papszListIn) : CPLStringList()
69 :
70 : {
71 18737 : Assign(CSLDuplicate(papszListIn));
72 18737 : }
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 169389 : CPLStringList::CPLStringList(const std::vector<std::string> &aosList)
88 : {
89 169389 : if (!aosList.empty())
90 : {
91 47379 : bOwnList = true;
92 47379 : papszList = static_cast<char **>(
93 47379 : VSI_CALLOC_VERBOSE(aosList.size() + 1, sizeof(char *)));
94 47379 : nCount = static_cast<int>(aosList.size());
95 111863 : for (int i = 0; i < nCount; ++i)
96 : {
97 64484 : papszList[i] = VSI_STRDUP_VERBOSE(aosList[i].c_str());
98 : }
99 : }
100 169389 : }
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 35282 : CPLStringList::CPLStringList(const CPLStringList &oOther) : CPLStringList()
129 :
130 : {
131 35282 : operator=(oOther);
132 35283 : }
133 :
134 : /************************************************************************/
135 : /* CPLStringList() */
136 : /************************************************************************/
137 :
138 : //! Move constructor
139 3706390 : CPLStringList::CPLStringList(CPLStringList &&oOther) : CPLStringList()
140 :
141 : {
142 3698140 : operator=(std::move(oOther));
143 3708540 : }
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 98 : const CPLStringList CPLStringList::BoundToConstList(CSLConstList papszListIn)
161 : {
162 : return CPLStringList(const_cast<char **>(papszListIn),
163 98 : /* bTakeOwnership= */ false);
164 : }
165 :
166 : /************************************************************************/
167 : /* operator=() */
168 : /************************************************************************/
169 :
170 289772 : CPLStringList &CPLStringList::operator=(const CPLStringList &oOther)
171 : {
172 289772 : if (this != &oOther)
173 : {
174 289771 : char **l_papszList = CSLDuplicate(oOther.papszList);
175 289771 : if (l_papszList)
176 : {
177 12487 : Assign(l_papszList, TRUE);
178 12488 : nAllocation = oOther.nCount > 0 ? oOther.nCount + 1 : 0;
179 12488 : nCount = oOther.nCount;
180 12488 : bIsSorted = oOther.bIsSorted;
181 : }
182 : }
183 :
184 289773 : return *this;
185 : }
186 :
187 : /************************************************************************/
188 : /* operator=() */
189 : /************************************************************************/
190 :
191 3708680 : CPLStringList &CPLStringList::operator=(CPLStringList &&oOther)
192 : {
193 3708680 : if (this != &oOther)
194 : {
195 3711750 : Clear();
196 3716610 : papszList = oOther.papszList;
197 3716610 : oOther.papszList = nullptr;
198 3716610 : nCount = oOther.nCount;
199 3716610 : oOther.nCount = 0;
200 3716610 : nAllocation = oOther.nAllocation;
201 3716610 : oOther.nAllocation = 0;
202 3716610 : bOwnList = oOther.bOwnList;
203 3716610 : oOther.bOwnList = false;
204 3716610 : bIsSorted = oOther.bIsSorted;
205 3716610 : oOther.bIsSorted = true;
206 : }
207 :
208 3713540 : return *this;
209 : }
210 :
211 : /************************************************************************/
212 : /* operator=() */
213 : /************************************************************************/
214 :
215 105482 : CPLStringList &CPLStringList::operator=(CSLConstList papszListIn)
216 : {
217 105482 : if (papszListIn != papszList)
218 : {
219 17559 : Assign(CSLDuplicate(papszListIn));
220 17559 : bIsSorted = false;
221 : }
222 :
223 105482 : return *this;
224 : }
225 :
226 : /************************************************************************/
227 : /* ~CPLStringList() */
228 : /************************************************************************/
229 :
230 29793300 : CPLStringList::~CPLStringList()
231 :
232 : {
233 14903500 : Clear();
234 14889800 : }
235 :
236 : /************************************************************************/
237 : /* Clear() */
238 : /************************************************************************/
239 :
240 : /**
241 : * Clear the string list.
242 : */
243 22822800 : CPLStringList &CPLStringList::Clear()
244 :
245 : {
246 22822800 : if (bOwnList)
247 : {
248 3638030 : CSLDestroy(papszList);
249 3630190 : papszList = nullptr;
250 :
251 3630190 : bOwnList = FALSE;
252 3630190 : nAllocation = 0;
253 3630190 : nCount = 0;
254 : }
255 :
256 22815000 : 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 4094080 : CPLStringList &CPLStringList::Assign(char **papszListIn, int bTakeOwnership)
275 :
276 : {
277 4094080 : Clear();
278 :
279 4088240 : papszList = papszListIn;
280 4088240 : bOwnList = CPL_TO_BOOL(bTakeOwnership);
281 :
282 4085300 : if (papszList == nullptr || *papszList == nullptr)
283 1910280 : nCount = 0;
284 : else
285 2175020 : nCount = -1; // unknown
286 :
287 4085300 : nAllocation = 0;
288 4085300 : bIsSorted = FALSE;
289 :
290 4085300 : return *this;
291 : }
292 :
293 : /************************************************************************/
294 : /* Count() */
295 : /************************************************************************/
296 :
297 : /**
298 : * @return count of strings in the list, zero if empty.
299 : */
300 :
301 3725250 : int CPLStringList::Count() const
302 :
303 : {
304 3725250 : if (nCount == -1)
305 : {
306 601085 : if (papszList == nullptr)
307 : {
308 0 : nCount = 0;
309 0 : nAllocation = 0;
310 : }
311 : else
312 : {
313 601085 : nCount = CSLCount(papszList);
314 601098 : nAllocation = std::max(nCount + 1, nAllocation);
315 : }
316 : }
317 :
318 3725200 : 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 8994780 : bool CPLStringList::MakeOurOwnCopy()
329 :
330 : {
331 8994780 : if (bOwnList)
332 5036100 : return true;
333 :
334 3958690 : if (papszList == nullptr)
335 3958240 : return true;
336 :
337 451 : Count();
338 99 : char **papszListNew = CSLDuplicate(papszList);
339 99 : if (papszListNew == nullptr)
340 : {
341 0 : return false;
342 : }
343 99 : papszList = papszListNew;
344 99 : bOwnList = true;
345 99 : nAllocation = nCount + 1;
346 99 : 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 13051100 : bool CPLStringList::EnsureAllocation(int nMaxList)
358 :
359 : {
360 13051100 : if (!bOwnList)
361 : {
362 3130550 : if (!MakeOurOwnCopy())
363 0 : return false;
364 : }
365 :
366 13050900 : 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 6482420 : if (nMaxList < 0 || nMaxList > std::numeric_limits<int>::max() - 1 ||
371 3241500 : static_cast<size_t>(nMaxList) >
372 3241500 : std::numeric_limits<size_t>::max() / sizeof(char *) - 1)
373 : {
374 0 : return false;
375 : }
376 3241110 : int nNewAllocation = nMaxList + 1;
377 3241110 : if (nNewAllocation <= (std::numeric_limits<int>::max() - 20) / 2 /
378 : static_cast<int>(sizeof(char *)))
379 3241320 : nNewAllocation = std::max(nNewAllocation * 2 + 20, nMaxList + 1);
380 3241160 : if (papszList == nullptr)
381 : {
382 3133860 : papszList = static_cast<char **>(
383 3133690 : VSI_CALLOC_VERBOSE(nNewAllocation, sizeof(char *)));
384 3133860 : bOwnList = true;
385 3133860 : nCount = 0;
386 3133860 : if (papszList == nullptr)
387 0 : return false;
388 : }
389 : else
390 : {
391 107463 : char **papszListNew = static_cast<char **>(VSI_REALLOC_VERBOSE(
392 : papszList, nNewAllocation * sizeof(char *)));
393 107463 : if (papszListNew == nullptr)
394 0 : return false;
395 107463 : papszList = papszListNew;
396 : }
397 3241330 : nAllocation = nNewAllocation;
398 : }
399 13051000 : 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 13043100 : CPLStringList &CPLStringList::AddStringDirectly(char *pszNewString)
416 :
417 : {
418 13043100 : if (nCount == -1)
419 716 : Count();
420 :
421 13043100 : if (!EnsureAllocation(nCount + 1))
422 : {
423 86 : VSIFree(pszNewString);
424 0 : return *this;
425 : }
426 :
427 13043200 : papszList[nCount++] = pszNewString;
428 13043200 : papszList[nCount] = nullptr;
429 :
430 13043200 : bIsSorted = false;
431 :
432 13043200 : 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 4160910 : CPLStringList &CPLStringList::AddString(const char *pszNewString)
448 :
449 : {
450 4160910 : char *pszDupString = VSI_STRDUP_VERBOSE(pszNewString);
451 4160940 : if (pszDupString == nullptr)
452 0 : return *this;
453 4160940 : 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 27595 : CPLStringList &CPLStringList::AddString(const std::string &newString)
469 : {
470 27595 : return AddString(newString.c_str());
471 : }
472 :
473 : /************************************************************************/
474 : /* AddString() */
475 : /************************************************************************/
476 : /**
477 : * Add a string to the list.
478 : *
479 : * A copy of the passed in string_view is made and inserted in the list.
480 : *
481 : * @param newString the string to add to the list.
482 : * @return a reference to the CPLStringList on which it was invoked.
483 : */
484 :
485 3212840 : CPLStringList &CPLStringList::AddString(std::string_view newString)
486 : {
487 : char *pszDupString =
488 3212840 : static_cast<char *>(VSI_MALLOC_VERBOSE(newString.size() + 1));
489 3212820 : if (pszDupString == nullptr)
490 : {
491 0 : return *this;
492 : }
493 3212820 : std::memcpy(pszDupString, newString.data(), newString.size());
494 3212810 : pszDupString[newString.size()] = '\0';
495 :
496 3212820 : return AddStringDirectly(pszDupString);
497 : }
498 :
499 : /************************************************************************/
500 : /* push_back() */
501 : /************************************************************************/
502 :
503 : /**
504 : * Add a string to the list.
505 : *
506 : * A copy of the passed in string is made and inserted in the list.
507 : *
508 : * @param svStr the string to add to the list.
509 : *
510 : * @since 3.13
511 : */
512 :
513 92 : void CPLStringList::push_back(std::string_view svStr)
514 :
515 : {
516 : char *pszDupString =
517 92 : static_cast<char *>(VSI_MALLOC_VERBOSE(svStr.size() + 1));
518 92 : if (pszDupString == nullptr)
519 0 : return;
520 92 : memcpy(pszDupString, svStr.data(), svStr.size());
521 92 : pszDupString[svStr.size()] = 0;
522 92 : CPL_IGNORE_RET_VAL(AddStringDirectly(pszDupString));
523 : }
524 :
525 : /************************************************************************/
526 : /* AddNameValue() */
527 : /************************************************************************/
528 :
529 : /**
530 : * Add a name=value entry to the list.
531 : *
532 : * A key=value string is prepared and appended to the list. There is no
533 : * check for other values for the same key in the list.
534 : *
535 : * @param pszKey the key name to add.
536 : * @param pszValue the key value to add.
537 : */
538 :
539 5778970 : CPLStringList &CPLStringList::AddNameValue(const char *pszKey,
540 : const char *pszValue)
541 :
542 : {
543 5778970 : if (pszKey == nullptr || pszValue == nullptr)
544 144933 : return *this;
545 :
546 5634040 : if (!MakeOurOwnCopy())
547 0 : return *this;
548 :
549 : /* -------------------------------------------------------------------- */
550 : /* Format the line. */
551 : /* -------------------------------------------------------------------- */
552 11268300 : if (strlen(pszKey) >
553 11268400 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
554 5634350 : strlen(pszKey) + strlen(pszValue) >
555 5634350 : std::numeric_limits<size_t>::max() - 2)
556 : {
557 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
558 : "Too big strings in AddNameValue()");
559 0 : return *this;
560 : }
561 5634070 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
562 5634070 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
563 5634210 : if (pszLine == nullptr)
564 0 : return *this;
565 5634210 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
566 :
567 : /* -------------------------------------------------------------------- */
568 : /* If we don't need to keep the sort order things are pretty */
569 : /* straight forward. */
570 : /* -------------------------------------------------------------------- */
571 5634210 : if (!IsSorted())
572 5626890 : return AddStringDirectly(pszLine);
573 :
574 : /* -------------------------------------------------------------------- */
575 : /* Find the proper insertion point. */
576 : /* -------------------------------------------------------------------- */
577 7332 : CPLAssert(IsSorted());
578 7304 : const int iKey = FindSortedInsertionPoint(pszLine);
579 7304 : InsertStringDirectly(iKey, pszLine);
580 7304 : bIsSorted = true; // We have actually preserved sort order.
581 :
582 7304 : return *this;
583 : }
584 :
585 : /************************************************************************/
586 : /* SetNameValue() */
587 : /************************************************************************/
588 :
589 : /**
590 : * Set name=value entry in the list.
591 : *
592 : * Similar to AddNameValue(), except if there is already a value for
593 : * the key in the list it is replaced instead of adding a new entry to
594 : * the list. If pszValue is NULL any existing key entry is removed.
595 : *
596 : * @param pszKey the key name to add.
597 : * @param pszValue the key value to add.
598 : */
599 :
600 5871420 : CPLStringList &CPLStringList::SetNameValue(const char *pszKey,
601 : const char *pszValue)
602 :
603 : {
604 5871420 : int iKey = FindName(pszKey);
605 :
606 5871400 : if (iKey == -1)
607 5742320 : return AddNameValue(pszKey, pszValue);
608 :
609 129081 : Count();
610 128819 : if (!MakeOurOwnCopy())
611 0 : return *this;
612 :
613 128819 : CPLFree(papszList[iKey]);
614 128819 : if (pszValue == nullptr) // delete entry
615 : {
616 :
617 : // shift everything down by one.
618 930 : do
619 : {
620 3598 : papszList[iKey] = papszList[iKey + 1];
621 3598 : } while (papszList[iKey++] != nullptr);
622 :
623 2668 : nCount--;
624 : }
625 : else
626 : {
627 252302 : if (strlen(pszKey) >
628 252302 : std::numeric_limits<size_t>::max() - strlen(pszValue) ||
629 126151 : strlen(pszKey) + strlen(pszValue) >
630 126151 : std::numeric_limits<size_t>::max() - 2)
631 : {
632 0 : CPLError(CE_Failure, CPLE_OutOfMemory,
633 : "Too big strings in AddNameValue()");
634 0 : return *this;
635 : }
636 126151 : const size_t nLen = strlen(pszKey) + strlen(pszValue) + 2;
637 126151 : char *pszLine = static_cast<char *>(VSI_MALLOC_VERBOSE(nLen));
638 126151 : if (pszLine == nullptr)
639 0 : return *this;
640 126151 : snprintf(pszLine, nLen, "%s=%s", pszKey, pszValue);
641 :
642 126151 : papszList[iKey] = pszLine;
643 : }
644 :
645 128819 : return *this;
646 : }
647 :
648 : /************************************************************************/
649 : /* SetString() */
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 (will be copied)
657 : * @return a reference to the CPLStringList on which it was invoked.
658 : * @since 3.13
659 : */
660 6 : CPLStringList &CPLStringList::SetString(int pos, const char *pszString)
661 : {
662 6 : return SetStringDirectly(pos, VSI_STRDUP_VERBOSE(pszString));
663 : }
664 :
665 : /**
666 : * Replace a string within the list.
667 : *
668 : * @param pos 0-index position of the string to replace
669 : * @param osString value to be used (will be copied)
670 : * @return a reference to the CPLStringList on which it was invoked.
671 : * @since 3.13
672 : */
673 1 : CPLStringList &CPLStringList::SetString(int pos, const std::string &osString)
674 : {
675 1 : return SetString(pos, osString.c_str());
676 : }
677 :
678 : /**
679 : * Replace a string within the list.
680 : *
681 : * @param pos 0-index position of the string to replace
682 : * @param pszString value to be used (ownership is taken)
683 : * @return a reference to the CPLStringList on which it was invoked.
684 : * @since 3.13
685 : */
686 6 : CPLStringList &CPLStringList::SetStringDirectly(int pos, char *pszString)
687 : {
688 6 : if (!MakeOurOwnCopy())
689 0 : return *this;
690 :
691 6 : CPLFree(papszList[pos]);
692 6 : papszList[pos] = pszString;
693 :
694 6 : if (bIsSorted)
695 : {
696 8 : if (pos > 0 &&
697 2 : CPLCompareKeyValueString(papszList[pos], papszList[pos - 1]) == -1)
698 : {
699 0 : bIsSorted = false;
700 : }
701 11 : if (pos < Count() - 1 &&
702 5 : CPLCompareKeyValueString(papszList[pos], papszList[pos + 1]) == 1)
703 : {
704 3 : bIsSorted = false;
705 : }
706 : }
707 :
708 6 : return *this;
709 : }
710 :
711 : /************************************************************************/
712 : /* operator[] */
713 : /************************************************************************/
714 :
715 : /**
716 : * Fetch entry "i".
717 : *
718 : * Fetches the requested item in the list. Note that the returned string
719 : * remains owned by the CPLStringList. If "i" is out of range NULL is
720 : * returned.
721 : *
722 : * @param i the index of the list item to return.
723 : * @return selected entry in the list.
724 : */
725 1507660 : char *CPLStringList::operator[](int i)
726 :
727 : {
728 1507660 : if (nCount == -1)
729 282 : Count();
730 :
731 1507660 : if (i < 0 || i >= nCount)
732 50 : return nullptr;
733 :
734 1507610 : return papszList[i];
735 : }
736 :
737 807350 : const char *CPLStringList::operator[](int i) const
738 :
739 : {
740 807350 : if (nCount == -1)
741 743 : Count();
742 :
743 807345 : if (i < 0 || i >= nCount)
744 2 : return nullptr;
745 :
746 807343 : return papszList[i];
747 : }
748 :
749 : /************************************************************************/
750 : /* StealList() */
751 : /************************************************************************/
752 :
753 : /**
754 : * Seize ownership of underlying string array.
755 : *
756 : * This method is similar to List(), except that the returned list is
757 : * now owned by the caller and the CPLStringList is emptied.
758 : *
759 : * @return the C style string list.
760 : */
761 3488060 : char **CPLStringList::StealList()
762 :
763 : {
764 3488060 : char **papszRetList = papszList;
765 :
766 3488060 : bOwnList = false;
767 3488060 : papszList = nullptr;
768 3488060 : nCount = 0;
769 3488060 : nAllocation = 0;
770 :
771 3488060 : return papszRetList;
772 : }
773 :
774 : /* Case insensitive comparison function */
775 916906 : static int CPLCompareKeyValueString(const char *pszKVa, const char *pszKVb)
776 : {
777 916906 : const char *pszItera = pszKVa;
778 916906 : const char *pszIterb = pszKVb;
779 : while (true)
780 : {
781 6240420 : char cha = *pszItera;
782 6240420 : char chb = *pszIterb;
783 6240420 : if (cha == '=' || cha == '\0')
784 : {
785 4293 : if (chb == '=' || chb == '\0')
786 2 : return 0;
787 : else
788 4291 : return -1;
789 : }
790 6236130 : if (chb == '=' || chb == '\0')
791 : {
792 9544 : return 1;
793 : }
794 6226590 : if (cha >= 'a' && cha <= 'z')
795 529851 : cha -= ('a' - 'A');
796 6226590 : if (chb >= 'a' && chb <= 'z')
797 531144 : chb -= ('a' - 'A');
798 6226590 : if (cha < chb)
799 532665 : return -1;
800 5693920 : else if (cha > chb)
801 370404 : return 1;
802 5323520 : pszItera++;
803 5323520 : pszIterb++;
804 5323520 : }
805 : }
806 :
807 : /************************************************************************/
808 : /* Sort() */
809 : /************************************************************************/
810 :
811 : /**
812 : * Sort the entries in the list and mark list sorted.
813 : *
814 : * Note that once put into "sorted" mode, the CPLStringList will attempt to
815 : * keep things in sorted order through calls to AddString(),
816 : * AddStringDirectly(), AddNameValue(), SetNameValue(). Complete list
817 : * assignments (via Assign() and operator= will clear the sorting state.
818 : * When in sorted order FindName(), FetchNameValue() and FetchNameValueDef()
819 : * will do a binary search to find the key, substantially improve lookup
820 : * performance in large lists.
821 : */
822 :
823 101175 : CPLStringList &CPLStringList::Sort()
824 :
825 : {
826 101175 : Count();
827 101176 : if (!MakeOurOwnCopy())
828 0 : return *this;
829 :
830 101175 : if (nCount > 1)
831 : {
832 6366 : std::sort(papszList, papszList + nCount,
833 858718 : [](const char *a, const char *b)
834 858718 : { return CPLCompareKeyValueString(a, b) < 0; });
835 : }
836 101176 : bIsSorted = true;
837 :
838 101176 : return *this;
839 : }
840 :
841 : /************************************************************************/
842 : /* FindName() */
843 : /************************************************************************/
844 :
845 : /**
846 : * Get index of given name/value keyword.
847 : *
848 : * Note that this search is for a line in the form name=value or name:value.
849 : * Use FindString() or PartialFindString() for searches not based on name=value
850 : * pairs.
851 : *
852 : * @param pszKey the name to search for.
853 : *
854 : * @return the string list index of this name, or -1 on failure.
855 : */
856 :
857 18282000 : int CPLStringList::FindName(const char *pszKey) const
858 :
859 : {
860 18282000 : if (!IsSorted())
861 18259200 : return CSLFindName(papszList, pszKey);
862 :
863 : // If we are sorted, we can do an optimized binary search.
864 22730 : int iStart = 0;
865 22730 : int iEnd = nCount - 1;
866 22730 : size_t nKeyLen = strlen(pszKey);
867 :
868 58530 : while (iStart <= iEnd)
869 : {
870 43215 : const int iMiddle = (iEnd + iStart) / 2;
871 43215 : const char *pszMiddle = papszList[iMiddle];
872 :
873 43215 : if (EQUALN(pszMiddle, pszKey, nKeyLen) &&
874 7884 : (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':'))
875 7415 : return iMiddle;
876 :
877 35800 : if (CPLCompareKeyValueString(pszKey, pszMiddle) < 0)
878 9348 : iEnd = iMiddle - 1;
879 : else
880 26452 : iStart = iMiddle + 1;
881 : }
882 :
883 15315 : return -1;
884 : }
885 :
886 : /************************************************************************/
887 : /* FetchBool() */
888 : /************************************************************************/
889 : /**
890 : *
891 : * Check for boolean key value.
892 : *
893 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
894 : * with the given name, and if it can be interpreted as being TRUE. If
895 : * the key appears without any "=Value" portion it will be considered true.
896 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
897 : * if the key appears in the list it will be considered TRUE. If the key
898 : * doesn't appear at all, the indicated default value will be returned.
899 : *
900 : * @param pszKey the key value to look for (case insensitive).
901 : * @param bDefault the value to return if the key isn't found at all.
902 : *
903 : * @return true or false
904 : */
905 :
906 16081 : bool CPLStringList::FetchBool(const char *pszKey, bool bDefault) const
907 :
908 : {
909 16081 : const char *pszValue = FetchNameValue(pszKey);
910 :
911 16082 : if (pszValue == nullptr)
912 15793 : return bDefault;
913 :
914 289 : return CPLTestBool(pszValue);
915 : }
916 :
917 : /************************************************************************/
918 : /* FetchBoolean() */
919 : /************************************************************************/
920 : /**
921 : *
922 : * DEPRECATED: Check for boolean key value.
923 : *
924 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
925 : * with the given name, and if it can be interpreted as being TRUE. If
926 : * the key appears without any "=Value" portion it will be considered true.
927 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
928 : * if the key appears in the list it will be considered TRUE. If the key
929 : * doesn't appear at all, the indicated default value will be returned.
930 : *
931 : * @param pszKey the key value to look for (case insensitive).
932 : * @param bDefault the value to return if the key isn't found at all.
933 : *
934 : * @return TRUE or FALSE
935 : */
936 :
937 2985 : int CPLStringList::FetchBoolean(const char *pszKey, int bDefault) const
938 :
939 : {
940 2985 : return FetchBool(pszKey, CPL_TO_BOOL(bDefault)) ? TRUE : FALSE;
941 : }
942 :
943 : /************************************************************************/
944 : /* FetchNameValue() */
945 : /************************************************************************/
946 :
947 : /**
948 : * Fetch value associated with this key name.
949 : *
950 : * If this list sorted, a fast binary search is done, otherwise a linear
951 : * scan is done. Name lookup is case insensitive.
952 : *
953 : * @param pszName the key name to search for.
954 : *
955 : * @return the corresponding value or NULL if not found. The returned string
956 : * should not be modified and points into internal object state that may
957 : * change on future calls.
958 : */
959 :
960 12411300 : const char *CPLStringList::FetchNameValue(const char *pszName) const
961 :
962 : {
963 12411300 : const int iKey = FindName(pszName);
964 :
965 12411000 : if (iKey == -1)
966 4758540 : return nullptr;
967 :
968 7652420 : CPLAssert(papszList[iKey][strlen(pszName)] == '=' ||
969 : papszList[iKey][strlen(pszName)] == ':');
970 :
971 7652420 : return papszList[iKey] + strlen(pszName) + 1;
972 : }
973 :
974 : /************************************************************************/
975 : /* FetchNameValueDef() */
976 : /************************************************************************/
977 :
978 : /**
979 : * Fetch value associated with this key name.
980 : *
981 : * If this list sorted, a fast binary search is done, otherwise a linear
982 : * scan is done. Name lookup is case insensitive.
983 : *
984 : * @param pszName the key name to search for.
985 : * @param pszDefault the default value returned if the named entry isn't found.
986 : *
987 : * @return the corresponding value or the passed default if not found.
988 : */
989 :
990 49523 : const char *CPLStringList::FetchNameValueDef(const char *pszName,
991 : const char *pszDefault) const
992 :
993 : {
994 49523 : const char *pszValue = FetchNameValue(pszName);
995 49523 : if (pszValue == nullptr)
996 35015 : return pszDefault;
997 :
998 14508 : return pszValue;
999 : }
1000 :
1001 : /************************************************************************/
1002 : /* InsertString() */
1003 : /************************************************************************/
1004 :
1005 : /**
1006 : * \fn CPLStringList *CPLStringList::InsertString( int nInsertAtLineNo,
1007 : * const char *pszNewLine );
1008 : *
1009 : * \brief Insert into the list at identified location.
1010 : *
1011 : * This method will insert a string into the list at the identified
1012 : * location. The insertion point must be within or at the end of the list.
1013 : * The following entries are pushed down to make space.
1014 : *
1015 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
1016 : * @param pszNewLine to the line to insert. This string will be copied.
1017 : */
1018 :
1019 : /************************************************************************/
1020 : /* InsertStringDirectly() */
1021 : /************************************************************************/
1022 :
1023 : /**
1024 : * Insert into the list at identified location.
1025 : *
1026 : * This method will insert a string into the list at the identified
1027 : * location. The insertion point must be within or at the end of the list.
1028 : * The following entries are pushed down to make space.
1029 : *
1030 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
1031 : * @param pszNewLine to the line to insert, the ownership of this string
1032 : * will be taken over the by the object. It must have been allocated on the
1033 : * heap.
1034 : */
1035 :
1036 7700 : CPLStringList &CPLStringList::InsertStringDirectly(int nInsertAtLineNo,
1037 : char *pszNewLine)
1038 :
1039 : {
1040 7700 : if (nCount == -1)
1041 27 : Count();
1042 :
1043 7700 : if (!EnsureAllocation(nCount + 1))
1044 : {
1045 0 : VSIFree(pszNewLine);
1046 0 : return *this;
1047 : }
1048 :
1049 7700 : if (nInsertAtLineNo < 0 || nInsertAtLineNo > nCount)
1050 : {
1051 0 : CPLError(CE_Failure, CPLE_AppDefined,
1052 : "CPLStringList::InsertString() requested beyond list end.");
1053 0 : return *this;
1054 : }
1055 :
1056 7700 : bIsSorted = false;
1057 :
1058 24108 : for (int i = nCount; i > nInsertAtLineNo; i--)
1059 16408 : papszList[i] = papszList[i - 1];
1060 :
1061 7700 : papszList[nInsertAtLineNo] = pszNewLine;
1062 7700 : papszList[++nCount] = nullptr;
1063 :
1064 7700 : return *this;
1065 : }
1066 :
1067 : /************************************************************************/
1068 : /* RemoveStrings() */
1069 : /************************************************************************/
1070 :
1071 : /**
1072 : * Remove strings inside a CPLStringList.
1073 : *
1074 : * @param nFirstLineToDelete the 0-based index of the first string to
1075 : * remove. If this value is -1 or is larger than the actual
1076 : * number of strings in list then the nNumToRemove last strings are
1077 : * removed.
1078 : * @param nNumToRemove the number of strings to remove
1079 : *
1080 : * @return a reference to the CPLStringList on which it was invoked.
1081 : * @since 3.13
1082 : */
1083 3 : CPLStringList &CPLStringList::RemoveStrings(int nFirstLineToDelete,
1084 : int nNumToRemove)
1085 : {
1086 3 : if (!MakeOurOwnCopy())
1087 0 : return *this;
1088 :
1089 3 : papszList =
1090 3 : CSLRemoveStrings(papszList, nFirstLineToDelete, nNumToRemove, nullptr);
1091 3 : nCount = -1;
1092 3 : return *this;
1093 : }
1094 :
1095 : /************************************************************************/
1096 : /* FindSortedInsertionPoint() */
1097 : /* */
1098 : /* Find the location at which the indicated line should be */
1099 : /* inserted in order to keep things in sorted order. */
1100 : /************************************************************************/
1101 :
1102 7304 : int CPLStringList::FindSortedInsertionPoint(const char *pszLine)
1103 :
1104 : {
1105 7304 : CPLAssert(IsSorted());
1106 :
1107 7304 : int iStart = 0;
1108 7304 : int iEnd = nCount - 1;
1109 :
1110 23554 : while (iStart <= iEnd)
1111 : {
1112 16250 : const int iMiddle = (iEnd + iStart) / 2;
1113 16250 : const char *pszMiddle = papszList[iMiddle];
1114 :
1115 16250 : if (CPLCompareKeyValueString(pszLine, pszMiddle) < 0)
1116 2411 : iEnd = iMiddle - 1;
1117 : else
1118 13839 : iStart = iMiddle + 1;
1119 : }
1120 :
1121 7304 : iEnd++;
1122 7304 : CPLAssert(iEnd >= 0 && iEnd <= nCount);
1123 7304 : CPLAssert(iEnd == 0 ||
1124 : CPLCompareKeyValueString(pszLine, papszList[iEnd - 1]) >= 0);
1125 7304 : CPLAssert(iEnd == nCount ||
1126 : CPLCompareKeyValueString(pszLine, papszList[iEnd]) <= 0);
1127 :
1128 7304 : return iEnd;
1129 : }
1130 :
1131 : namespace cpl
1132 : {
1133 :
1134 : /************************************************************************/
1135 : /* CSLIterator::operator==(const CSLIterator &other) */
1136 : /************************************************************************/
1137 :
1138 : /*! @cond Doxygen_Suppress */
1139 22917200 : bool CSLIterator::operator==(const CSLIterator &other) const
1140 : {
1141 22917200 : if (!m_bAtEnd && other.m_bAtEnd)
1142 : {
1143 22917200 : return m_papszList == nullptr || *m_papszList == nullptr;
1144 : }
1145 0 : if (!m_bAtEnd && !other.m_bAtEnd)
1146 : {
1147 0 : return m_papszList == other.m_papszList;
1148 : }
1149 0 : if (m_bAtEnd && other.m_bAtEnd)
1150 : {
1151 0 : return true;
1152 : }
1153 0 : return false;
1154 : }
1155 :
1156 : /*! @endcond */
1157 :
1158 : /************************************************************************/
1159 : /* CSLNameValueIterator::operator*() */
1160 : /************************************************************************/
1161 :
1162 : /*! @cond Doxygen_Suppress */
1163 8374 : CSLNameValueIterator::value_type CSLNameValueIterator::operator*()
1164 : {
1165 8374 : if (m_papszList)
1166 : {
1167 8375 : while (*m_papszList)
1168 : {
1169 8375 : char *pszKey = nullptr;
1170 8375 : const char *pszValue = CPLParseNameValue(*m_papszList, &pszKey);
1171 8375 : if (pszKey)
1172 : {
1173 8372 : m_osKey = pszKey;
1174 8372 : CPLFree(pszKey);
1175 8372 : return {m_osKey.c_str(), pszValue};
1176 : }
1177 3 : else if (m_bReturnNullKeyIfNotNameValue)
1178 : {
1179 2 : return {nullptr, *m_papszList};
1180 : }
1181 : // Skip entries that are not name=value pairs.
1182 1 : ++m_papszList;
1183 : }
1184 : }
1185 : // Should not happen
1186 0 : CPLAssert(false);
1187 : return {"", ""};
1188 : }
1189 :
1190 : /*! @endcond */
1191 :
1192 : /************************************************************************/
1193 : /* CSLNameValueIteratorWrapper::end() */
1194 : /************************************************************************/
1195 :
1196 : /*! @cond Doxygen_Suppress */
1197 13615 : CSLNameValueIterator CSLNameValueIteratorWrapper::end() const
1198 : {
1199 13615 : int nCount = CSLCount(m_papszList);
1200 13615 : if (!m_bReturnNullKeyIfNotNameValue)
1201 : {
1202 13512 : while (nCount > 0 && strchr(m_papszList[nCount - 1], '=') == nullptr)
1203 12 : --nCount;
1204 : }
1205 13615 : return CSLNameValueIterator{m_papszList + nCount,
1206 13615 : m_bReturnNullKeyIfNotNameValue};
1207 : }
1208 :
1209 : /*! @endcond */
1210 :
1211 : } // namespace cpl
|
