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