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 * Permission is hereby granted, free of charge, to any person obtaining a
12 * copy of this software and associated documentation files (the "Software"),
13 * to deal in the Software without restriction, including without limitation
14 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 * and/or sell copies of the Software, and to permit persons to whom the
16 * Software is furnished to do so, subject to the following conditions:
17 *
18 * The above copyright notice and this permission notice shall be included
19 * in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 * DEALINGS IN THE SOFTWARE.
28 ****************************************************************************/
29
30 #include "cpl_port.h"
31 #include "cpl_string.h"
32
33 #include <cstddef>
34 #include <cstdio>
35 #include <cstdlib>
36 #include <cstring>
37
38 #include <algorithm>
39 #include <string>
40
41 #include "cpl_conv.h"
42 #include "cpl_error.h"
43
44 CPL_CVSID("$Id: cplstringlist.cpp 237cce44e47cca3290bf053bbfa153856575017e 2019-08-17 15:01:52 +0200 Even Rouault $")
45
46 /************************************************************************/
47 /* CPLStringList() */
48 /************************************************************************/
49
50 CPLStringList::CPLStringList() = default;
51
52 /************************************************************************/
53 /* CPLStringList() */
54 /************************************************************************/
55
56 /**
57 * CPLStringList constructor.
58 *
59 * @param papszListIn the NULL terminated list of strings to consume.
60 * @param bTakeOwnership TRUE if the CPLStringList should take ownership
61 * of the list of strings which implies responsibility to free them.
62 */
63
CPLStringList(char ** papszListIn,int bTakeOwnership)64 CPLStringList::CPLStringList( char **papszListIn, int bTakeOwnership ):
65 CPLStringList()
66
67 {
68 Assign( papszListIn, bTakeOwnership );
69 }
70
71 /************************************************************************/
72 /* CPLStringList() */
73 /************************************************************************/
74
75 /**
76 * CPLStringList constructor.
77 *
78 * The input list is copied.
79 *
80 * @param papszListIn the NULL terminated list of strings to ingest.
81 */
82
CPLStringList(CSLConstList papszListIn)83 CPLStringList::CPLStringList( CSLConstList papszListIn ):
84 CPLStringList()
85
86 {
87 Assign( CSLDuplicate(papszListIn) );
88 }
89
90 /************************************************************************/
91 /* CPLStringList() */
92 /************************************************************************/
93
94 //! Copy constructor
CPLStringList(const CPLStringList & oOther)95 CPLStringList::CPLStringList( const CPLStringList &oOther ):
96 CPLStringList()
97
98 {
99 Assign( oOther.papszList, FALSE );
100
101 // We don't want to just retain a reference to the others list
102 // as we don't want to make assumptions about its lifetime that
103 // might surprise the client developer.
104 MakeOurOwnCopy();
105 bIsSorted = oOther.bIsSorted;
106 }
107
108 /************************************************************************/
109 /* operator=() */
110 /************************************************************************/
111
operator =(const CPLStringList & oOther)112 CPLStringList &CPLStringList::operator=( const CPLStringList& oOther )
113 {
114 if( this != &oOther )
115 {
116 Assign( oOther.papszList, FALSE );
117
118 // We don't want to just retain a reference to the others list
119 // as we don't want to make assumptions about its lifetime that
120 // might surprise the client developer.
121 MakeOurOwnCopy();
122 bIsSorted = oOther.bIsSorted;
123 }
124
125 return *this;
126 }
127
128 /************************************************************************/
129 /* operator=() */
130 /************************************************************************/
131
operator =(CPLStringList && oOther)132 CPLStringList &CPLStringList::operator=( CPLStringList&& oOther )
133 {
134 if( this != &oOther )
135 {
136 Clear();
137 papszList = oOther.papszList;
138 oOther.papszList = nullptr;
139 nCount = oOther.nCount;
140 oOther.nCount = 0;
141 nAllocation = oOther.nAllocation;
142 oOther.nAllocation = 0;
143 bOwnList = oOther.bOwnList;
144 oOther.bOwnList = false;
145 bIsSorted = oOther.bIsSorted;
146 oOther.bIsSorted = true;
147 }
148
149 return *this;
150 }
151
152 /************************************************************************/
153 /* operator=() */
154 /************************************************************************/
155
operator =(CSLConstList papszListIn)156 CPLStringList &CPLStringList::operator=( CSLConstList papszListIn )
157 {
158 if( papszListIn != papszList )
159 {
160 Assign( CSLDuplicate(papszListIn) );
161 bIsSorted = false;
162 }
163
164 return *this;
165 }
166
167 /************************************************************************/
168 /* ~CPLStringList() */
169 /************************************************************************/
170
~CPLStringList()171 CPLStringList::~CPLStringList()
172
173 {
174 Clear();
175 }
176
177 /************************************************************************/
178 /* Clear() */
179 /************************************************************************/
180
181 /**
182 * Clear the string list.
183 */
Clear()184 CPLStringList &CPLStringList::Clear()
185
186 {
187 if( bOwnList )
188 {
189 CSLDestroy( papszList );
190 papszList = nullptr;
191
192 bOwnList = FALSE;
193 nAllocation = 0;
194 nCount = 0;
195 }
196
197 return *this;
198 }
199
200 /************************************************************************/
201 /* Assign() */
202 /************************************************************************/
203
204 /**
205 * Assign a list of strings.
206 *
207 *
208 * @param papszListIn the NULL terminated list of strings to consume.
209 * @param bTakeOwnership TRUE if the CPLStringList should take ownership
210 * of the list of strings which implies responsibility to free them.
211 *
212 * @return a reference to the CPLStringList on which it was invoked.
213 */
214
Assign(char ** papszListIn,int bTakeOwnership)215 CPLStringList &CPLStringList::Assign( char **papszListIn, int bTakeOwnership )
216
217 {
218 Clear();
219
220 papszList = papszListIn;
221 bOwnList = CPL_TO_BOOL(bTakeOwnership);
222
223 if( papszList == nullptr || *papszList == nullptr )
224 nCount = 0;
225 else
226 nCount = -1; // unknown
227
228 nAllocation = 0;
229 bIsSorted = FALSE;
230
231 return *this;
232 }
233
234 /************************************************************************/
235 /* Count() */
236 /************************************************************************/
237
238 /**
239 * @return count of strings in the list, zero if empty.
240 */
241
Count() const242 int CPLStringList::Count() const
243
244 {
245 if( nCount == -1 )
246 {
247 if( papszList == nullptr )
248 {
249 nCount = 0;
250 nAllocation = 0;
251 }
252 else
253 {
254 nCount = CSLCount( papszList );
255 nAllocation = std::max(nCount + 1, nAllocation);
256 }
257 }
258
259 return nCount;
260 }
261
262 /************************************************************************/
263 /* MakeOurOwnCopy() */
264 /* */
265 /* If we don't own the list, a copy is made which we own. */
266 /* Necessary if we are going to modify the list. */
267 /************************************************************************/
268
MakeOurOwnCopy()269 void CPLStringList::MakeOurOwnCopy()
270
271 {
272 if( bOwnList )
273 return;
274
275 if( papszList == nullptr )
276 return;
277
278 Count();
279 bOwnList = true;
280 papszList = CSLDuplicate( papszList );
281 nAllocation = nCount+1;
282 }
283
284 /************************************************************************/
285 /* EnsureAllocation() */
286 /* */
287 /* Ensure we have enough room allocated for at least the */
288 /* requested number of strings (so nAllocation will be at least */
289 /* one more than the target) */
290 /************************************************************************/
291
EnsureAllocation(int nMaxList)292 void CPLStringList::EnsureAllocation( int nMaxList )
293
294 {
295 if( !bOwnList )
296 MakeOurOwnCopy();
297
298 if( nAllocation <= nMaxList )
299 {
300 nAllocation = std::max(nAllocation * 2 + 20, nMaxList + 1);
301 if( papszList == nullptr )
302 {
303 papszList = static_cast<char **>(
304 CPLCalloc(nAllocation, sizeof(char*)) );
305 bOwnList = true;
306 nCount = 0;
307 }
308 else
309 {
310 papszList = static_cast<char **>(
311 CPLRealloc(papszList, nAllocation*sizeof(char*)) );
312 }
313 }
314 }
315
316 /************************************************************************/
317 /* AddStringDirectly() */
318 /************************************************************************/
319
320 /**
321 * Add a string to the list.
322 *
323 * This method is similar to AddString(), but ownership of the
324 * pszNewString is transferred to the CPLStringList class.
325 *
326 * @param pszNewString the string to add to the list.
327 */
328
AddStringDirectly(char * pszNewString)329 CPLStringList &CPLStringList::AddStringDirectly( char *pszNewString )
330
331 {
332 if( nCount == -1 )
333 Count();
334
335 EnsureAllocation( nCount+1 );
336
337 papszList[nCount++] = pszNewString;
338 papszList[nCount] = nullptr;
339
340 bIsSorted = false;
341
342 return *this;
343 }
344
345 /************************************************************************/
346 /* AddString() */
347 /************************************************************************/
348
349 /**
350 * Add a string to the list.
351 *
352 * A copy of the passed in string is made and inserted in the list.
353 *
354 * @param pszNewString the string to add to the list.
355 */
356
AddString(const char * pszNewString)357 CPLStringList &CPLStringList::AddString( const char *pszNewString )
358
359 {
360 return AddStringDirectly( CPLStrdup( pszNewString ) );
361 }
362
363 /************************************************************************/
364 /* AddNameValue() */
365 /************************************************************************/
366
367 /**
368 * Add a name=value entry to the list.
369 *
370 * A key=value string is prepared and appended to the list. There is no
371 * check for other values for the same key in the list.
372 *
373 * @param pszKey the key name to add.
374 * @param pszValue the key value to add.
375 */
376
AddNameValue(const char * pszKey,const char * pszValue)377 CPLStringList &CPLStringList::AddNameValue( const char *pszKey,
378 const char *pszValue )
379
380 {
381 if( pszKey == nullptr || pszValue==nullptr )
382 return *this;
383
384 MakeOurOwnCopy();
385
386 /* -------------------------------------------------------------------- */
387 /* Format the line. */
388 /* -------------------------------------------------------------------- */
389 const size_t nLen = strlen(pszKey)+strlen(pszValue)+2;
390 char *pszLine = static_cast<char *>( CPLMalloc(nLen) );
391 snprintf( pszLine, nLen, "%s=%s", pszKey, pszValue );
392
393 /* -------------------------------------------------------------------- */
394 /* If we don't need to keep the sort order things are pretty */
395 /* straight forward. */
396 /* -------------------------------------------------------------------- */
397 if( !IsSorted() )
398 return AddStringDirectly( pszLine );
399
400 /* -------------------------------------------------------------------- */
401 /* Find the proper insertion point. */
402 /* -------------------------------------------------------------------- */
403 CPLAssert( IsSorted() );
404 const int iKey = FindSortedInsertionPoint( pszLine );
405 InsertStringDirectly( iKey, pszLine );
406 bIsSorted = true; // We have actually preserved sort order.
407
408 return *this;
409 }
410
411 /************************************************************************/
412 /* SetNameValue() */
413 /************************************************************************/
414
415 /**
416 * Set name=value entry in the list.
417 *
418 * Similar to AddNameValue(), except if there is already a value for
419 * the key in the list it is replaced instead of adding a new entry to
420 * the list. If pszValue is NULL any existing key entry is removed.
421 *
422 * @param pszKey the key name to add.
423 * @param pszValue the key value to add.
424 */
425
SetNameValue(const char * pszKey,const char * pszValue)426 CPLStringList &CPLStringList::SetNameValue( const char *pszKey,
427 const char *pszValue )
428
429 {
430 int iKey = FindName( pszKey );
431
432 if( iKey == -1 )
433 return AddNameValue( pszKey, pszValue );
434
435 Count();
436 MakeOurOwnCopy();
437
438 CPLFree( papszList[iKey] );
439 if( pszValue == nullptr ) // delete entry
440 {
441
442 // shift everything down by one.
443 do
444 {
445 papszList[iKey] = papszList[iKey+1];
446 }
447 while( papszList[iKey++] != nullptr );
448
449 nCount--;
450 }
451 else
452 {
453 const size_t nLen = strlen(pszKey)+strlen(pszValue)+2;
454 char *pszLine = static_cast<char *>( CPLMalloc(nLen) );
455 snprintf( pszLine, nLen, "%s=%s", pszKey, pszValue );
456
457 papszList[iKey] = pszLine;
458 }
459
460 return *this;
461 }
462
463 /************************************************************************/
464 /* operator[] */
465 /************************************************************************/
466
467 /**
468 * Fetch entry "i".
469 *
470 * Fetches the requested item in the list. Note that the returned string
471 * remains owned by the CPLStringList. If "i" is out of range NULL is
472 * returned.
473 *
474 * @param i the index of the list item to return.
475 * @return selected entry in the list.
476 */
operator [](int i)477 char *CPLStringList::operator[]( int i )
478
479 {
480 if( nCount == -1 )
481 Count();
482
483 if( i < 0 || i >= nCount )
484 return nullptr;
485
486 return papszList[i];
487 }
488
operator [](int i) const489 const char *CPLStringList::operator[]( int i ) const
490
491 {
492 if( nCount == -1 )
493 Count();
494
495 if( i < 0 || i >= nCount )
496 return nullptr;
497
498 return papszList[i];
499 }
500
501 /************************************************************************/
502 /* StealList() */
503 /************************************************************************/
504
505 /**
506 * Seize ownership of underlying string array.
507 *
508 * This method is similar to List(), except that the returned list is
509 * now owned by the caller and the CPLStringList is emptied.
510 *
511 * @return the C style string list.
512 */
StealList()513 char **CPLStringList::StealList()
514
515 {
516 char **papszRetList = papszList;
517
518 bOwnList = false;
519 papszList = nullptr;
520 nCount = 0;
521 nAllocation = 0;
522
523 return papszRetList;
524 }
525
CPLCompareKeyValueString(const char * pszKVa,const char * pszKVb)526 static int CPLCompareKeyValueString(const char* pszKVa, const char* pszKVb)
527 {
528 const char* pszItera = pszKVa;
529 const char* pszIterb = pszKVb;
530 while( true )
531 {
532 char cha = *pszItera;
533 char chb = *pszIterb;
534 if( cha == '=' || cha == '\0' )
535 {
536 if( chb == '=' || chb == '\0' )
537 return 0;
538 else
539 return -1;
540 }
541 if( chb == '=' || chb == '\0' )
542 {
543 return 1;
544 }
545 if( cha >= 'a' && cha <= 'z' )
546 cha -= ('a' - 'A');
547 if( chb >= 'a' && chb <= 'z' )
548 chb -= ('a' - 'A');
549 if( cha < chb )
550 return -1;
551 else if( cha > chb )
552 return 1;
553 pszItera++;
554 pszIterb++;
555 }
556 }
557
558 /************************************************************************/
559 /* llCompareStr() */
560 /* */
561 /* Note this is case insensitive! This is because we normally */
562 /* treat key value keywords as case insensitive. */
563 /************************************************************************/
llCompareStr(const void * a,const void * b)564 static int llCompareStr(const void *a, const void *b)
565 {
566 return CPLCompareKeyValueString(
567 *static_cast<const char **>(const_cast<void *>(a)),
568 *static_cast<const char **>(const_cast<void *>(b)) );
569 }
570
571 /************************************************************************/
572 /* Sort() */
573 /************************************************************************/
574
575 /**
576 * Sort the entries in the list and mark list sorted.
577 *
578 * Note that once put into "sorted" mode, the CPLStringList will attempt to
579 * keep things in sorted order through calls to AddString(),
580 * AddStringDirectly(), AddNameValue(), SetNameValue(). Complete list
581 * assignments (via Assign() and operator= will clear the sorting state.
582 * When in sorted order FindName(), FetchNameValue() and FetchNameValueDef()
583 * will do a binary search to find the key, substantially improve lookup
584 * performance in large lists.
585 */
586
Sort()587 CPLStringList &CPLStringList::Sort()
588
589 {
590 Count();
591 MakeOurOwnCopy();
592
593 if( nCount )
594 qsort( papszList, nCount, sizeof(char*), llCompareStr );
595 bIsSorted = true;
596
597 return *this;
598 }
599
600 /************************************************************************/
601 /* FindName() */
602 /************************************************************************/
603
604 /**
605 * Get index of given name/value keyword.
606 *
607 * Note that this search is for a line in the form name=value or name:value.
608 * Use FindString() or PartialFindString() for searches not based on name=value
609 * pairs.
610 *
611 * @param pszKey the name to search for.
612 *
613 * @return the string list index of this name, or -1 on failure.
614 */
615
FindName(const char * pszKey) const616 int CPLStringList::FindName( const char *pszKey ) const
617
618 {
619 if( !IsSorted() )
620 return CSLFindName( papszList, pszKey );
621
622 // If we are sorted, we can do an optimized binary search.
623 int iStart = 0;
624 int iEnd = nCount - 1;
625 size_t nKeyLen = strlen(pszKey);
626
627 while( iStart <= iEnd )
628 {
629 const int iMiddle = (iEnd + iStart) / 2;
630 const char *pszMiddle = papszList[iMiddle];
631
632 if( EQUALN(pszMiddle, pszKey, nKeyLen )
633 && (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':') )
634 return iMiddle;
635
636 if( CPLCompareKeyValueString(pszKey, pszMiddle) < 0 )
637 iEnd = iMiddle-1;
638 else
639 iStart = iMiddle+1;
640 }
641
642 return -1;
643 }
644
645 /************************************************************************/
646 /* FetchBool() */
647 /************************************************************************/
648 /**
649 *
650 * Check for boolean key value.
651 *
652 * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
653 * with the given name, and if it can be interpreted as being TRUE. If
654 * the key appears without any "=Value" portion it will be considered true.
655 * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
656 * if the key appears in the list it will be considered TRUE. If the key
657 * doesn't appear at all, the indicated default value will be returned.
658 *
659 * @param pszKey the key value to look for (case insensitive).
660 * @param bDefault the value to return if the key isn't found at all.
661 *
662 * @return true or false
663 */
664
FetchBool(const char * pszKey,bool bDefault) const665 bool CPLStringList::FetchBool( const char *pszKey, bool bDefault ) const
666
667 {
668 const char *pszValue = FetchNameValue( pszKey );
669
670 if( pszValue == nullptr )
671 return bDefault;
672
673 return CPLTestBool( pszValue );
674 }
675
676 /************************************************************************/
677 /* FetchBoolean() */
678 /************************************************************************/
679 /**
680 *
681 * DEPRECATED: Check for boolean key value.
682 *
683 * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
684 * with the given name, and if it can be interpreted as being TRUE. If
685 * the key appears without any "=Value" portion it will be considered true.
686 * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
687 * if the key appears in the list it will be considered TRUE. If the key
688 * doesn't appear at all, the indicated default value will be returned.
689 *
690 * @param pszKey the key value to look for (case insensitive).
691 * @param bDefault the value to return if the key isn't found at all.
692 *
693 * @return TRUE or FALSE
694 */
695
FetchBoolean(const char * pszKey,int bDefault) const696 int CPLStringList::FetchBoolean( const char *pszKey, int bDefault ) const
697
698 {
699 return FetchBool( pszKey, CPL_TO_BOOL(bDefault) ) ? TRUE : FALSE;
700 }
701
702 /************************************************************************/
703 /* FetchNameValue() */
704 /************************************************************************/
705
706 /**
707 * Fetch value associated with this key name.
708 *
709 * If this list sorted, a fast binary search is done, otherwise a linear
710 * scan is done. Name lookup is case insensitive.
711 *
712 * @param pszName the key name to search for.
713 *
714 * @return the corresponding value or NULL if not found. The returned string
715 * should not be modified and points into internal object state that may
716 * change on future calls.
717 */
718
FetchNameValue(const char * pszName) const719 const char *CPLStringList::FetchNameValue( const char *pszName ) const
720
721 {
722 const int iKey = FindName( pszName );
723
724 if( iKey == -1 )
725 return nullptr;
726
727 CPLAssert( papszList[iKey][strlen(pszName)] == '='
728 || papszList[iKey][strlen(pszName)] == ':' );
729
730 return papszList[iKey] + strlen(pszName)+1;
731 }
732
733 /************************************************************************/
734 /* FetchNameValueDef() */
735 /************************************************************************/
736
737 /**
738 * Fetch value associated with this key name.
739 *
740 * If this list sorted, a fast binary search is done, otherwise a linear
741 * scan is done. Name lookup is case insensitive.
742 *
743 * @param pszName the key name to search for.
744 * @param pszDefault the default value returned if the named entry isn't found.
745 *
746 * @return the corresponding value or the passed default if not found.
747 */
748
FetchNameValueDef(const char * pszName,const char * pszDefault) const749 const char *CPLStringList::FetchNameValueDef( const char *pszName,
750 const char *pszDefault ) const
751
752 {
753 const char *pszValue = FetchNameValue( pszName );
754 if( pszValue == nullptr )
755 return pszDefault;
756
757 return pszValue;
758 }
759
760 /************************************************************************/
761 /* InsertString() */
762 /************************************************************************/
763
764 /**
765 * \fn CPLStringList *CPLStringList::InsertString( int nInsertAtLineNo,
766 * const char *pszNewLine );
767 *
768 * \brief Insert into the list at identified location.
769 *
770 * This method will insert a string into the list at the identified
771 * location. The insertion point must be within or at the end of the list.
772 * The following entries are pushed down to make space.
773 *
774 * @param nInsertAtLineNo the line to insert at, zero to insert at front.
775 * @param pszNewLine to the line to insert. This string will be copied.
776 */
777
778 /************************************************************************/
779 /* InsertStringDirectly() */
780 /************************************************************************/
781
782 /**
783 * Insert into the list at identified location.
784 *
785 * This method will insert a string into the list at the identified
786 * location. The insertion point must be within or at the end of the list.
787 * The following entries are pushed down to make space.
788 *
789 * @param nInsertAtLineNo the line to insert at, zero to insert at front.
790 * @param pszNewLine to the line to insert, the ownership of this string
791 * will be taken over the by the object. It must have been allocated on the
792 * heap.
793 */
794
InsertStringDirectly(int nInsertAtLineNo,char * pszNewLine)795 CPLStringList &CPLStringList::InsertStringDirectly( int nInsertAtLineNo,
796 char *pszNewLine )
797
798 {
799 if( nCount == -1 )
800 Count();
801
802 EnsureAllocation( nCount+1 );
803
804 if( nInsertAtLineNo < 0 || nInsertAtLineNo > nCount )
805 {
806 CPLError( CE_Failure, CPLE_AppDefined,
807 "CPLStringList::InsertString() requested beyond list end." );
808 return *this;
809 }
810
811 bIsSorted = false;
812
813 for( int i = nCount; i > nInsertAtLineNo; i-- )
814 papszList[i] = papszList[i-1];
815
816 papszList[nInsertAtLineNo] = pszNewLine;
817 papszList[++nCount] = nullptr;
818
819 return *this;
820 }
821
822 /************************************************************************/
823 /* FindSortedInsertionPoint() */
824 /* */
825 /* Find the location at which the indicated line should be */
826 /* inserted in order to keep things in sorted order. */
827 /************************************************************************/
828
FindSortedInsertionPoint(const char * pszLine)829 int CPLStringList::FindSortedInsertionPoint( const char *pszLine )
830
831 {
832 CPLAssert( IsSorted() );
833
834 int iStart = 0;
835 int iEnd = nCount - 1;
836
837 while( iStart <= iEnd )
838 {
839 const int iMiddle = (iEnd + iStart) / 2;
840 const char *pszMiddle = papszList[iMiddle];
841
842 if( CPLCompareKeyValueString(pszLine, pszMiddle) < 0 )
843 iEnd = iMiddle - 1;
844 else
845 iStart = iMiddle + 1;
846 }
847
848 iEnd++;
849 CPLAssert( iEnd >= 0 && iEnd <= nCount );
850 CPLAssert( iEnd == 0
851 || CPLCompareKeyValueString(pszLine, papszList[iEnd-1]) >= 0 );
852 CPLAssert( iEnd == nCount
853 || CPLCompareKeyValueString(pszLine, papszList[iEnd]) <= 0 );
854
855 return iEnd;
856 }
857