oculus1: cfe4979ab3eb libovr/Src/Kernel/OVR

oculus1

view libovr/Src/Kernel/OVR_String.cpp @ 17:cfe4979ab3eb

ops, minor error in the last commit

author	John Tsiombikas <nuclear@member.fsf.org>
date	Sat, 21 Sep 2013 07:09:48 +0300
parents	e2f9e4603129
children

line source

1 /************************************************************************************

3 Filename : OVR_String.cpp

4 Content : String UTF8 string implementation with copy-on-write semantics

5 (thread-safe for assignment but not modification).

6 Created : September 19, 2012

7 Notes :

11 Use of this software is subject to the terms of the Oculus license

12 agreement provided at the time of installation or download, or which

13 otherwise accompanies this software in either electronic or hard copy form.

15 ************************************************************************************/

17 #include "OVR_String.h"

19 #include <stdlib.h>

20 #include <ctype.h>

22 #ifdef OVR_OS_QNX

23 # include <strings.h>

24 #endif

26 namespace OVR {

28 #define String_LengthIsSize (UPInt(1) << String::Flag_LengthIsSizeShift)

30 String::DataDesc String::NullData = {String_LengthIsSize, 1, {0} };

33 String::String()

34 {

35 pData = &NullData;

36 pData->AddRef();

37 };

39 String::String(const char* pdata)

40 {

41 // Obtain length in bytes; it doesn't matter if _data is UTF8.

42 UPInt size = pdata ? OVR_strlen(pdata) : 0;

43 pData = AllocDataCopy1(size, 0, pdata, size);

44 };

46 String::String(const char* pdata1, const char* pdata2, const char* pdata3)

47 {

48 // Obtain length in bytes; it doesn't matter if _data is UTF8.

49 UPInt size1 = pdata1 ? OVR_strlen(pdata1) : 0;

50 UPInt size2 = pdata2 ? OVR_strlen(pdata2) : 0;

51 UPInt size3 = pdata3 ? OVR_strlen(pdata3) : 0;

53 DataDesc *pdataDesc = AllocDataCopy2(size1 + size2 + size3, 0,

54 pdata1, size1, pdata2, size2);

55 memcpy(pdataDesc->Data + size1 + size2, pdata3, size3);

56 pData = pdataDesc;

57 }

59 String::String(const char* pdata, UPInt size)

60 {

61 OVR_ASSERT((size == 0) || (pdata != 0));

62 pData = AllocDataCopy1(size, 0, pdata, size);

63 };

66 String::String(const InitStruct& src, UPInt size)

67 {

68 pData = AllocData(size, 0);

69 src.InitString(GetData()->Data, size);

70 }

72 String::String(const String& src)

73 {

74 pData = src.GetData();

75 pData->AddRef();

76 }

78 String::String(const StringBuffer& src)

79 {

80 pData = AllocDataCopy1(src.GetSize(), 0, src.ToCStr(), src.GetSize());

81 }

83 String::String(const wchar_t* data)

84 {

85 pData = &NullData;

86 pData->AddRef();

87 // Simplified logic for wchar_t constructor.

88 if (data)

89 *this = data;

90 }

93 String::DataDesc* String::AllocData(UPInt size, UPInt lengthIsSize)

94 {

95 String::DataDesc* pdesc;

97 if (size == 0)

98 {

99 pdesc = &NullData;

100 pdesc->AddRef();

101 return pdesc;

102 }

103

104 pdesc = (DataDesc*)OVR_ALLOC(sizeof(DataDesc)+ size);

105 pdesc->Data[size] = 0;

106 pdesc->RefCount = 1;

107 pdesc->Size = size | lengthIsSize;

108 return pdesc;

109 }

110

111

112 String::DataDesc* String::AllocDataCopy1(UPInt size, UPInt lengthIsSize,

113 const char* pdata, UPInt copySize)

114 {

115 String::DataDesc* pdesc = AllocData(size, lengthIsSize);

116 memcpy(pdesc->Data, pdata, copySize);

117 return pdesc;

118 }

119

120 String::DataDesc* String::AllocDataCopy2(UPInt size, UPInt lengthIsSize,

121 const char* pdata1, UPInt copySize1,

122 const char* pdata2, UPInt copySize2)

123 {

124 String::DataDesc* pdesc = AllocData(size, lengthIsSize);

125 memcpy(pdesc->Data, pdata1, copySize1);

126 memcpy(pdesc->Data + copySize1, pdata2, copySize2);

127 return pdesc;

128 }

129

130

131 UPInt String::GetLength() const

132 {

133 // Optimize length accesses for non-UTF8 character strings.

134 DataDesc* pdata = GetData();

135 UPInt length, size = pdata->GetSize();

136

137 if (pdata->LengthIsSize())

138 return size;

139

140 length = (UPInt)UTF8Util::GetLength(pdata->Data, (UPInt)size);

141

142 if (length == size)

143 pdata->Size |= String_LengthIsSize;

144

145 return length;

146 }

147

148

149 //static UInt32 String_CharSearch(const char* buf, )

150

151

152 UInt32 String::GetCharAt(UPInt index) const

153 {

154 SPInt i = (SPInt) index;

155 DataDesc* pdata = GetData();

156 const char* buf = pdata->Data;

157 UInt32 c;

158

159 if (pdata->LengthIsSize())

160 {

161 OVR_ASSERT(index < pdata->GetSize());

162 buf += i;

163 return UTF8Util::DecodeNextChar_Advance0(&buf);

164 }

165

166 c = UTF8Util::GetCharAt(index, buf, pdata->GetSize());

167 return c;

168 }

169

170 UInt32 String::GetFirstCharAt(UPInt index, const char** offset) const

171 {

172 DataDesc* pdata = GetData();

173 SPInt i = (SPInt) index;

174 const char* buf = pdata->Data;

175 const char* end = buf + pdata->GetSize();

176 UInt32 c;

177

178 do

179 {

180 c = UTF8Util::DecodeNextChar_Advance0(&buf);

181 i--;

182

183 if (buf >= end)

184 {

185 // We've hit the end of the string; don't go further.

186 OVR_ASSERT(i == 0);

187 return c;

188 }

189 } while (i >= 0);

190

191 *offset = buf;

192

193 return c;

194 }

195

196 UInt32 String::GetNextChar(const char** offset) const

197 {

198 return UTF8Util::DecodeNextChar(offset);

199 }

200

201

202

203 void String::AppendChar(UInt32 ch)

204 {

205 DataDesc* pdata = GetData();

206 UPInt size = pdata->GetSize();

207 char buff[8];

208 SPInt encodeSize = 0;

209

210 // Converts ch into UTF8 string and fills it into buff.

211 UTF8Util::EncodeChar(buff, &encodeSize, ch);

212 OVR_ASSERT(encodeSize >= 0);

213

214 SetData(AllocDataCopy2(size + (UPInt)encodeSize, 0,

215 pdata->Data, size, buff, (UPInt)encodeSize));

216 pdata->Release();

217 }

218

219

220 void String::AppendString(const wchar_t* pstr, SPInt len)

221 {

222 if (!pstr)

223 return;

224

225 DataDesc* pdata = GetData();

226 UPInt oldSize = pdata->GetSize();

227 UPInt encodeSize = (UPInt)UTF8Util::GetEncodeStringSize(pstr, len);

228

229 DataDesc* pnewData = AllocDataCopy1(oldSize + (UPInt)encodeSize, 0,

230 pdata->Data, oldSize);

231 UTF8Util::EncodeString(pnewData->Data + oldSize, pstr, len);

232

233 SetData(pnewData);

234 pdata->Release();

235 }

236

237

238 void String::AppendString(const char* putf8str, SPInt utf8StrSz)

239 {

240 if (!putf8str || !utf8StrSz)

241 return;

242 if (utf8StrSz == -1)

243 utf8StrSz = (SPInt)OVR_strlen(putf8str);

244

245 DataDesc* pdata = GetData();

246 UPInt oldSize = pdata->GetSize();

247

248 SetData(AllocDataCopy2(oldSize + (UPInt)utf8StrSz, 0,

249 pdata->Data, oldSize, putf8str, (UPInt)utf8StrSz));

250 pdata->Release();

251 }

252

253 void String::AssignString(const InitStruct& src, UPInt size)

254 {

255 DataDesc* poldData = GetData();

256 DataDesc* pnewData = AllocData(size, 0);

257 src.InitString(pnewData->Data, size);

258 SetData(pnewData);

259 poldData->Release();

260 }

261

262 void String::AssignString(const char* putf8str, UPInt size)

263 {

264 DataDesc* poldData = GetData();

265 SetData(AllocDataCopy1(size, 0, putf8str, size));

266 poldData->Release();

267 }

268

269 void String::operator = (const char* pstr)

270 {

271 AssignString(pstr, pstr ? OVR_strlen(pstr) : 0);

272 }

273

274 void String::operator = (const wchar_t* pwstr)

275 {

276 DataDesc* poldData = GetData();

277 UPInt size = pwstr ? (UPInt)UTF8Util::GetEncodeStringSize(pwstr) : 0;

278

279 DataDesc* pnewData = AllocData(size, 0);

280 UTF8Util::EncodeString(pnewData->Data, pwstr);

281 SetData(pnewData);

282 poldData->Release();

283 }

284

285

286 void String::operator = (const String& src)

287 {

288 DataDesc* psdata = src.GetData();

289 DataDesc* pdata = GetData();

290

291 SetData(psdata);

292 psdata->AddRef();

293 pdata->Release();

294 }

295

296

297 void String::operator = (const StringBuffer& src)

298 {

299 DataDesc* polddata = GetData();

300 SetData(AllocDataCopy1(src.GetSize(), 0, src.ToCStr(), src.GetSize()));

301 polddata->Release();

302 }

303

304 void String::operator += (const String& src)

305 {

306 DataDesc *pourData = GetData(),

307 *psrcData = src.GetData();

308 UPInt ourSize = pourData->GetSize(),

309 srcSize = psrcData->GetSize();

310 UPInt lflag = pourData->GetLengthFlag() & psrcData->GetLengthFlag();

311

312 SetData(AllocDataCopy2(ourSize + srcSize, lflag,

313 pourData->Data, ourSize, psrcData->Data, srcSize));

314 pourData->Release();

315 }

316

317

318 String String::operator + (const char* str) const

319 {

320 String tmp1(*this);

321 tmp1 += (str ? str : "");

322 return tmp1;

323 }

324

325 String String::operator + (const String& src) const

326 {

327 String tmp1(*this);

328 tmp1 += src;

329 return tmp1;

330 }

331

332 void String::Remove(UPInt posAt, SPInt removeLength)

333 {

334 DataDesc* pdata = GetData();

335 UPInt oldSize = pdata->GetSize();

336 // Length indicates the number of characters to remove.

337 UPInt length = GetLength();

338

339 // If index is past the string, nothing to remove.

340 if (posAt >= length)

341 return;

342 // Otherwise, cap removeLength to the length of the string.

343 if ((posAt + removeLength) > length)

344 removeLength = length - posAt;

345

346 // Get the byte position of the UTF8 char at position posAt.

347 SPInt bytePos = UTF8Util::GetByteIndex(posAt, pdata->Data, oldSize);

348 SPInt removeSize = UTF8Util::GetByteIndex(removeLength, pdata->Data + bytePos, oldSize-bytePos);

349

350 SetData(AllocDataCopy2(oldSize - removeSize, pdata->GetLengthFlag(),

351 pdata->Data, bytePos,

352 pData->Data + bytePos + removeSize, (oldSize - bytePos - removeSize)));

353 pdata->Release();

354 }

355

356

357 String String::Substring(UPInt start, UPInt end) const

358 {

359 UPInt length = GetLength();

360 if ((start >= length) || (start >= end))

361 return String();

362

363 DataDesc* pdata = GetData();

364

365 // If size matches, we know the exact index range.

366 if (pdata->LengthIsSize())

367 return String(pdata->Data + start, end - start);

368

369 // Get position of starting character.

370 SPInt byteStart = UTF8Util::GetByteIndex(start, pdata->Data, pdata->GetSize());

371 SPInt byteSize = UTF8Util::GetByteIndex(end - start, pdata->Data + byteStart, pdata->GetSize()-byteStart);

372 return String(pdata->Data + byteStart, (UPInt)byteSize);

373 }

374

375 void String::Clear()

376 {

377 NullData.AddRef();

378 GetData()->Release();

379 SetData(&NullData);

380 }

381

382

383 String String::ToUpper() const

384 {

385 UInt32 c;

386 const char* psource = GetData()->Data;

387 const char* pend = psource + GetData()->GetSize();

388 String str;

389 SPInt bufferOffset = 0;

390 char buffer[512];

391

392 while(psource < pend)

393 {

394 do {

395 c = UTF8Util::DecodeNextChar_Advance0(&psource);

396 UTF8Util::EncodeChar(buffer, &bufferOffset, OVR_towupper(wchar_t(c)));

397 } while ((psource < pend) && (bufferOffset < SPInt(sizeof(buffer)-8)));

398

399 // Append string a piece at a time.

400 str.AppendString(buffer, bufferOffset);

401 bufferOffset = 0;

402 }

403

404 return str;

405 }

406

407 String String::ToLower() const

408 {

409 UInt32 c;

410 const char* psource = GetData()->Data;

411 const char* pend = psource + GetData()->GetSize();

412 String str;

413 SPInt bufferOffset = 0;

414 char buffer[512];

415

416 while(psource < pend)

417 {

418 do {

419 c = UTF8Util::DecodeNextChar_Advance0(&psource);

420 UTF8Util::EncodeChar(buffer, &bufferOffset, OVR_towlower(wchar_t(c)));

421 } while ((psource < pend) && (bufferOffset < SPInt(sizeof(buffer)-8)));

422

423 // Append string a piece at a time.

424 str.AppendString(buffer, bufferOffset);

425 bufferOffset = 0;

426 }

427

428 return str;

429 }

430

431

432

433 String& String::Insert(const char* substr, UPInt posAt, SPInt strSize)

434 {

435 DataDesc* poldData = GetData();

436 UPInt oldSize = poldData->GetSize();

437 UPInt insertSize = (strSize < 0) ? OVR_strlen(substr) : (UPInt)strSize;

438 UPInt byteIndex = (poldData->LengthIsSize()) ?

439 posAt : (UPInt)UTF8Util::GetByteIndex(posAt, poldData->Data, oldSize);

440

441 OVR_ASSERT(byteIndex <= oldSize);

442

443 DataDesc* pnewData = AllocDataCopy2(oldSize + insertSize, 0,

444 poldData->Data, byteIndex, substr, insertSize);

445 memcpy(pnewData->Data + byteIndex + insertSize,

446 poldData->Data + byteIndex, oldSize - byteIndex);

447 SetData(pnewData);

448 poldData->Release();

449 return *this;

450 }

451

452 /*

453 String& String::Insert(const UInt32* substr, UPInt posAt, SPInt len)

454 {

455 for (SPInt i = 0; i < len; ++i)

456 {

457 UPInt charw = InsertCharAt(substr[i], posAt);

458 posAt += charw;

459 }

460 return *this;

461 }

462 */

463

464 UPInt String::InsertCharAt(UInt32 c, UPInt posAt)

465 {

466 char buf[8];

467 SPInt index = 0;

468 UTF8Util::EncodeChar(buf, &index, c);

469 OVR_ASSERT(index >= 0);

470 buf[(UPInt)index] = 0;

471

472 Insert(buf, posAt, index);

473 return (UPInt)index;

474 }

475

476

477 int String::CompareNoCase(const char* a, const char* b)

478 {

479 return OVR_stricmp(a, b);

480 }

481

482 int String::CompareNoCase(const char* a, const char* b, SPInt len)

483 {

484 if (len)

485 {

486 SPInt f,l;

487 SPInt slen = len;

488 const char *s = b;

489 do {

490 f = (SPInt)OVR_tolower((int)(*(a++)));

491 l = (SPInt)OVR_tolower((int)(*(b++)));

492 } while (--len && f && (f == l) && *b != 0);

493

494 if (f == l && (len != 0 || *b != 0))

495 {

496 f = (SPInt)slen;

497 l = (SPInt)OVR_strlen(s);

498 return int(f - l);

499 }

500

501 return int(f - l);

502 }

503 else

504 return (0-(int)OVR_strlen(b));

505 }

506

507 // ***** Implement hash static functions

508

509 // Hash function

510 UPInt String::BernsteinHashFunction(const void* pdataIn, UPInt size, UPInt seed)

511 {

512 const UByte* pdata = (const UByte*) pdataIn;

513 UPInt h = seed;

514 while (size > 0)

515 {

516 size--;

517 h = ((h << 5) + h) ^ (unsigned) pdata[size];

518 }

519

520 return h;

521 }

522

523 // Hash function, case-insensitive

524 UPInt String::BernsteinHashFunctionCIS(const void* pdataIn, UPInt size, UPInt seed)

525 {

526 const UByte* pdata = (const UByte*) pdataIn;

527 UPInt h = seed;

528 while (size > 0)

529 {

530 size--;

531 h = ((h << 5) + h) ^ OVR_tolower(pdata[size]);

532 }

533

534 // Alternative: "sdbm" hash function, suggested at same web page above.

535 // h = 0;

536 // for bytes { h = (h << 16) + (h << 6) - hash + *p; }

537 return h;

538 }

539

540

541

542 // ***** String Buffer used for Building Strings

543

544

545 #define OVR_SBUFF_DEFAULT_GROW_SIZE 512

546 // Constructors / Destructor.

547 StringBuffer::StringBuffer()

548 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

549 {

550 }

551

552 StringBuffer::StringBuffer(UPInt growSize)

553 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

554 {

555 SetGrowSize(growSize);

556 }

557

558 StringBuffer::StringBuffer(const char* data)

559 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

560 {

561 *this = data;

562 }

563

564 StringBuffer::StringBuffer(const char* data, UPInt dataSize)

565 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

566 {

567 AppendString(data, dataSize);

568 }

569

570 StringBuffer::StringBuffer(const String& src)

571 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

572 {

573 AppendString(src.ToCStr(), src.GetSize());

574 }

575

576 StringBuffer::StringBuffer(const StringBuffer& src)

577 : pData(NULL), Size(0), BufferSize(src.GetGrowSize()), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

578 {

579 AppendString(src.ToCStr(), src.GetSize());

580 LengthIsSize = src.LengthIsSize;

581 }

582

583 StringBuffer::StringBuffer(const wchar_t* data)

584 : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)

