"Fossies" - the Fresh Open Source Software Archive 
Member "muscle/util/String.cpp" (21 Nov 2020, 41335 Bytes) of package /linux/privat/muscle7.62.zip:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "String.cpp" see the
Fossies "Dox" file reference documentation and the latest
Fossies "Diffs" side-by-side code changes report:
7.61_vs_7.62.
1 /* This file is Copyright 2000-2013 Meyer Sound Laboratories Inc. See the included LICENSE.txt file for details. */
2
3 #include "util/String.h"
4 #include "support/Point.h"
5 #include "support/Rect.h"
6 #include <stdarg.h>
7
8 #ifdef __APPLE__
9 # include <CoreFoundation/CFString.h>
10 #endif
11
12 namespace muscle {
13
14 const char * StrcasestrEx(const char * haystack, uint32 haystackLen, const char * needle, uint32 needleLen, bool searchBackwards)
15 {
16 if ((haystack==NULL)||(needle==NULL)) return NULL;
17
18 if (haystackLen >= needleLen)
19 {
20 const uint32 searchLen = haystackLen-(needleLen-1);
21 if (searchBackwards)
22 {
23 for (int32 i=(searchLen-1); i>=0; i--) if (Strncasecmp(haystack+i, needle, needleLen) == 0) return haystack+i;
24 }
25 else
26 {
27 for (uint32 i=0; i<searchLen; i++) if (Strncasecmp(haystack+i, needle, needleLen) == 0) return haystack+i;
28 }
29 }
30 return NULL;
31 }
32
33 const char * Strcasestr(const char * haystack, const char * needle)
34 {
35 #ifdef WIN32
36 return StrcasestrEx(haystack, (uint32)strlen(haystack), needle, (uint32)strlen(needle), false);
37 #else
38 return strcasestr(haystack, needle);
39 #endif
40 }
41
42 int String :: IndexOfIgnoreCase(char ch, uint32 f) const
43 {
44 const char lowerChar = (char) tolower(ch);
45 const char upperChar = (char) toupper(ch);
46 if (lowerChar == upperChar) return IndexOf(ch, f);
47 else
48 {
49 const char * p = Cstr();
50 for (uint32 i=f; i<Length(); i++) if ((p[i] == lowerChar)||(p[i] == upperChar)) return i;
51 return -1;
52 }
53 }
54
55 int String :: IndexOfIgnoreCase(const String & s, uint32 f) const
56 {
57 const char * p = (f<Length())?StrcasestrEx(Cstr()+f, Length()-f, s(), s.Length(), false):NULL;
58 return p?(int)(p-Cstr()):-1;
59 }
60
61 int String :: IndexOfIgnoreCase(const char * s, uint32 f) const
62 {
63 if (s==NULL) s="";
64
65 const char * p = (f<Length()) ? StrcasestrEx(Cstr()+f, Length()-f, s, (uint32)strlen(s), false) : NULL;
66 return p ? ((int)(p-Cstr())): -1;
67 }
68
69 int String :: LastIndexOfIgnoreCase(const String & s, uint32 f) const
70 {
71 const char * p = (f<Length()) ? StrcasestrEx(Cstr()+f, Length()-f, s(), s.Length(), true) : NULL;
72 return p ? ((int)(p-Cstr())) : -1;
73 }
74
75 int String :: LastIndexOfIgnoreCase(const char * s, uint32 f) const
76 {
77 if (s==NULL) s="";
78
79 const char * p = (f<Length()) ? StrcasestrEx(Cstr()+f, Length()-f, s, (uint32)strlen(s), true) : NULL;
80 return p ? ((int)(p-Cstr())) : -1;
81 }
82
83 int String :: LastIndexOfIgnoreCase(char ch, uint32 f) const
84 {
85 const char lowerChar = (char) tolower(ch);
86 const char upperChar = (char) toupper(ch);
87 if (lowerChar == upperChar) return LastIndexOf(ch, f);
88 else
89 {
90 const char * p = Cstr();
91 for (int32 i=((int32)Length())-1; i>=(int32)f; i--) if ((p[i] == lowerChar)||(p[i] == upperChar)) return i;
92 return -1;
93 }
94 }
95
96 bool String :: EndsWithIgnoreCase(const char * s) const
97 {
98 if (s==NULL) s="";
99
100 const uint32 slen = (uint32) strlen(s);
101 return ((Length() >= slen)&&(Strcasecmp(Cstr()+(Length()-slen), s) == 0));
102 }
103
104
105 void String :: ClearAndFlush()
106 {
107 if (IsArrayDynamicallyAllocated()) muscleFree(_strData._bigBuffer);
108 ClearSmallBuffer();
109 _bufferLen = sizeof(_strData._smallBuffer);
110 _length = 0;
111 }
112
113 status_t String :: SetFromString(const String & s, uint32 firstChar, uint32 afterLastChar)
114 {
115 afterLastChar = muscleMin(afterLastChar, s.Length());
116 const uint32 len = (afterLastChar > firstChar) ? (afterLastChar-firstChar) : 0;
117 if (len > 0)
118 {
119 status_t ret;
120 if (EnsureBufferSize(len+1, false, false).IsError(ret)) return ret; // guaranteed not to realloc in the (&s==this) case
121
122 char * b = GetBuffer();
123 memmove(b, s()+firstChar, len); // memmove() is used in case (&s==this)
124 b[len] = '\0';
125 _length = len;
126 }
127 else ClearAndFlush();
128
129 return B_NO_ERROR;
130 }
131
132 status_t String :: SetCstr(const char * str, uint32 maxLen)
133 {
134 // If (str)'s got a NUL byte before maxLen, make (maxLen) smaller.
135 // We can't call strlen(str) because we don't have any guarantee that the NUL
136 // byte even exists! Without a NUL byte, strlen() could run off into the weeds...
137 uint32 sLen = 0;
138 if (str) {while((sLen<maxLen)&&(str[sLen] != '\0')) sLen++;}
139 maxLen = muscleMin(maxLen, sLen);
140 if (maxLen > 0)
141 {
142 if (str[maxLen-1] != '\0') maxLen++; // make room to add the NUL byte if necessary
143
144 status_t ret;
145 if (EnsureBufferSize(maxLen, false, false).IsError(ret)) return ret; // guaranteed not to realloc in the IsCharInLocalArray(str) case
146
147 char * b = GetBuffer();
148 memmove(b, str, maxLen-1); // memmove() is used in case (str) points into our array
149 b[maxLen-1] = '\0';
150 _length = maxLen-1;
151 }
152 else Clear();
153
154 return B_NO_ERROR;
155 }
156
157 String &
158 String :: operator+=(const String &other)
159 {
160 const uint32 otherLen = other.Length(); // save this value first, in case (&other==this)
161 if ((otherLen > 0)&&(EnsureBufferSize(Length()+otherLen+1, true, false) == B_NO_ERROR))
162 {
163 memmove(GetBuffer()+_length, other(), otherLen+1); // memmove() is used in case (&other==this)
164 _length += otherLen;
165 }
166 return *this;
167 }
168
169 String &
170 String :: operator+=(const char * other)
171 {
172 if (other == NULL) other = "";
173 const uint32 otherLen = (uint32) strlen(other);
174 if (otherLen > 0)
175 {
176 if (IsCharInLocalArray(other)) return operator+=(String(other,otherLen)); // avoid potential free-ing of (other) inside EnsureBufferSize()
177 if (EnsureBufferSize(Length()+otherLen+1, true, false) == B_NO_ERROR)
178 {
179 memcpy(GetBuffer()+_length, other, otherLen+1);
180 _length += otherLen;
181 }
182 }
183 return *this;
184 }
185
186 String & String :: operator-=(const char aChar)
187 {
188 const int idx = LastIndexOf(aChar);
189 if (idx >= 0)
190 {
191 char * b = GetBuffer();
192 memmove(b+idx, b+idx+1, _length-idx);
193 --_length;
194 }
195 return *this;
196 }
197
198 String & String :: operator-=(const String &other)
199 {
200 if (*this == other) Clear();
201 else if (other.HasChars())
202 {
203 const int idx = LastIndexOf(other);
204 if (idx >= 0)
205 {
206 const uint32 newEndIdx = idx+other.Length();
207 char * b = GetBuffer();
208 memmove(b+idx, b+newEndIdx, 1+_length-newEndIdx);
209 _length -= other.Length();
210 }
211 }
212 return *this;
213 }
214
215 String & String :: operator-=(const char * other)
216 {
217 const int otherLen = ((other)&&(*other)) ? (int)strlen(other) : 0;
218 if (otherLen > 0)
219 {
220 const int idx = LastIndexOf(other);
221 if (idx >= 0)
222 {
223 const uint32 newEndIdx = idx+otherLen;
224 char * b = GetBuffer();
225 memmove(b+idx, b+newEndIdx, 1+_length-newEndIdx);
226 _length -= otherLen;
227 }
228 }
229 return *this;
230 }
231
232 String & String :: operator<<(int rhs)
233 {
234 char buf[64];
235 muscleSprintf(buf, "%d", rhs);
236 return *this << buf;
237 }
238
239 String & String :: operator<<(float rhs)
240 {
241 char buf[64];
242 muscleSprintf(buf, "%.2f", rhs);
243 return *this << buf;
244 }
245
246 String & String :: operator<<(bool rhs)
247 {
248 const char * val = rhs ? "true" : "false";
249 return *this << val;
250 }
251
252 void String :: Reverse()
253 {
254 if (HasChars())
255 {
256 uint32 from = 0;
257 uint32 to = Length()-1;
258 char * b = GetBuffer();
259 while(from<to) muscleSwap(b[from++], b[to--]);
260 }
261 }
262
263 uint32 String :: Replace(char findChar, char replaceChar, uint32 maxReplaceCount)
264 {
265 uint32 ret = 0;
266 if (findChar != replaceChar)
267 {
268 char * c = GetBuffer();
269 while((*c)&&(maxReplaceCount > 0))
270 {
271 if (*c == findChar)
272 {
273 *c = replaceChar;
274 maxReplaceCount--;
275 ret++;
276 }
277 c++;
278 }
279 }
280 return ret;
281 }
282
283 String String :: WithReplacements(char replaceMe, char withMe, uint32 maxReplaceCount) const
284 {
285 String ret = *this;
286 ret.Replace(replaceMe, withMe, maxReplaceCount);
287 return ret;
288 }
289
290 int32 String :: Replace(const String & replaceMe, const String & withMe, uint32 maxReplaceCount)
291 {
292 TCHECKPOINT;
293
294 if (maxReplaceCount == 0) return 0;
295 if (replaceMe.IsEmpty()) return 0; // can't replace an empty string, that's silly!
296 if (replaceMe == withMe) return muscleMin(maxReplaceCount, GetNumInstancesOf(replaceMe)); // no changes necessary!
297 if (&replaceMe == this) return (SetFromString(withMe)==B_NO_ERROR)?1:-1; // avoid self-entanglement
298 if (&withMe == this) return Replace(replaceMe, String(withMe), maxReplaceCount); // avoid self-entanglement
299
300 String temp;
301 const int32 perInstanceDelta = ((int32)withMe.Length())-((int32)replaceMe.Length());
302 if (perInstanceDelta > 0)
303 {
304 // If we are replacing a shorter string with a longer string, we'll have to do a copy-and-swap
305 uint32 numInstances = muscleMin(GetNumInstancesOf(replaceMe), maxReplaceCount);
306 if (numInstances == 0) return 0; // no changes necessary!
307 if (temp.Prealloc(Length()+(perInstanceDelta*numInstances)) != B_NO_ERROR) return -1;
308 }
309
310 // This code works for both the in-place and the copy-over modes!
311 int32 ret = 0;
312 const char * readPtr = Cstr();
313 char * writePtr = (perInstanceDelta > 0) ? temp.GetBuffer() : NULL;
314 while(1)
315 {
316 char * nextReplaceMe = (maxReplaceCount>0) ? strstr((char *) readPtr, (char *) replaceMe()) : NULL;
317 if (nextReplaceMe)
318 {
319 ret++;
320 if (writePtr)
321 {
322 uint32 numBytes = (uint32) (nextReplaceMe-readPtr);
323 if (perInstanceDelta != 0) memmove(writePtr, readPtr, numBytes);
324 writePtr += numBytes;
325 }
326 else writePtr = nextReplaceMe;
327
328 memcpy(writePtr, withMe(), withMe.Length());
329 readPtr = nextReplaceMe + replaceMe.Length();
330 writePtr += withMe.Length();
331 maxReplaceCount--;
332 }
333 else
334 {
335 if (writePtr)
336 {
337 // Finish up
338 const uint32 numBytes = (uint32) (Cstr()+Length()-readPtr);
339 if (perInstanceDelta != 0) memmove(writePtr, readPtr, numBytes);
340 writePtr += numBytes;
341 *writePtr = '\0';
342 if (perInstanceDelta > 0)
343 {
344 temp._length = (uint32) (writePtr-temp());
345 SwapContents(temp);
346 }
347 else _length = (uint32) (writePtr-Cstr());
348 }
349 return ret;
350 }
351 }
352 return ret; // just to shut the compiler up; we never actually get here
353 }
354
355 String String :: WithReplacements(const Hashtable<String, String> & beforeToAfter, uint32 maxReplaceCount) const
356 {
357 if ((maxReplaceCount == 0)||(beforeToAfter.IsEmpty())||(IsEmpty())) return *this;
358
359 // We'll set each pointer in this array to point to the key in the Hashtable that has a claim on its associated char in our String
360 const String ** reservations = newnothrow const String *[Length()];
361 if (reservations) for (uint32 i=0; i<Length(); i++) reservations[i] = NULL;
362 else
363 {
364 WARN_OUT_OF_MEMORY;
365 return *this;
366 }
367
368 const char * nullTerminator = Cstr()+Length();
369
370 int32 stringLengthDelta = 0;
371 for (HashtableIterator<String, String> iter(beforeToAfter); ((maxReplaceCount > 0)&&(iter.HasData())); iter++)
372 {
373 const String & replaceMe = iter.GetKey();
374 const String & withMe = iter.GetValue();
375
376 const char * readPtr = Cstr();
377 while((maxReplaceCount > (uint32)0)&&((uint32)(nullTerminator-readPtr)>=replaceMe.Length()))
378 {
379 const char * nextFind = strstr(readPtr, replaceMe());
380 if (nextFind)
381 {
382 // Check to see if all of the reservation-char-slots for this substring are still open (if not, we'll skip this match)
383 bool alreadyReserved = false;
384 const uint32 startOffset = (uint32)(nextFind-Cstr());
385 const uint32 endOffset = startOffset+replaceMe.Length();
386 for (uint32 i=startOffset; i<endOffset; i++) {if (reservations[i] != NULL) alreadyReserved = true; break;}
387 if (alreadyReserved == false)
388 {
389 // Make the reservation!
390 for (uint32 i=startOffset; i<endOffset; i++) reservations[i] = &replaceMe;
391 stringLengthDelta += (withMe.Length()-replaceMe.Length());
392 if (maxReplaceCount != MUSCLE_NO_LIMIT) maxReplaceCount--;
393 }
394 readPtr = nextFind + replaceMe.Length();
395 }
396 else break;
397 }
398 }
399
400 // Now that we have our reservations-table set up, we can use it to generate the new String
401 String ret;
402 if (ret.Prealloc(Length()+stringLengthDelta).IsOK())
403 {
404 for (uint32 i=0; i<Length(); i++)
405 {
406 if (reservations[i])
407 {
408 const String & replaceMe = *reservations[i];
409 ret += beforeToAfter[replaceMe];
410 i += replaceMe.Length()-1; // -1 because the for-loop will also do an increment
411 }
412 else ret += (*this)[i];
413 }
414 }
415 else
416 {
417 WARN_OUT_OF_MEMORY;
418 ret = *this;
419 }
420
421 delete [] reservations;
422 return ret;
423 }
424
425 String String :: WithReplacements(const String & replaceMe, const String & withMe, uint32 maxReplaceCount) const
426 {
427 String ret = *this;
428 ret.Replace(replaceMe, withMe, maxReplaceCount);
429 return ret;
430 }
431
432 int String :: LastIndexOf(const String &s2, uint32 fromIndex) const
433 {
434 TCHECKPOINT;
435
436 if (s2.IsEmpty()) return Length()-1;
437 if (fromIndex >= Length()) return -1;
438 for (int i=fromIndex; i>=0; i--) if (strncmp(Cstr()+i, s2.Cstr(), s2.Length()) == 0) return i;
439 return -1;
440 }
441
442 int String :: LastIndexOf(const char * s2, uint32 fromIndex) const
443 {
444 TCHECKPOINT;
445
446 if (s2 == NULL) s2 = "";
447 const uint32 s2Len = (uint32) strlen(s2);
448 if (s2Len == 0) return Length()-1;
449 if (fromIndex >= Length()) return -1;
450 for (int i=fromIndex; i>=0; i--) if (strncmp(Cstr()+i, s2, s2Len) == 0) return i;
451 return -1;
452 }
453
454 String String :: ToLowerCase() const
455 {
456 String ret(*this);
457 char * b = ret.GetBuffer();
458 for (uint32 i=0; i<ret.Length(); i++) b[i] = (char)tolower(b[i]);
459 return ret;
460 }
461
462 String String :: ToMixedCase() const
463 {
464 bool prevCharWasLetter = false;
465 String ret(*this);
466 char * b = ret.GetBuffer();
467 for (uint32 i=0; i<ret.Length(); i++)
468 {
469 char & c = b[i];
470 const bool charIsLetter = (muscleInRange(c, 'a', 'z'))||(muscleInRange(c, 'A', 'Z'))||(muscleInRange(c, '0', '9')); // yes, digits count as letters, dontcha know
471 c = prevCharWasLetter ? (char)tolower(c) : (char)toupper(c);
472 prevCharWasLetter = charIsLetter;
473 }
474 return ret;
475 }
476
477 String String :: ToUpperCase() const
478 {
479 String ret(*this);
480 char * b = ret.GetBuffer();
481 for (uint32 i=0; i<ret.Length(); i++) b[i] = (char)toupper(b[i]);
482 return ret;
483 }
484
485 String String :: Trim() const
486 {
487 TCHECKPOINT;
488
489 const int32 len = (int32) Length();
490 const char * s = Cstr();
491 int32 startIdx; for (startIdx = 0; startIdx<len; startIdx++) if (!IsSpaceChar(s[startIdx])) break;
492 int32 endIdx; for (endIdx = len-1; endIdx>startIdx; endIdx--) if (!IsSpaceChar(s[endIdx])) break;
493 return String(*this, (uint32)startIdx, (uint32)(endIdx+1));
494 }
495
496 uint32 String :: GetNumInstancesOf(char ch) const
497 {
498 uint32 ret = 0;
499 for (const char * s = Cstr(); (*s != '\0'); s++) if (*s == ch) ret++;
500 return ret;
501 }
502
503 uint32 String :: GetNumInstancesOf(const String & substring) const
504 {
505 TCHECKPOINT;
506
507 uint32 ret = 0;
508 if (substring.HasChars())
509 {
510 uint32 lastIdx = 0;
511 int32 idx;
512 while((idx = IndexOf(substring, lastIdx)) >= 0)
513 {
514 ret++;
515 lastIdx = idx + substring.Length();
516 }
517 }
518 return ret;
519 }
520
521 uint32 String :: GetNumInstancesOf(const char * substring) const
522 {
523 TCHECKPOINT;
524
525 if (substring == NULL) substring = "";
526 uint32 ret = 0;
527 const uint32 substringLength = (uint32) strlen(substring);
528 if (substringLength > 0)
529 {
530 uint32 lastIdx = 0;
531 int32 idx;
532 while((idx = IndexOf(substring, lastIdx)) >= 0)
533 {
534 ret++;
535 lastIdx = idx + substringLength;
536 }
537 }
538 return ret;
539 }
540
541 String String :: Prepend(const String & str, uint32 count) const
542 {
543 TCHECKPOINT;
544
545 if (&str == this) return Prepend(String(str), count); // avoid self-entanglement
546
547 String ret;
548 const uint32 newLen = (count*str.Length())+Length();
549 if (ret.Prealloc(newLen) == B_NO_ERROR)
550 {
551 char * b = ret.GetBuffer();
552
553 if (str.HasChars())
554 {
555 for (uint32 i=0; i<count; i++)
556 {
557 memcpy(b, str(), str.Length());
558 b += str.Length();
559 }
560 }
561 if (HasChars())
562 {
563 memcpy(b, Cstr(), Length());
564 b += Length();
565 }
566
567 char * afterBuf = ret.GetBuffer();
568 ret._length = (uint32)(b-afterBuf);
569 afterBuf[ret._length] = '\0'; // terminate the string
570 }
571 return ret;
572 }
573
574 String String :: Prepend(const char * str, uint32 count) const
575 {
576 TCHECKPOINT;
577
578 if ((str == NULL)||(*str == '\0')) return *this;
579 else if (IsCharInLocalArray(str)) return Prepend(String(str), count); // avoid self-entanglement!
580 else
581 {
582 const uint32 sLen = (uint32) strlen(str);
583 String ret;
584 const uint32 newLen = (count*sLen)+Length();
585 if (ret.Prealloc(newLen) == B_NO_ERROR)
586 {
587 char * b = ret.GetBuffer();
588
589 if (sLen > 0)
590 {
591 for (uint32 i=0; i<count; i++)
592 {
593 memcpy(b, str, sLen);
594 b += sLen;
595 }
596 }
597 if (HasChars())
598 {
599 memcpy(b, Cstr(), Length());
600 b += Length();
601 }
602 char * afterBuf = ret.GetBuffer();
603 ret._length = (uint32)(b-afterBuf);
604 afterBuf[ret._length] = '\0'; // terminate the string
605 }
606 return ret;
607 }
608 }
609
610 String String :: Append(const String & str, uint32 count) const
611 {
612 TCHECKPOINT;
613
614 if (&str == this) return Append(String(str), count); // avoid self-entanglement
615
616 String ret;
617 const uint32 newLen = Length()+(count*str.Length());
618 if (ret.Prealloc(newLen) == B_NO_ERROR)
619 {
620 char * b = ret.GetBuffer();
621 if (HasChars())
622 {
623 memcpy(b, Cstr(), Length());
624 b += Length();
625 }
626 if (str.HasChars())
627 {
628 for (uint32 i=0; i<count; i++)
629 {
630 memcpy(b, str(), str.Length());
631 b += str.Length();
632 }
633 }
634 char * afterBuf = ret.GetBuffer();
635 ret._length = (uint32)(b-afterBuf);
636 afterBuf[ret._length] = '\0'; // terminate the string
637 }
638 return ret;
639 }
640
641 String String :: Append(const char * str, uint32 count) const
642 {
643 TCHECKPOINT;
644
645 if ((str == NULL)||(*str == '\0')) return *this;
646 else if (IsCharInLocalArray(str)) return Append(String(str), count); // avoid self-entanglement!
647 else
648 {
649 const uint32 sLen = (uint32) strlen(str);
650 String ret;
651 const uint32 newLen = Length()+(count*sLen);
652 if (ret.Prealloc(newLen) == B_NO_ERROR)
653 {
654 char * b = ret.GetBuffer();
655 if (HasChars())
656 {
657 memcpy(b, Cstr(), Length());
658 b += Length();
659 }
660 if (sLen > 0)
661 {
662 for (uint32 i=0; i<count; i++)
663 {
664 memcpy(b, str, sLen);
665 b += sLen;
666 }
667 }
668 char * afterBuf = ret.GetBuffer();
669 ret._length = (uint32) (b-afterBuf);
670 afterBuf[ret._length] = '\0'; // terminate the string
671 }
672 return ret;
673 }
674 }
675
676 String String :: AppendWord(const char * str, const char * sep) const
677 {
678 if ((str == NULL)||(*str == '\0')) return *this;
679 if ((HasChars())&&(strncmp(str, sep, strlen(sep)) != 0)&&(EndsWith(sep) == false)) return String(*this).Append(sep).Append(str);
680 else return String(*this).Append(str);
681 }
682
683 String String :: AppendWord(const String & str, const char * sep) const
684 {
685 if (str.IsEmpty()) return *this;
686 if ((HasChars())&&(str.StartsWith(sep) == false)&&(EndsWith(sep) == false)) return String(*this).Append(sep).Append(str);
687 else return String(*this).Append(str);
688 }
689
690 static uint32 NextPowerOfTwo(uint32 n)
691 {
692 // This code was stolen from: http://stackoverflow.com/a/1322548/131930
693
694 n--;
695 n |= n >> 1; // Divide by 2^k for consecutive doublings of k up to 32,
696 n |= n >> 2; // and then or the results.
697 n |= n >> 4;
698 n |= n >> 8;
699 n |= n >> 16;
700 n++; // The result is a number of 1 bits equal to the number
701 // of bits in the original number, plus 1. That's the
702 // next highest power of 2.
703 return n;
704 }
705
706 static uint32 GetNextBufferSize(uint32 bufLen)
707 {
708 // For very small strings, we'll try to conserve memory by betting that they won't expand much more
709 if (bufLen < 32) return bufLen+SMALL_MUSCLE_STRING_LENGTH;
710
711 static const uint32 STRING_PAGE_SIZE = 4096;
712 static const uint32 STRING_MALLOC_OVERHEAD = 12; // we assume that malloc() might need as many as 12 bytes for book keeping
713
714 // For medium-length strings, do a geometric expansion to reduce the number of reallocations
715 uint32 geomLen = NextPowerOfTwo((bufLen-1)*2);
716 #ifdef MUSCLE_ENABLE_MEMORY_TRACKING
717 geomLen -= sizeof(size_t); // so that the internal allocation size will be a power of two, after GlobalMemoryAllocator.cpp adds its header bytes
718 #endif
719 if (geomLen < (STRING_PAGE_SIZE-STRING_MALLOC_OVERHEAD)) return geomLen;
720
721 // For large (multi-page) allocations, we'll increase by one page. According to Trolltech, modern implementations
722 // of realloc() don't actually copy the entire large buffer, they just rearrange the memory map and add
723 // a new page to the end, so this will be more efficient than it appears.
724 const uint32 curNumPages = (bufLen+STRING_MALLOC_OVERHEAD)/STRING_PAGE_SIZE;
725 return ((curNumPages+1)*STRING_PAGE_SIZE)-STRING_MALLOC_OVERHEAD;
726 }
727
728 // This method tries to ensure that at least (newBufLen) chars
729 // are available for storing data in. (requestedBufLen) should include
730 // the terminating NUL. If (retainValue) is true, the current string value
731 // will be retained; otherwise it should be set right after this call returns...
732 status_t String :: EnsureBufferSize(uint32 requestedBufLen, bool retainValue, bool allowShrink)
733 {
734 if (allowShrink ? (requestedBufLen == _bufferLen) : (requestedBufLen <= _bufferLen)) return B_NO_ERROR;
735
736 // If we're doing a first-time allocation or a shrink, allocate exactly the number of the bytes requested.
737 // If it's a re-allocation, allocate more than requested in the hopes avoiding another realloc in the future.
738 char * newBuf = NULL;
739 const bool arrayWasDynamicallyAllocated = IsArrayDynamicallyAllocated();
740 const uint32 newBufLen = ((allowShrink)||(requestedBufLen <= SMALL_MUSCLE_STRING_LENGTH+1)||((IsEmpty())&&(!arrayWasDynamicallyAllocated))) ? requestedBufLen : GetNextBufferSize(requestedBufLen);
741 if (newBufLen == 0)
742 {
743 ClearAndFlush();
744 return B_NO_ERROR;
745 }
746
747 const bool goToSmallBufferMode = ((allowShrink)&&(newBufLen <= (SMALL_MUSCLE_STRING_LENGTH+1)));
748 const uint32 newMaxLength = newBufLen-1;
749 if (retainValue)
750 {
751 if (arrayWasDynamicallyAllocated)
752 {
753 if (goToSmallBufferMode)
754 {
755 char * bigBuffer = _strData._bigBuffer; // guaranteed not to be equal to _strData._smallBuffer. Gotta make this copy now because the memcpy() below will munge the pointer
756 memcpy(_strData._smallBuffer, bigBuffer, newBufLen); // copy the data back into our inline array
757 _strData._smallBuffer[newMaxLength] = '\0'; // make sure we're terminated (could be an issue if we're shrinking)
758 _length = muscleMin(_length, newMaxLength);
759 _bufferLen = sizeof(_strData._smallBuffer);
760 muscleFree(bigBuffer); // get rid of the dynamically allocated array we were using before
761 return B_NO_ERROR; // return now to avoid setting _strData._bigBuffer below
762 }
763 else
764 {
765 // Here we call muscleRealloc() to (hopefully) avoid unnecessary data copying
766 newBuf = (char *) muscleRealloc(_strData._bigBuffer, newBufLen);
767 if (newBuf == NULL) RETURN_OUT_OF_MEMORY;
768 }
769 }
770 else
771 {
772 if (goToSmallBufferMode)
773 {
774 // In the was-small-buffer, still-is-small-buffer case, all we need to do is truncate the string
775 _strData._smallBuffer[newMaxLength] = '\0';
776 _length = muscleMin(Length(), newMaxLength);
777 // Setting _bufferLen isn't necessary here, since we are already in small-mode
778 return B_NO_ERROR; // return now to avoid setting _strData._bigBuffer below
779 }
780 else
781 {
782 // Oops, muscleRealloc() won't do in this case.... we'll just have to copy the bytes over
783 newBuf = (char *) muscleAlloc(newBufLen);
784 if (newBuf == NULL) RETURN_OUT_OF_MEMORY;
785 memcpy(newBuf, GetBuffer(), muscleMin(Length()+1, newBufLen));
786 }
787 }
788 }
789 else
790 {
791 // If the caller doesn't care about retaining this String's value, then it's
792 // probably cheaper just to allocate a new buffer and free the old one.
793 if (goToSmallBufferMode)
794 {
795 ClearAndFlush(); // might as well just dump everything
796 return B_NO_ERROR; // return now to avoid setting _strData._bigBuffer below
797 }
798 else
799 {
800 newBuf = (char *) muscleAlloc(newBufLen);
801 if (newBuf == NULL) RETURN_OUT_OF_MEMORY;
802 newBuf[0] = '\0'; // avoid potential user-visible garbage bytes
803 if (arrayWasDynamicallyAllocated) muscleFree(_strData._bigBuffer);
804 }
805 }
806
807 newBuf[muscleMin(Length(), newMaxLength)] = '\0'; // ensure new char array is terminated (it might not be if allowShrink is true)
808 _strData._bigBuffer = newBuf;
809 _bufferLen = newBufLen;
810
811 return B_NO_ERROR;
812 }
813
814 String String :: Pad(uint32 minLength, bool padOnRight, char padChar) const
815 {
816 if (Length() < minLength)
817 {
818 const uint32 padLen = minLength-Length();
819 String temp; temp += padChar;
820 return (padOnRight) ? Append(temp, padLen) : Prepend(temp, padLen);
821 }
822 else return *this;
823 }
824
825 String String :: Indent(uint32 numIndentChars, char indentChar) const
826 {
827 if ((numIndentChars == 0)||(indentChar == '\0')) return *this;
828
829 const String pad = String().Pad(numIndentChars);
830 String ret;
831 if ((StartsWith('\r'))||(StartsWith('\n'))) ret = pad;
832
833 bool seenChars = false;
834 const char * s = Cstr();
835 while(*s)
836 {
837 if ((*s == '\n')||(*s == '\r')) seenChars = false;
838 else if (seenChars == false)
839 {
840 ret += pad;
841 seenChars = true;
842 }
843 ret += *s;
844 s++;
845 }
846 return ret;
847 }
848
849 String String :: WithoutSuffix(char c, uint32 maxToRemove) const
850 {
851 String ret = *this;
852 while(ret.EndsWith(c))
853 {
854 ret--;
855 if (--maxToRemove == 0) break;
856 }
857 return ret;
858 }
859
860 String String :: WithoutSuffix(const String & str, uint32 maxToRemove) const
861 {
862 if (str.IsEmpty()) return *this;
863
864 String ret = *this;
865 while(ret.EndsWith(str))
866 {
867 ret.TruncateChars(str.Length());
868 if (--maxToRemove == 0) break;
869 }
870 return ret;
871 }
872
873 String String :: WithoutPrefix(char c, uint32 maxToRemove) const
874 {
875 uint32 numInitialChars = 0;
876 const uint32 len = Length();
877 for (uint32 i=0; i<len; i++)
878 {
879 if ((*this)[i] == c)
880 {
881 numInitialChars++;
882 if (--maxToRemove == 0) break;
883 }
884 else break;
885 }
886
887 return Substring(numInitialChars);
888 }
889
890 String String :: WithoutPrefix(const String & str, uint32 maxToRemove) const
891 {
892 if ((str.IsEmpty())||(StartsWith(str) == false)) return *this;
893
894 String ret = *this;
895 while(ret.StartsWith(str))
896 {
897 ret = ret.Substring(str.Length());
898 if (--maxToRemove == 0) break;
899 }
900 return ret;
901 }
902
903 String String :: WithoutSuffixIgnoreCase(char c, uint32 maxToRemove) const
904 {
905 if (EndsWithIgnoreCase(c) == false) return *this;
906
907 String ret = *this;
908 while(ret.EndsWithIgnoreCase(c))
909 {
910 ret--;
911 if (--maxToRemove == 0) break;
912 }
913 return ret;
914 }
915
916 String String :: WithoutSuffixIgnoreCase(const String & str, uint32 maxToRemove) const
917 {
918 if ((str.IsEmpty())||(EndsWithIgnoreCase(str) == false)) return *this;
919
920 String ret = *this;
921 while(ret.EndsWithIgnoreCase(str))
922 {
923 ret.TruncateChars(str.Length());
924 if (--maxToRemove == 0) break;
925 }
926 return ret;
927 }
928
929 String String :: WithoutPrefixIgnoreCase(char c, uint32 maxToRemove) const
930 {
931 const char cU = (char) toupper(c);
932 const char cL = (char) tolower(c);
933
934 String ret = *this;
935 uint32 numInitialChars = 0;
936 for (uint32 i=0; i<ret.Length(); i++)
937 {
938 const char n = (*this)[i];
939 if ((n==cU)||(n==cL))
940 {
941 numInitialChars++;
942 if (--maxToRemove == 0) break;
943 }
944 else break;
945 }
946 return Substring(numInitialChars);
947 }
948
949 String String :: WithoutPrefixIgnoreCase(const String & str, uint32 maxToRemove) const
950 {
951 if ((str.IsEmpty())||(StartsWithIgnoreCase(str) == false)) return *this;
952
953 String ret = *this;
954 while(ret.StartsWithIgnoreCase(str))
955 {
956 ret = ret.Substring(str.Length());
957 if (--maxToRemove == 0) break;
958 }
959 return ret;
960 }
961
962 #define ARG_IMPLEMENTATION \
963 char buf[256]; \
964 muscleSprintf(buf, fmt, value); \
965 return ArgAux(buf)
966
967 String String :: Arg(bool value, const char * fmt) const
968 {
969 if (strstr(fmt, "%s")) return ArgAux(value?"true":"false");
970 else {ARG_IMPLEMENTATION;}
971 }
972
973 String String :: Arg(char value, const char * fmt) const {ARG_IMPLEMENTATION;}
974 String String :: Arg(unsigned char value, const char * fmt) const {ARG_IMPLEMENTATION;}
975 String String :: Arg(short value, const char * fmt) const {ARG_IMPLEMENTATION;}
976 String String :: Arg(unsigned short value, const char * fmt) const {ARG_IMPLEMENTATION;}
977 String String :: Arg(int value, const char * fmt) const {ARG_IMPLEMENTATION;}
978 String String :: Arg(unsigned int value, const char * fmt) const {ARG_IMPLEMENTATION;}
979 String String :: Arg(long value, const char * fmt) const {ARG_IMPLEMENTATION;}
980 String String :: Arg(unsigned long int value, const char * fmt) const {ARG_IMPLEMENTATION;}
981 String String :: Arg(long long value, const char * fmt) const {ARG_IMPLEMENTATION;}
982 String String :: Arg(unsigned long long value, const char * fmt) const {ARG_IMPLEMENTATION;}
983 String String :: Arg(double value, const char * fmt) const {ARG_IMPLEMENTATION;}
984 String String :: Arg(const String & value) const {return ArgAux(value());}
985 String String :: Arg(const char * value) const {return ArgAux(value);}
986
987 String String :: Arg(double f, uint32 minDigitsAfterDecimal, uint32 maxDigitsAfterDecimal) const
988 {
989 char buf[256];
990 if (maxDigitsAfterDecimal == MUSCLE_NO_LIMIT) muscleSprintf(buf, "%f", f);
991 else
992 {
993 char formatBuf[128];
994 muscleSprintf(formatBuf, "%%.0" UINT32_FORMAT_SPEC "f", maxDigitsAfterDecimal);
995 muscleSprintf(buf, formatBuf, f);
996 }
997
998 String ret = buf;
999
1000 // Start by removing all trailing zeroes from the String
1001 if (ret.Contains('.')) while(ret.EndsWith('0')) ret--;
1002 if (minDigitsAfterDecimal == 0)
1003 {
1004 if (ret.EndsWith('.')) ret--; // Remove trailing . for integer-style display
1005 }
1006 else
1007 {
1008 // Pad with 0's if necessary to meet the minDigitsAfterDecimal requirement
1009 int32 dotIdx = ret.LastIndexOf('.');
1010 if (dotIdx < 0) {ret += '.'; dotIdx = ret.Length()-1;} // semi-paranoia
1011 uint32 numDigitsPresent = (ret.Length()-dotIdx)-1;
1012 for(uint32 i=numDigitsPresent; i<minDigitsAfterDecimal; i++) ret += '0';
1013 }
1014 return ArgAux(buf);
1015 }
1016
1017 String String :: Arg(const Point & value, const char * fmt) const
1018 {
1019 char buf[512];
1020 muscleSprintf(buf, fmt, value.x(), value.y());
1021 return ArgAux(buf);
1022 }
1023
1024 String String :: Arg(const Rect & value, const char * fmt) const
1025 {
1026 char buf[512];
1027 muscleSprintf(buf, fmt, value.left(), value.top(), value.right(), value.bottom());
1028 return ArgAux(buf);
1029 }
1030
1031 String String :: Arg(const void * value) const
1032 {
1033 char buf[128];
1034 muscleSprintf(buf, "%p", value);
1035 return ArgAux(buf);
1036 }
1037
1038 String String :: ArgAux(const char * buf) const
1039 {
1040 TCHECKPOINT;
1041
1042 int32 lowestArg = -1;
1043 const char * s = Cstr();
1044 while(*s != '\0')
1045 {
1046 if (*s == '%')
1047 {
1048 s++;
1049 if (muscleInRange(*s, '0', '9'))
1050 {
1051 const int32 val = (int32) atol(s);
1052 lowestArg = (lowestArg < 0) ? val : muscleMin(val, lowestArg);
1053 while(muscleInRange(*s, '0', '9')) s++;
1054 }
1055 }
1056 else s++;
1057 }
1058
1059 if (lowestArg >= 0)
1060 {
1061 char token[64];
1062 muscleSprintf(token, "%%" INT32_FORMAT_SPEC, lowestArg);
1063 String ret(*this);
1064 (void) ret.Replace(token, buf);
1065 return ret;
1066 }
1067 else return *this;
1068 }
1069
1070 uint32 String :: ParseNumericSuffix(uint32 defaultValue) const
1071 {
1072 const char * s = Cstr();
1073 const char * n = s+Length(); // initially points to the NUL terminator
1074 while((n>s)&&(muscleInRange(*(n-1), '0', '9'))) n--; // move back to first char of numeric suffix
1075 return muscleInRange(*n, '0', '9') ? (uint32) atol(n) : defaultValue;
1076 }
1077
1078 String String :: WithoutNumericSuffix(uint32 * optRemovedSuffixValue) const
1079 {
1080 String ret(*this);
1081 String suffix;
1082 while(ret.HasChars())
1083 {
1084 const char c = ret[ret.Length()-1];
1085 if (muscleInRange(c, '0', '9'))
1086 {
1087 suffix += c;
1088 ret--;
1089 }
1090 else break;
1091 }
1092 if (optRemovedSuffixValue)
1093 {
1094 suffix.Reverse();
1095 *optRemovedSuffixValue = (uint32) atol(suffix());
1096 }
1097 return ret;
1098 }
1099
1100 // Stolen from: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B
1101 static uint32 GetLevenshteinDistanceAux(const char *shortString, uint32 shortStringLen, const char * longString, uint32 longStringLen, uint32 maxResult)
1102 {
1103 assert(shortStringLen<=longStringLen); // this makes clang++SA happy
1104
1105 const uint32 allocLen = shortStringLen+1;
1106 #ifdef __clang_analyzer__
1107 uint32 * columns = newnothrow uint32[allocLen]; // ClangSA doesn't like my tempBuf trick
1108 #else
1109 uint32 tempBuf[256]; // We'll try to avoid using the heap for small strings
1110 uint32 * columns = (allocLen > ARRAYITEMS(tempBuf)) ? newnothrow uint32[allocLen] : tempBuf;
1111 #endif
1112 if (columns == NULL)
1113 {
1114 WARN_OUT_OF_MEMORY;
1115 return maxResult;
1116 }
1117
1118 for (uint32 x=1; x<allocLen; x++) columns[x] = x;
1119 for (uint32 x=1; x<=longStringLen; x++)
1120 {
1121 columns[0] = x;
1122 for (uint32 y=1, lastdiag=(x-1); y<=shortStringLen; y++)
1123 {
1124 const uint32 olddiag = columns[y];
1125 columns[y] = muscleMin(columns[y]+1, columns[y-1]+1, lastdiag+((shortString[y-1]==longString[x-1])?0:1));
1126 lastdiag = olddiag;
1127 }
1128 if (columns[shortStringLen] >= maxResult) break;
1129 }
1130
1131 const uint32 ret = columns[shortStringLen];
1132 #ifdef __clang_analyzer__
1133 delete [] columns; // ClangSA doesn't like my tempBuf trick
1134 #else
1135 if (allocLen > ARRAYITEMS(tempBuf)) delete [] columns;
1136 #endif
1137 return muscleMin(ret, maxResult);
1138 }
1139
1140 static uint32 GetLevenshteinDistance(const char *s1, uint32 s1len, const char *s2, uint32 s2len, uint32 maxResult)
1141 {
1142 // Minimize the amount of heap memory required, by swapping the arguments if (s2) is shorter than (s1).
1143 // Since the function is commutative, this won't affect the resulting values
1144 return (s2len < s1len)
1145 ? GetLevenshteinDistanceAux(s2, s2len, s1, s1len, maxResult)
1146 : GetLevenshteinDistanceAux(s1, s1len, s2, s2len, maxResult);
1147 }
1148
1149 uint32 String :: GetDistanceTo(const String & otherString, uint32 maxResult) const
1150 {
1151 return GetLevenshteinDistance(Cstr(), Length(), otherString(), otherString.Length(), maxResult);
1152 }
1153
1154 uint32 String :: GetDistanceTo(const char * otherString, uint32 maxResult) const
1155 {
1156 return GetLevenshteinDistance(Cstr(), Length(), otherString?otherString:"", otherString?(uint32)strlen(otherString):(uint32)0, maxResult);
1157 }
1158
1159 #ifdef __APPLE__
1160 // Congratulations to Apple for making a seemingly trivial operation as painful as it could possibly be
1161 status_t String :: SetFromCFStringRef(const CFStringRef & cfStringRef)
1162 {
1163 status_t ret = B_NO_ERROR;
1164 if (cfStringRef != NULL)
1165 {
1166 char tempBuf[256]; // try to avoid a call to muscleAlloc() in most cases
1167 const uint32 allocLen = ((uint32)CFStringGetMaximumSizeForEncoding(CFStringGetLength(cfStringRef), kCFStringEncodingUTF8))+1;
1168 const bool doAlloc = (allocLen > sizeof(tempBuf));
1169
1170 char * str = doAlloc ? (char *)muscleAlloc(allocLen) : tempBuf;
1171 if (str)
1172 {
1173 ret = CFStringGetCString(cfStringRef, str, allocLen, kCFStringEncodingUTF8) ? SetCstr(str) : B_ERROR("CFStringGetCString() failed");
1174 if (doAlloc) muscleFree(str);
1175 }
1176 else RETURN_OUT_OF_MEMORY;
1177 }
1178 else Clear();
1179
1180 return ret;
1181 }
1182
1183 CFStringRef String :: ToCFStringRef() const
1184 {
1185 return CFStringCreateWithCString(NULL, Cstr(), kCFStringEncodingUTF8);
1186 }
1187 #endif
1188
1189 /* strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
1190 Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>
1191
1192 This software is provided 'as-is', without any express or implied
1193 warranty. In no event will the authors be held liable for any damages
1194 arising from the use of this software.
1195
1196 Permission is granted to anyone to use this software for any purpose,
1197 including commercial applications, and to alter it and redistribute it
1198 freely, subject to the following restrictions:
1199
1200 1. The origin of this software must not be misrepresented; you must not
1201 claim that you wrote the original software. If you use this software
1202 in a product, an acknowledgment in the product documentation would be
1203 appreciated but is not required.
1204 2. Altered source versions must be plainly marked as such, and must not be
1205 misrepresented as being the original software. (JAF-note: I have altered
1206 this software slightly -- it is not the same as the original code!)
1207 3. This notice may not be removed or altered from any source distribution.
1208 */
1209
1210 /* These are defined as macros to make it easier to adapt this code to
1211 * different characters types or comparison functions. */
1212 static inline int nat_isdigit(char a) {return isdigit((unsigned char) a);}
1213 static inline int nat_isspace(char a) {return isspace((unsigned char) a);}
1214 static inline char nat_toupper(char a) {return (char) toupper((unsigned char) a);}
1215
1216 static int nat_compare_right(char const *a, char const *b)
1217 {
1218 int bias = 0;
1219
1220 /* The longest run of digits wins. That aside, the greatest
1221 value wins, but we can't know that it will until we've scanned
1222 both numbers to know that they have the same magnitude, so we
1223 remember it in BIAS. */
1224 for (;; a++, b++)
1225 {
1226 if (!nat_isdigit(*a) && !nat_isdigit(*b)) return bias;
1227 else if (!nat_isdigit(*a)) return -1;
1228 else if (!nat_isdigit(*b)) return +1;
1229 else if (*a < *b)
1230 {
1231 if (!bias) bias = -1;
1232 }
1233 else if (*a > *b)
1234 {
1235 if (!bias) bias = +1;
1236 }
1237 else if ((!*a)&&(!*b)) return bias;
1238 }
1239 return 0;
1240 }
1241
1242 static int nat_compare_left(char const *a, char const *b)
1243 {
1244 /* Compare two left-aligned numbers: the first to have a different value wins. */
1245 while(1)
1246 {
1247 if ((!nat_isdigit(*a))&&(!nat_isdigit(*b))) return 0;
1248 else if (!nat_isdigit(*a)) return -1;
1249 else if (!nat_isdigit(*b)) return +1;
1250 else if (*a < *b) return -1;
1251 else if (*a > *b) return +1;
1252 ++a; ++b;
1253 }
1254 return 0;
1255 }
1256
1257 static int strnatcmp0(char const *a, char const *b, int fold_case)
1258 {
1259 int ai = 0;
1260 int bi = 0;
1261 while(1)
1262 {
1263 char ca = a[ai];
1264 char cb = b[bi];
1265
1266 /* skip over leading spaces or zeros */
1267 while(nat_isspace(ca)) ca = a[++ai];
1268 while(nat_isspace(cb)) cb = b[++bi];
1269
1270 /* process run of digits */
1271 if ((nat_isdigit(ca))&&(nat_isdigit(cb)))
1272 {
1273 int fractional = (ca == '0' || cb == '0');
1274 if (fractional)
1275 {
1276 int result = nat_compare_left(a+ai, b+bi);
1277 if (result != 0) return result;
1278 }
1279 else
1280 {
1281 int result = nat_compare_right(a+ai, b+bi);
1282 if (result != 0) return result;
1283 }
1284 }
1285
1286 /* The strings compare the same. Call strcmp() to break the tie. */
1287 if (!ca && !cb) return strcmp(a,b);
1288
1289 if (fold_case)
1290 {
1291 ca = nat_toupper(ca);
1292 cb = nat_toupper(cb);
1293 }
1294
1295 if (ca < cb) return -1;
1296 else if (ca > cb) return +1;
1297
1298 ++ai; ++bi;
1299 }
1300 }
1301
1302 static int strnatcmp(char const *a, char const *b) {return strnatcmp0(a, b, 0);}
1303 static int strnatcasecmp(char const *a, char const *b) {return strnatcmp0(a, b, 1);}
1304
1305 int NumericAwareStrcmp(const char * s1, const char * s2) {return strnatcmp( s1, s2);}
1306 int NumericAwareStrcasecmp(const char * s1, const char * s2) {return strnatcasecmp(s1, s2);}
1307
1308 } // end namespace muscle