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 3120846 : CPLStringList::CPLStringList()
40 :
41 : {
42 3120846 : Initialize();
43 3120846 : }
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 3120846 : void CPLStringList::Initialize()
107 :
108 : {
109 3120846 : papszList = NULL;
110 3120846 : nCount = 0;
111 3120846 : nAllocation = 0;
112 3120846 : bOwnList = FALSE;
113 3120846 : bIsSorted = FALSE;
114 3120846 : }
115 :
116 : /************************************************************************/
117 : /* ~CPLStringList() */
118 : /************************************************************************/
119 :
120 3116310 : CPLStringList::~CPLStringList()
121 :
122 : {
123 3116310 : Clear();
124 3116310 : }
125 :
126 : /************************************************************************/
127 : /* Clear() */
128 : /************************************************************************/
129 :
130 : /**
131 : * Clear the string list.
132 : */
133 3318137 : CPLStringList &CPLStringList::Clear()
134 :
135 : {
136 3318137 : if( bOwnList )
137 : {
138 158962 : CSLDestroy( papszList );
139 158962 : papszList = NULL;
140 :
141 158962 : bOwnList = FALSE;
142 158962 : nAllocation = 0;
143 158962 : nCount = 0;
144 : }
145 :
146 3318137 : 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 201733 : CPLStringList &CPLStringList::Assign( char **papszListIn, int bTakeOwnership )
165 :
166 : {
167 201733 : Clear();
168 :
169 201733 : papszList = papszListIn;
170 201733 : bOwnList = bTakeOwnership;
171 :
172 397844 : if( papszList == NULL || *papszList == NULL )
173 196111 : nCount = 0;
174 : else
175 5622 : nCount = -1; // unknown
176 :
177 201733 : nAllocation = 0;
178 201733 : bIsSorted = FALSE;
179 :
180 201733 : return *this;
181 : }
182 :
183 : /************************************************************************/
184 : /* Count() */
185 : /************************************************************************/
186 :
187 : /**
188 : * @return count of strings in the list, zero if empty.
189 : */
190 :
191 168915 : int CPLStringList::Count() const
192 :
193 : {
194 168915 : if( nCount == -1 )
195 : {
196 5492 : if( papszList == NULL )
197 : {
198 0 : nCount = nAllocation = 0;
199 : }
200 : else
201 : {
202 5492 : nCount = CSLCount( papszList );
203 5492 : nAllocation = MAX(nCount+1,nAllocation);
204 : }
205 : }
206 :
207 168915 : 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 3761924 : void CPLStringList::MakeOurOwnCopy()
218 :
219 : {
220 3761924 : if( bOwnList )
221 845927 : return;
222 :
223 2915997 : if( papszList == NULL )
224 2915997 : 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 5155618 : void CPLStringList::EnsureAllocation( int nMaxList )
241 :
242 : {
243 5155618 : if( !bOwnList )
244 2915967 : MakeOurOwnCopy();
245 :
246 5155618 : if( nAllocation <= nMaxList )
247 : {
248 3101229 : nAllocation = MAX(nAllocation*2 + 20,nMaxList+1);
249 3101229 : if( papszList == NULL )
250 : {
251 3071383 : papszList = (char **) CPLCalloc(nAllocation,sizeof(char*));
252 3071383 : bOwnList = TRUE;
253 3071383 : nCount = 0;
254 : }
255 : else
256 29846 : papszList = (char **) CPLRealloc(papszList, nAllocation*sizeof(char*));
257 : }
258 5155618 : }
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 4475578 : CPLStringList &CPLStringList::AddStringDirectly( char *pszNewString )
274 :
275 : {
276 4475578 : if( nCount == -1 )
277 0 : Count();
278 :
279 4475578 : EnsureAllocation( nCount+1 );
280 :
281 4475578 : papszList[nCount++] = pszNewString;
282 4475578 : papszList[nCount] = NULL;
283 :
284 4475578 : bIsSorted = FALSE;
285 :
286 4475578 : 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 4475368 : CPLStringList &CPLStringList::AddString( const char *pszNewString )
302 :
303 : {
304 4475368 : 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 680240 : CPLStringList &CPLStringList::AddNameValue( const char *pszKey,
322 : const char *pszValue )
323 :
324 : {
325 680240 : if (pszKey == NULL || pszValue==NULL)
326 8 : return *this;
327 :
328 680232 : MakeOurOwnCopy();
329 :
330 : /* -------------------------------------------------------------------- */
331 : /* Format the line. */
332 : /* -------------------------------------------------------------------- */
333 : char *pszLine;
334 680232 : pszLine = (char *) CPLMalloc(strlen(pszKey)+strlen(pszValue)+2);
335 680232 : 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 680232 : if( !IsSorted() )
342 192 : return AddStringDirectly( pszLine );
343 :
344 : /* -------------------------------------------------------------------- */
345 : /* Find the proper insertion point. */
346 : /* -------------------------------------------------------------------- */
347 680040 : CPLAssert( IsSorted() );
348 680040 : int iKey = FindSortedInsertionPoint( pszLine );
349 680040 : InsertStringDirectly( iKey, pszLine );
350 680040 : bIsSorted = TRUE; // we have actually preserved sort order.
351 :
352 680040 : 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 683223 : CPLStringList &CPLStringList::SetNameValue( const char *pszKey,
371 : const char *pszValue )
372 :
373 : {
374 683223 : int iKey = FindName( pszKey );
375 :
376 683223 : if( iKey == -1 )
377 680108 : return AddNameValue( pszKey, pszValue );
378 :
379 3115 : Count();
380 3115 : MakeOurOwnCopy();
381 :
382 3115 : CPLFree( papszList[iKey] );
383 3115 : if( pszValue == NULL ) // delete entry
384 : {
385 :
386 : // shift everything down by one.
387 8 : do
388 : {
389 4 : papszList[iKey] = papszList[iKey+1];
390 : }
391 8 : while( papszList[iKey++] != NULL );
392 :
393 4 : nCount--;
394 : }
395 : else
396 : {
397 : char *pszLine;
398 3111 : pszLine = (char *) CPLMalloc(strlen(pszKey)+strlen(pszValue)+2);
399 3111 : sprintf( pszLine, "%s=%s", pszKey, pszValue );
400 :
401 3111 : papszList[iKey] = pszLine;
402 : }
403 :
404 3115 : 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 5064 : char *CPLStringList::operator[]( int i )
422 :
423 : {
424 5064 : if( nCount == -1 )
425 0 : Count();
426 :
427 5064 : if( i < 0 || i >= nCount )
428 0 : return NULL;
429 : else
430 5064 : 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 2957408 : char **CPLStringList::StealList()
458 :
459 : {
460 2957408 : char **papszRetList = papszList;
461 :
462 2957408 : bOwnList = FALSE;
463 2957408 : papszList = NULL;
464 2957408 : nCount = 0;
465 2957408 : nAllocation = 0;
466 :
467 2957408 : 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 380798 : static int llCompareStr(const void *a, const void *b)
477 : {
478 380798 : 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 162610 : CPLStringList &CPLStringList::Sort()
498 :
499 : {
500 162610 : Count();
501 162610 : MakeOurOwnCopy();
502 :
503 162610 : qsort( papszList, nCount, sizeof(char*), llCompareStr );
504 162610 : bIsSorted = TRUE;
505 :
506 162610 : 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 724425 : int CPLStringList::FindName( const char *pszKey ) const
526 :
527 : {
528 724425 : if( !IsSorted() )
529 62 : return CSLFindName( papszList, pszKey );
530 :
531 : // If we are sorted, we can do an optimized binary search.
532 724363 : int iStart=0, iEnd=nCount-1;
533 724363 : int nKeyLen = strlen(pszKey);
534 :
535 2368651 : while( iStart <= iEnd )
536 : {
537 957374 : int iMiddle = (iEnd+iStart)/2;
538 957374 : const char *pszMiddle = papszList[iMiddle];
539 :
540 996571 : if (EQUALN(pszMiddle, pszKey, nKeyLen)
541 39197 : && (pszMiddle[nKeyLen] == '=' || pszMiddle[nKeyLen] == ':') )
542 37449 : return iMiddle;
543 :
544 919925 : if( STRCASECMP(pszKey,pszMiddle) < 0 )
545 738275 : iEnd = iMiddle-1;
546 : else
547 181650 : iStart = iMiddle+1;
548 : }
549 :
550 686914 : 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 41202 : const char *CPLStringList::FetchNameValue( const char *pszName ) const
602 :
603 : {
604 41202 : int iKey = FindName( pszName );
605 :
606 41202 : if( iKey == -1 )
607 6866 : return NULL;
608 :
609 68672 : CPLAssert( papszList[iKey][strlen(pszName)] == '='
610 68672 : || papszList[iKey][strlen(pszName)] == ':' );
611 :
612 34336 : 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 680040 : CPLStringList &CPLStringList::InsertStringDirectly( int nInsertAtLineNo,
679 : char *pszNewLine )
680 :
681 : {
682 680040 : if( nCount == -1 )
683 0 : Count();
684 :
685 680040 : EnsureAllocation( nCount+1 );
686 :
687 680040 : 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 680040 : bIsSorted = FALSE;
695 :
696 2104925 : for( int i = nCount; i > nInsertAtLineNo; i-- )
697 1424885 : papszList[i] = papszList[i-1];
698 :
699 680040 : papszList[nInsertAtLineNo] = pszNewLine;
700 680040 : papszList[++nCount] = NULL;
701 :
702 680040 : 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 680040 : int CPLStringList::FindSortedInsertionPoint( const char *pszLine )
713 :
714 : {
715 680040 : CPLAssert( IsSorted() );
716 :
717 680040 : int iStart=0, iEnd=nCount-1;
718 :
719 2236175 : while( iStart <= iEnd )
720 : {
721 876095 : int iMiddle = (iEnd+iStart)/2;
722 876095 : const char *pszMiddle = papszList[iMiddle];
723 :
724 876095 : if( STRCASECMP(pszLine,pszMiddle) < 0 )
725 722833 : iEnd = iMiddle-1;
726 : else
727 153262 : iStart = iMiddle+1;
728 : }
729 :
730 680040 : iEnd++;
731 680040 : CPLAssert( iEnd >= 0 && iEnd <= nCount );
732 106902 : CPLAssert( iEnd == 0
733 786942 : || STRCASECMP(pszLine,papszList[iEnd-1]) >= 0 );
734 502572 : CPLAssert( iEnd == nCount
735 1182612 : || STRCASECMP(pszLine,papszList[iEnd]) <= 0 );
736 :
737 680040 : return iEnd;
738 : }
|