585 {

586 *this = data;

587 }

588

589 StringBuffer::~StringBuffer()

590 {

591 if (pData)

592 OVR_FREE(pData);

593 }

594 void StringBuffer::SetGrowSize(UPInt growSize)

595 {

596 if (growSize <= 16)

597 GrowSize = 16;

598 else

599 {

600 UByte bits = Alg::UpperBit(UInt32(growSize-1));

601 UPInt size = 1<<bits;

602 GrowSize = size == growSize ? growSize : size;

603 }

604 }

605

606 UPInt StringBuffer::GetLength() const

607 {

608 UPInt length, size = GetSize();

609 if (LengthIsSize)

610 return size;

611

612 length = (UPInt)UTF8Util::GetLength(pData, (UPInt)GetSize());

613

614 if (length == GetSize())

615 LengthIsSize = true;

616 return length;

617 }

618

619 void StringBuffer::Reserve(UPInt _size)

620 {

621 if (_size >= BufferSize) // >= because of trailing zero! (!AB)

622 {

623 BufferSize = (_size + 1 + GrowSize - 1)& ~(GrowSize-1);

624 if (!pData)

625 pData = (char*)OVR_ALLOC(BufferSize);

626 else

627 pData = (char*)OVR_REALLOC(pData, BufferSize);

628 }

629 }

