1 : /******************************************************************************
2 : * $Id: cplstringlist.cpp 23043 2011-09-04 15:28:19Z rouault $
3 : *
4 : * Project: GDAL
5 : * Purpose: CPLStringList implementation.
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 2011, Frank Warmerdam <warmerdam@pobox.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_string.h"
31 : #include <string>
32 :
33 : CPL_CVSID("$Id: cplstringlist.cpp 23043 2011-09-04 15:28:19Z rouault $");
34 :
35 : /************************************************************************/
36 : /* CPLStringList() */
37 : /************************************************************************/
38 :
39 1524223 : CPLStringList::CPLStringList()
40 :
41 : {
42 1524223 : Initialize();
43 1524223 : }
44 :
45 : /************************************************************************/
46 : /* CPLStringList() */
47 : /************************************************************************/
48 :
49 : /**
50 : * CPLStringList constructor.
51 : *
52 : * @param papszListIn the NULL terminated list of strings to consume.
53 : * @param bTakeOwnership TRUE if the CPLStringList should take ownership
54 : * of the list of strings which implies responsibility to free them.
55 : */
56 :
57 0 : CPLStringList::CPLStringList( char **papszListIn, int bTakeOwnership )
58 :
59 : {
60 0 : Initialize();
61 0 : Assign( papszListIn, bTakeOwnership );
62 0 : }
63 :
64 : /************************************************************************/
65 : /* CPLStringList() */
66 : /************************************************************************/
67 :
68 : //! Copy constructor
69 0 : CPLStringList::CPLStringList( const CPLStringList &oOther )
70 :
71 : {
72 0 : Initialize();
73 0 : Assign( oOther.papszList, FALSE );
74 :
75 : // We don't want to just retain a reference to the others list
76 : // as we don't want to make assumptions about it's lifetime that
77 : // might surprise the client developer.
78 0 : MakeOurOwnCopy();
79 0 : bIsSorted = oOther.bIsSorted;
80 0 : }
81 :
82 : /************************************************************************/
83 : /* operator=() */
84 : /************************************************************************/
85 :
86 0 : CPLStringList &CPLStringList::operator=(const CPLStringList& oOther)
87 : {
88 0 : if (this != &oOther)
89 : {
90 0 : Assign( oOther.papszList, FALSE );
91 :
92 : // We don't want to just retain a reference to the others list
93 : // as we don't want to make assumptions about it's lifetime that
94 : // might surprise the client developer.
95 0 : MakeOurOwnCopy();
96 0 : bIsSorted = oOther.bIsSorted;
97 : }
98 :
99 0 : return *this;
100 : }
101 :
102 : /************************************************************************/
103 : /* Initialize() */
104 : /************************************************************************/
105 :
106 1524223 : void CPLStringList::Initialize()
107 :
108 : {
109 1524223 : papszList = NULL;
110 1524223 : nCount = 0;
111 1524223 : nAllocation = 0;
112 1524223 : bOwnList = FALSE;
113 1524223 : bIsSorted = FALSE;
114 1524223 : }
115 :
116 : /************************************************************************/
117 : /* ~CPLStringList() */
118 : /************************************************************************/
119 :
120 1522378 : CPLStringList::~CPLStringList()
121 :
122 : {
123 1522378 : Clear();
124 1522378 : }
125 :
126 : /************************************************************************/
127 : /* Clear() */
128 : /************************************************************************/
129 :
130 : /**
131 : * Clear the string list.
132 : */
133 1617486 : CPLStringList &CPLStringList::Clear()
134 :
135 : {
136 1617486 : if( bOwnList )
137 : {
138 76150 : CSLDestroy( papszList );
139 76150 : papszList = NULL;
140 :
141 76150 : bOwnList = FALSE;
142 76150 : nAllocation = 0;
143 76150 : nCount = 0;
144 : }
145 :
146 1617486 : return *this;
147 : }
148 :
149 : /************************************************************************/
150 : /* Assign() */
151 : /************************************************************************/
152 :
153 : /**
154 : * Assign a list of strings.
155 : *
156 : *
157 : * @param papszListIn the NULL terminated list of strings to consume.
158 : * @param bTakeOwnership TRUE if the CPLStringList should take ownership
159 : * of the list of strings which implies responsibility to free them.
160 : *
161 : * @return a reference to the CPLStringList on which it was invoked.
162 : */
163 :
164 95063 : CPLStringList &CPLStringList::Assign( char **papszListIn, int bTakeOwnership )
165 :
166 : {
167 95063 : Clear();
168 :
169 95063 : papszList = papszListIn;
170 95063 : bOwnList = bTakeOwnership;
171 :
172 187676 : if( papszList == NULL || *papszList == NULL )
173 92613 : nCount = 0;
174 : else
175 2450 : nCount = -1; // unknown
176 :
177 95063 : nAllocation = 0;
178 95063 : bIsSorted = FALSE;
179 :
180 95063 : return *this;
181 : }
182 :
183 : /************************************************************************/
184 : /* Count() */
185 : /************************************************************************/
186 :
187 : /**
188 : * @return count of strings in the list, zero if empty.
189 : */
190 :
191 80358 : int CPLStringList::Count() const
192 :
193 : {
194 80358 : if( nCount == -1 )
195 : {
196 2401 : if( papszList == NULL )
197 : {
198 0 : nCount = nAllocation = 0;
199 : }
200 : else
201 : {
202 2401 : nCount = CSLCount( papszList );
203 2401 : nAllocation = MAX(nCount+1,nAllocation);
204 : }
205 : }
206 :
207 80358 : return nCount;
208 : }
209 :
210 : /************************************************************************/
211 : /* MakeOurOwnCopy() */
212 : /* */
213 : /* If we don't own the list, a copy is made which we own. */
214 : /* Necessary if we are going to modify the list. */
215 : /************************************************************************/
216 :
217 1829935 : void CPLStringList::MakeOurOwnCopy()
218 :
219 : {
220 1829935 : if( bOwnList )
221 402092 : return;
222 :
223 1427843 : if( papszList == NULL )
224 1427843 : return;
225 :
226 0 : Count();
227 0 : bOwnList = TRUE;
228 0 : papszList = CSLDuplicate( papszList );
229 0 : nAllocation = nCount+1;
230 : }
231 :
232 : /************************************************************************/
233 : /* EnsureAllocation() */
234 : /* */
235 : /* Ensure we have enough room allocated for at least the */
236 : /* requested number of strings (so nAllocation will be at least */
237 : /* one more than the target) */
238 : /************************************************************************/
239 :
240 2456136 : void CPLStringList::EnsureAllocation( int nMaxList )
241 :
242 : {
243 2456136 : if( !bOwnList )
244 1427843 : MakeOurOwnCopy();
245 :
246 2456136 : if( nAllocation <= nMaxList )
247 : {
248 1516419 : nAllocation = MAX(nAllocation*2 + 20,nMaxList+1);
249 1516419 : if( papszList == NULL )
250 : {
251 1502241 : papszList = (char **) CPLCalloc(nAllocation,sizeof(char*));
252 1502241 : bOwnList = TRUE;
253 1502241 : nCount = 0;
254 : }
255 : else
256 14178 : papszList = (char **) CPLRealloc(papszList, nAllocation*sizeof(char*));
257 : }
258 2456136 : }
259 :
260 : /************************************************************************/
261 : /* AddStringDirectly() */
262 : /************************************************************************/
263 :
264 : /**
265 : * Add a string to the list.
266 : *
267 : * This method is similar to AddString(), but ownership of the
268 : * pszNewString is transferred to the CPLStringList class.
269 : *
270 : * @param pszNewString the string to add to the list.
271 : */
272 :
273 2133182 : CPLStringList &CPLStringList::AddStringDirectly( char *pszNewString )
274 :
275 : {
276 2133182 : if( nCount == -1 )
277 0 : Count();
278 :
279 2133182 : EnsureAllocation( nCount+1 );
280 :
281 2133182 : papszList[nCount++] = pszNewString;
282 2133182 : papszList[nCount] = NULL;
283 :
284 2133182 : bIsSorted = FALSE;
285 :
286 2133182 : return *this;
287 : }
288 :
289 : /************************************************************************/
290 : /* AddString() */
291 : /************************************************************************/
292 :
293 : /**
294 : * Add a string to the list.
295 : *
296 : * A copy of the passed in string is made and inserted in the list.
297 : *
298 : * @param pszNewString the string to add to the list.
299 : */
300 :
301 2133143 : CPLStringList &CPLStringList::AddString( const char *pszNewString )
302 :
303 : {
304 2133143 : return AddStringDirectly( CPLStrdup( pszNewString ) );
305 : }
306 :
307 : /************************************************************************/
308 : /* AddNameValue() */
309 : /************************************************************************/
310 :
311 : /**
312 : * A a name=value entry to the list.
313 : *
314 : * A key=value string is prepared and appended to the list. There is no
315 : * check for other values for the same key in the list.
316 : *
317 : * @param pszKey the key name to add.
318 : * @param pszValue the key value to add.
319 : */
320 :
321 322984 : CPLStringList &CPLStringList::AddNameValue( const char *pszKey,
322 : const char *pszValue )
323 :
324 : {
325 322984 : if (pszKey == NULL || pszValue==NULL)
326 0 : return *this;
327 :
328 322984 : MakeOurOwnCopy();
329 :
330 : /* -------------------------------------------------------------------- */
331 : /* Format the line. */
332 : /* -------------------------------------------------------------------- */
333 : char *pszLine;
334 322984 : pszLine = (char *) CPLMalloc(strlen(pszKey)+strlen(pszValue)+2);
335 322984 : sprintf( pszLine, "%s=%s", pszKey, pszValue );
336 :
337 : /* -------------------------------------------------------------------- */
338 : /* If we don't need to keep the sort order things are pretty */
339 : /* straight forward. */
340 : /* -------------------------------------------------------------------- */
341 322984 : if( !IsSorted() )
342 30 : return AddStringDirectly( pszLine );
343 :
344 : /* -------------------------------------------------------------------- */
345 : /* Find the proper insertion point. */
346 : /* -------------------------------------------------------------------- */
347 322954 : CPLAssert( IsSorted() );
348 322954 : int iKey = FindSortedInsertionPoint( pszLine );
349 322954 : InsertStringDirectly( iKey, pszLine );
350 322954 : bIsSorted = TRUE; // we have actually preserved sort order.
351 :
352 322954 : return *this;
353 : }
354 :
355 : /************************************************************************/
356 : /* SetNameValue() */
357 : /************************************************************************/
358 :
359 : /**
360 : * Set name=value entry in the list.
361 : *
362 : * Similar to AddNameValue(), except if there is already a value for
363 : * the key in the list it is replaced instead of adding a new entry to
364 : * the list. If pszValue is NULL any existing key entry is removed.
365 : *
366 : * @param pszKey the key name to add.
367 : * @param pszValue the key value to add.
368 : */
369 :
370 324481 : CPLStringList &CPLStringList::SetNameValue( const char *pszKey,
371 : const char *pszValue )
372 :
373 : {
374 324481 : int iKey = FindName( pszKey );
375 :
376 324481 : if( iKey == -1 )
377 322984 : return AddNameValue( pszKey, pszValue );
378 :
379 1497 : Count();
380 1497 : MakeOurOwnCopy();
381 :
382 1497 : CPLFree( papszList[iKey] );
383 1497 : if( pszValue == NULL ) // delete entry
384 : {
385 :
386 : // shift everything down by one.
387 0 : do
388 : {
389 0 : papszList[iKey] = papszList[iKey+1];
390 : }
391 0 : while( papszList[iKey++] != NULL );
392 :
393 0 : nCount--;
394 : }
395 : else
396 : {
397 : char *pszLine;
398 1497 : pszLine = (char *) CPLMalloc(strlen(pszKey)+strlen(pszValue)+2);
399 1497 : sprintf( pszLine, "%s=%s", pszKey, pszValue );
400 :
401 1497 : papszList[iKey] = pszLine;
402 : }
403 :
404 1497 : return *this;
405 : }
406 :
407 : /************************************************************************/
408 : /* operator[] */
409 : /************************************************************************/
410 :
411 : /**
412 : * Fetch entry "i".
413 : *
414 : * Fetches the requested item in the list. Note that the returned string
415 : * remains owned by the CPLStringList. If "i" is out of range NULL is
416 : * returned.
417 : *
418 : * @param i the index of the list item to return.
419 : * @return selected entry in the list.
420 : */
421 2066 : char *CPLStringList::operator[]( int i )
422 :
423 : {
424 2066 : if( nCount == -1 )
425 0 : Count();
426 :
427 2066 : if( i < 0 || i >= nCount )
428 0 : return NULL;
429 : else
430 2066 : return papszList[i];
431 : }
432 :
433 0 : const char *CPLStringList::operator[]( int i ) const
434 :
435 : {
436 0 : if( nCount == -1 )
437 0 : Count();
438 :
439 0 : if( i < 0 || i >= nCount )
440 0 : return NULL;
441 : else
442 0 : return papszList[i];
443 : }
444 :
445 : /************************************************************************/
446 : /* StealList() */
447 : /************************************************************************/
448 :
449 : /**
450 : * Seize ownership of underlying string array.
451 : *
452 : * This method is simmilar to List(), except that the returned list is
453 : * now owned by the caller and the CPLStringList is emptied.
454 : *
455 : * @return the C style string list.
456 : */
457 1446404 : char **CPLStringList::StealList()
458 :
459 : {
460 1446404 : char **papszRetList = papszList;
461 :
462 1446404 : bOwnList = FALSE;
463 1446404 : papszList = NULL;
464 1446404 : nCount = 0;
465 1446404 : nAllocation = 0;
466 :
467 1446404 : return papszRetList;
468 : }
469 :
470 : /************************************************************************/
471 : /* llCompareStr() */
472 : /* */
473 : /* Note this is case insensitive! This is because we normally */
474 : /* treat key value keywords as case insensitive. */
475 : /************************************************************************/
476 187959 : static int llCompareStr(const void *a, const void *b)
477 : {
478 187959 : return STRCASECMP((*(const char **)a),(*(const char **)b));
479 : }
480 :
481 : /************************************************************************/
482 : /* Sort() */
483 : /************************************************************************/
484 :
485 : /**
486 : * Sort the entries in the list and mark list sorted.
487 : *
488 : * Note that once put into "sorted" mode, the CPLStringList will attempt to
489 : * keep things in sorted order through calls to AddString(),
490 : * AddStringDirectly(), AddNameValue(), SetNameValue(). Complete list
491 : * assignments (via Assign() and operator= will clear the sorting state.
492 : * When in sorted order FindName(), FetchNameValue() and FetchNameValueDef()
493 : * will do a binary search to find the key, substantially improve lookup
494 : * performance in large lists.
495 : */
496 :
497 77611 : CPLStringList &CPLStringList::Sort()
498 :
499 : {
500 77611 : Count();
501 77611 : MakeOurOwnCopy();
502 :
503 77611 : qsort( papszList, nCount, sizeof(char*), llCompareStr );
504 77611 : bIsSorted = TRUE;
505 :
506 77611 : return *this;
507 : }
508 :
509 : /************************************************************************/
510 : /* FindName() */
511 : /************************************************************************/
512 :
513 : /**
514 : * Get index of given name/value keyword.
515 : *
516 : * Note that this search is for a line in the form name=value or name:value.
517 : * Use FindString() or PartialFindString() for searches not based on name=value
518 : * pairs.
519 : *
520 : * @param pszKey the name to search for.
521 : *
522 : * @return the string list index of this name, or -1 on failure.
523 : */
524 :
525 341477 : int CPLStringList::FindName( const char *pszKey ) const
526 :
527 : {
528 341477 : if( !IsSorted() )
529 31 : return CSLFindName( papszList, pszKey );
530 :
531 : // If we are sorted, we can do an optimized binary search.
532 341446 : int iStart=0, iEnd=nCount-1;
533 341446 : int nKeyLen = strlen(pszKey);
534 :
535 1116857 : while( iStart <= iEnd )
536 : {
537 449494 : int iMiddle = (iEnd+iStart)/2;
538 449494 : const char *pszMiddle = papszList[iMiddle];
539 :
540 465895 : if (EQUALN(pszMiddle, pszKey, nKeyLen)
541 16401 : && (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':') )
542 15529 : return iMiddle;
543 :
544 433965 : if( STRCASECMP(pszKey,pszMiddle) < 0 )
545 350095 : iEnd = iMiddle-1;
546 : else
547 83870 : iStart = iMiddle+1;
548 : }
549 :
550 325917 : return -1;
551 : }
552 :
553 : /************************************************************************/
554 : /* FetchBoolean() */
555 : /************************************************************************/
556 : /**
557 : *
558 : * Check for boolean key value.
559 : *
560 : * In a CPLStringList of "Name=Value" pairs, look to see if there is a key
561 : * with the given name, and if it can be interpreted as being TRUE. If
562 : * the key appears without any "=Value" portion it will be considered true.
563 : * If the value is NO, FALSE or 0 it will be considered FALSE otherwise
564 : * if the key appears in the list it will be considered TRUE. If the key
565 : * doesn't appear at all, the indicated default value will be returned.
566 : *
567 : * @param pszKey the key value to look for (case insensitive).
568 : * @param bDefault the value to return if the key isn't found at all.
569 : *
570 : * @return TRUE or FALSE
571 : */
572 :
573 0 : int CPLStringList::FetchBoolean( const char *pszKey, int bDefault ) const
574 :
575 : {
576 0 : const char *pszValue = FetchNameValue( pszKey );
577 :
578 0 : if( pszValue == NULL )
579 0 : return bDefault;
580 : else
581 0 : return CSLTestBoolean( pszValue );
582 : }
583 :
584 : /************************************************************************/
585 : /* FetchNameValue() */
586 : /************************************************************************/
587 :
588 : /**
589 : * Fetch value associated with this key name.
590 : *
591 : * If this list sorted, a fast binary search is done, otherwise a linear
592 : * scan is done. Name lookup is case insensitive.
593 : *
594 : * @param pszName the key name to search for.
595 : *
596 : * @return the corresponding value or NULL if not found. The returned string
597 : * should not be modified and points into internal object state that may
598 : * change on future calls.
599 : */
600 :
601 16996 : const char *CPLStringList::FetchNameValue( const char *pszName ) const
602 :
603 : {
604 16996 : int iKey = FindName( pszName );
605 :
606 16996 : if( iKey == -1 )
607 2963 : return NULL;
608 :
609 28066 : CPLAssert( papszList[iKey][strlen(pszName)] == '='
610 28066 : || papszList[iKey][strlen(pszName)] == ':' );
611 :
612 14033 : return papszList[iKey] + strlen(pszName)+1;
613 : }
614 :
615 : /************************************************************************/
616 : /* FetchNameValueDef() */
617 : /************************************************************************/
618 :
619 : /**
620 : * Fetch value associated with this key name.
621 : *
622 : * If this list sorted, a fast binary search is done, otherwise a linear
623 : * scan is done. Name lookup is case insensitive.
624 : *
625 : * @param pszName the key name to search for.
626 : * @param pszDefault the default value returned if the named entry isn't found.
627 : *
628 : * @return the corresponding value or the passed default if not found.
629 : */
630 :
631 0 : const char *CPLStringList::FetchNameValueDef( const char *pszName,
632 : const char *pszDefault ) const
633 :
634 : {
635 0 : const char *pszValue = FetchNameValue( pszName );
636 0 : if( pszValue == NULL )
637 0 : return pszDefault;
638 : else
639 0 : return pszValue;
640 : }
641 :
642 : /************************************************************************/
643 : /* InsertString() */
644 : /************************************************************************/
645 :
646 : /**
647 : * \fn CPLStringList *CPLStringList::InsertString( int nInsertAtLineNo,
648 : * const char *pszNewLine );
649 : *
650 : * \brief Insert into the list at identified location.
651 : *
652 : * This method will insert a string into the list at the identified
653 : * location. The insertion point must be within or at the end of the list.
654 : * The following entries are pushed down to make space.
655 : *
656 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
657 : * @param pszNewLine to the line to insert. This string will be copied.
658 : */
659 :
660 :
661 : /************************************************************************/
662 : /* InsertStringDirectly() */
663 : /************************************************************************/
664 :
665 : /**
666 : * Insert into the list at identified location.
667 : *
668 : * This method will insert a string into the list at the identified
669 : * location. The insertion point must be within or at the end of the list.
670 : * The following entries are pushed down to make space.
671 : *
672 : * @param nInsertAtLineNo the line to insert at, zero to insert at front.
673 : * @param pszNewLine to the line to insert, the ownership of this string
674 : * will be taken over the by the object. It must have been allocated on the
675 : * heap.
676 : */
677 :
678 322954 : CPLStringList &CPLStringList::InsertStringDirectly( int nInsertAtLineNo,
679 : char *pszNewLine )
680 :
681 : {
682 322954 : if( nCount == -1 )
683 0 : Count();
684 :
685 322954 : EnsureAllocation( nCount+1 );
686 :
687 322954 : if( nInsertAtLineNo < 0 || nInsertAtLineNo > nCount )
688 : {
689 : CPLError( CE_Failure, CPLE_AppDefined,
690 0 : "CPLStringList::InsertString() requested beyond list end." );
691 0 : return *this;
692 : }
693 :
694 322954 : bIsSorted = FALSE;
695 :
696 1002431 : for( int i = nCount; i > nInsertAtLineNo; i-- )
697 679477 : papszList[i] = papszList[i-1];
698 :
699 322954 : papszList[nInsertAtLineNo] = pszNewLine;
700 322954 : papszList[++nCount] = NULL;
701 :
702 322954 : return *this;
703 : }
704 :
705 : /************************************************************************/
706 : /* FindSortedInsertionPoint() */
707 : /* */
708 : /* Find the location at which the indicated line should be */
709 : /* inserted in order to keep things in sorted order. */
710 : /************************************************************************/
711 :
712 322954 : int CPLStringList::FindSortedInsertionPoint( const char *pszLine )
713 :
714 : {
715 322954 : CPLAssert( IsSorted() );
716 :
717 322954 : int iStart=0, iEnd=nCount-1;
718 :
719 1059892 : while( iStart <= iEnd )
720 : {
721 413984 : int iMiddle = (iEnd+iStart)/2;
722 413984 : const char *pszMiddle = papszList[iMiddle];
723 :
724 413984 : if( STRCASECMP(pszLine,pszMiddle) < 0 )
725 342910 : iEnd = iMiddle-1;
726 : else
727 71074 : iStart = iMiddle+1;
728 : }
729 :
730 322954 : iEnd++;
731 322954 : CPLAssert( iEnd >= 0 && iEnd <= nCount );
732 50110 : CPLAssert( iEnd == 0
733 373064 : || STRCASECMP(pszLine,papszList[iEnd-1]) >= 0 );
734 238544 : CPLAssert( iEnd == nCount
735 561498 : || STRCASECMP(pszLine,papszList[iEnd]) <= 0 );
736 :
737 322954 : return iEnd;
738 : }
|