630 void StringBuffer::Resize(UPInt _size)

631 {

632 Reserve(_size);

633 LengthIsSize = false;

634 Size = _size;

635 if (pData)

636 pData[Size] = 0;

637 }

638

639 void StringBuffer::Clear()

640 {

641 Resize(0);

642 /*

643 if (pData != pEmptyNullData)

644 {

645 OVR_FREE(pHeap, pData);

646 pData = pEmptyNullData;

647 Size = BufferSize = 0;

648 LengthIsSize = false;

649 }

650 */

651 }

652 // Appends a character

653 void StringBuffer::AppendChar(UInt32 ch)

654 {

655 char buff[8];

656 UPInt origSize = GetSize();

657

658 // Converts ch into UTF8 string and fills it into buff. Also increments index according to the number of bytes

659 // in the UTF8 string.

660 SPInt srcSize = 0;

661 UTF8Util::EncodeChar(buff, &srcSize, ch);

662 OVR_ASSERT(srcSize >= 0);

663

664 UPInt size = origSize + srcSize;

665 Resize(size);

666 memcpy(pData + origSize, buff, srcSize);

667 }

668

669 // Append a string

670 void StringBuffer::AppendString(const wchar_t* pstr, SPInt len)

671 {

672 if (!pstr)

673 return;

674

675 SPInt srcSize = UTF8Util::GetEncodeStringSize(pstr, len);

676 UPInt origSize = GetSize();

677 UPInt size = srcSize + origSize;

678

679 Resize(size);

680 UTF8Util::EncodeString(pData + origSize, pstr, len);

681 }

682

683 void StringBuffer::AppendString(const char* putf8str, SPInt utf8StrSz)

684 {

685 if (!putf8str || !utf8StrSz)

686 return;

687 if (utf8StrSz == -1)

688 utf8StrSz = (SPInt)OVR_strlen(putf8str);

689

690 UPInt origSize = GetSize();

691 UPInt size = utf8StrSz + origSize;

692

693 Resize(size);

694 memcpy(pData + origSize, putf8str, utf8StrSz);

695 }

696

697

698 void StringBuffer::operator = (const char* pstr)

699 {

700 pstr = pstr ? pstr : "";

701 UPInt size = OVR_strlen(pstr);

702 Resize(size);

703 memcpy(pData, pstr, size);

704 }

705

706 void StringBuffer::operator = (const wchar_t* pstr)

707 {

708 pstr = pstr ? pstr : L"";

709 UPInt size = (UPInt)UTF8Util::GetEncodeStringSize(pstr);

710 Resize(size);

711 UTF8Util::EncodeString(pData, pstr);

712 }

713

714 void StringBuffer::operator = (const String& src)

715 {

716 Resize(src.GetSize());

717 memcpy(pData, src.ToCStr(), src.GetSize());

718 }

719

720

721 // Inserts substr at posAt

722 void StringBuffer::Insert(const char* substr, UPInt posAt, SPInt len)

723 {

724 UPInt oldSize = Size;

725 UPInt insertSize = (len < 0) ? OVR_strlen(substr) : (UPInt)len;

726 UPInt byteIndex = LengthIsSize ? posAt :

727 (UPInt)UTF8Util::GetByteIndex(posAt, pData, (SPInt)Size);

728

729 OVR_ASSERT(byteIndex <= oldSize);

730 Reserve(oldSize + insertSize);

731

732 memmove(pData + byteIndex + insertSize, pData + byteIndex, oldSize - byteIndex + 1);

733 memcpy (pData + byteIndex, substr, insertSize);

734 LengthIsSize = false;

735 Size = oldSize + insertSize;

736 pData[Size] = 0;

737 }

738

739 // Inserts character at posAt

740 UPInt StringBuffer::InsertCharAt(UInt32 c, UPInt posAt)

741 {

742 char buf[8];

743 SPInt len = 0;

744 UTF8Util::EncodeChar(buf, &len, c);

745 OVR_ASSERT(len >= 0);

746 buf[(UPInt)len] = 0;

747

748 Insert(buf, posAt, len);

749 return (UPInt)len;

750 }

751

752 } // OVR