neo/idlib/Dict.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "precompiled.h"
  30 #pragma hdrstop
  31
  32 idStrPool               idDict::globalKeys;
  33 idStrPool               idDict::globalValues;
  34
  35 /*
  36 ================
  37 idDict::operator=
  38
  39   clear existing key/value pairs and copy all key/value pairs from other
  40 ================
  41 */
  42 idDict &idDict::operator=( const idDict &other ) {
  43         int i;
  44
  45         // check for assignment to self
  46         if ( this == &other ) {
  47                 return *this;
  48         }
  49
  50         Clear();
  51
  52         args = other.args;
  53         argHash = other.argHash;
  54
  55         for ( i = 0; i < args.Num(); i++ ) {
  56                 args[i].key = globalKeys.CopyString( args[i].key );
  57                 args[i].value = globalValues.CopyString( args[i].value );
  58         }
  59
  60         return *this;
  61 }
  62
  63 /*
  64 ================
  65 idDict::Copy
  66
  67   copy all key value pairs without removing existing key/value pairs not present in the other dict
  68 ================
  69 */
  70 void idDict::Copy( const idDict &other ) {
  71         int i, n, *found;
  72         idKeyValue kv;
  73
  74         // check for assignment to self
  75         if ( this == &other ) {
  76                 return;
  77         }
  78
  79         n = other.args.Num();
  80
  81         if ( args.Num() ) {
  82                 found = (int *) _alloca16( other.args.Num() * sizeof( int ) );
  83         for ( i = 0; i < n; i++ ) {
  84                         found[i] = FindKeyIndex( other.args[i].GetKey() );
  85                 }
  86         } else {
  87                 found = NULL;
  88         }
  89
  90         for ( i = 0; i < n; i++ ) {
  91                 if ( found && found[i] != -1 ) {
  92                         // first set the new value and then free the old value to allow proper self copying
  93                         const idPoolStr *oldValue = args[found[i]].value;
  94                         args[found[i]].value = globalValues.CopyString( other.args[i].value );
  95                         globalValues.FreeString( oldValue );
  96                 } else {
  97                         kv.key = globalKeys.CopyString( other.args[i].key );
  98                         kv.value = globalValues.CopyString( other.args[i].value );
  99                         argHash.Add( argHash.GenerateKey( kv.GetKey(), false ), args.Append( kv ) );
 100                 }
 101         }
 102 }
 103
 104 /*
 105 ================
 106 idDict::TransferKeyValues
 107
 108   clear existing key/value pairs and transfer key/value pairs from other
 109 ================
 110 */
 111 void idDict::TransferKeyValues( idDict &other ) {
 112         int i, n;
 113
 114         if ( this == &other ) {
 115                 return;
 116         }
 117
 118         if ( other.args.Num() && other.args[0].key->GetPool() != &globalKeys ) {
 119                 common->FatalError( "idDict::TransferKeyValues: can't transfer values across a DLL boundary" );
 120                 return;
 121         }
 122
 123         Clear();
 124
 125         n = other.args.Num();
 126         args.SetNum( n );
 127         for ( i = 0; i < n; i++ ) {
 128                 args[i].key = other.args[i].key;
 129                 args[i].value = other.args[i].value;
 130         }
 131         argHash = other.argHash;
 132
 133         other.args.Clear();
 134         other.argHash.Free();
 135 }
 136
 137 /*
 138 ================
 139 idDict::Parse
 140 ================
 141 */
 142 bool idDict::Parse( idParser &parser ) {
 143         idToken token;
 144         idToken token2;
 145         bool    errors;
 146
 147         errors = false;
 148
 149         parser.ExpectTokenString( "{" );
 150         parser.ReadToken( &token );
 151         while( ( token.type != TT_PUNCTUATION ) || ( token != "}" ) ) {
 152                 if ( token.type != TT_STRING ) {
 153                         parser.Error( "Expected quoted string, but found '%s'", token.c_str() );
 154                 }
 155
 156                 if ( !parser.ReadToken( &token2 ) ) {
 157                         parser.Error( "Unexpected end of file" );
 158                 }
 159
 160                 if ( FindKey( token ) ) {
 161                         parser.Warning( "'%s' already defined", token.c_str() );
 162                         errors = true;
 163                 }
 164                 Set( token, token2 );
 165
 166                 if ( !parser.ReadToken( &token ) ) {
 167                         parser.Error( "Unexpected end of file" );
 168                 }
 169         }
 170
 171         return !errors;
 172 }
 173
 174 /*
 175 ================
 176 idDict::SetDefaults
 177 ================
 178 */
 179 void idDict::SetDefaults( const idDict *dict ) {
 180         int i, n;
 181         const idKeyValue *kv, *def;
 182         idKeyValue newkv;
 183
 184         n = dict->args.Num();
 185         for( i = 0; i < n; i++ ) {
 186                 def = &dict->args[i];
 187                 kv = FindKey( def->GetKey() );
 188                 if ( !kv ) {
 189                         newkv.key = globalKeys.CopyString( def->key );
 190                         newkv.value = globalValues.CopyString( def->value );
 191                         argHash.Add( argHash.GenerateKey( newkv.GetKey(), false ), args.Append( newkv ) );
 192                 }
 193         }
 194 }
 195
 196 /*
 197 ================
 198 idDict::Clear
 199 ================
 200 */
 201 void idDict::Clear( void ) {
 202         int i;
 203
 204         for( i = 0; i < args.Num(); i++ ) {
 205                 globalKeys.FreeString( args[i].key );
 206                 globalValues.FreeString( args[i].value );
 207         }
 208
 209         args.Clear();
 210         argHash.Free();
 211 }
 212
 213 /*
 214 ================
 215 idDict::Print
 216 ================
 217 */
 218 void idDict::Print() const {
 219         int i;
 220         int n;
 221
 222         n = args.Num();
 223         for( i = 0; i < n; i++ ) {
 224                 idLib::common->Printf( "%s = %s\n", args[i].GetKey().c_str(), args[i].GetValue().c_str() );
 225         }
 226 }
 227
 228 int KeyCompare( const idKeyValue *a, const idKeyValue *b ) {
 229         return idStr::Cmp( a->GetKey(), b->GetKey() );
 230 }
 231
 232 /*
 233 ================
 234 idDict::Checksum
 235 ================
 236 */
 237 int     idDict::Checksum( void ) const {
 238         unsigned long ret;
 239         int i, n;
 240
 241         idList<idKeyValue> sorted = args;
 242         sorted.Sort( KeyCompare );
 243         n = sorted.Num();
 244         CRC32_InitChecksum( ret );
 245         for( i = 0; i < n; i++ ) {
 246                 CRC32_UpdateChecksum( ret, sorted[i].GetKey().c_str(), sorted[i].GetKey().Length() );
 247                 CRC32_UpdateChecksum( ret, sorted[i].GetValue().c_str(), sorted[i].GetValue().Length() );
 248         }
 249         CRC32_FinishChecksum( ret );
 250         return ret;
 251 }
 252
 253 /*
 254 ================
 255 idDict::Allocated
 256 ================
 257 */
 258 size_t idDict::Allocated( void ) const {
 259         int             i;
 260         size_t  size;
 261
 262         size = args.Allocated() + argHash.Allocated();
 263         for( i = 0; i < args.Num(); i++ ) {
 264                 size += args[i].Size();
 265         }
 266
 267         return size;
 268 }
 269
 270 /*
 271 ================
 272 idDict::Set
 273 ================
 274 */
 275 void idDict::Set( const char *key, const char *value ) {
 276         int i;
 277         idKeyValue kv;
 278
 279         if ( key == NULL || key[0] == '\0' ) {
 280                 return;
 281         }
 282
 283         i = FindKeyIndex( key );
 284         if ( i != -1 ) {
 285                 // first set the new value and then free the old value to allow proper self copying
 286                 const idPoolStr *oldValue = args[i].value;
 287                 args[i].value = globalValues.AllocString( value );
 288                 globalValues.FreeString( oldValue );
 289         } else {
 290                 kv.key = globalKeys.AllocString( key );
 291                 kv.value = globalValues.AllocString( value );
 292                 argHash.Add( argHash.GenerateKey( kv.GetKey(), false ), args.Append( kv ) );
 293         }
 294 }
 295
 296 /*
 297 ================
 298 idDict::GetFloat
 299 ================
 300 */
 301 bool idDict::GetFloat( const char *key, const char *defaultString, float &out ) const {
 302         const char      *s;
 303         bool            found;
 304
 305         found = GetString( key, defaultString, &s );
 306         out = atof( s );
 307         return found;
 308 }
 309
 310 /*
 311 ================
 312 idDict::GetInt
 313 ================
 314 */
 315 bool idDict::GetInt( const char *key, const char *defaultString, int &out ) const {
 316         const char      *s;
 317         bool            found;
 318
 319         found = GetString( key, defaultString, &s );
 320         out = atoi( s );
 321         return found;
 322 }
 323
 324 /*
 325 ================
 326 idDict::GetBool
 327 ================
 328 */
 329 bool idDict::GetBool( const char *key, const char *defaultString, bool &out ) const {
 330         const char      *s;
 331         bool            found;
 332
 333         found = GetString( key, defaultString, &s );
 334         out = ( atoi( s ) != 0 );
 335         return found;
 336 }
 337
 338 /*
 339 ================
 340 idDict::GetAngles
 341 ================
 342 */
 343 bool idDict::GetAngles( const char *key, const char *defaultString, idAngles &out ) const {
 344         bool            found;
 345         const char      *s;
 346
 347         if ( !defaultString ) {
 348                 defaultString = "0 0 0";
 349         }
 350
 351         found = GetString( key, defaultString, &s );
 352         out.Zero();
 353         sscanf( s, "%f %f %f", &out.pitch, &out.yaw, &out.roll );
 354         return found;
 355 }
 356
 357 /*
 358 ================
 359 idDict::GetVector
 360 ================
 361 */
 362 bool idDict::GetVector( const char *key, const char *defaultString, idVec3 &out ) const {
 363         bool            found;
 364         const char      *s;
 365
 366         if ( !defaultString ) {
 367                 defaultString = "0 0 0";
 368         }
 369
 370         found = GetString( key, defaultString, &s );
 371         out.Zero();
 372         sscanf( s, "%f %f %f", &out.x, &out.y, &out.z );
 373         return found;
 374 }
 375
 376 /*
 377 ================
 378 idDict::GetVec2
 379 ================
 380 */
 381 bool idDict::GetVec2( const char *key, const char *defaultString, idVec2 &out ) const {
 382         bool            found;
 383         const char      *s;
 384
 385         if ( !defaultString ) {
 386                 defaultString = "0 0";
 387         }
 388
 389         found = GetString( key, defaultString, &s );
 390         out.Zero();
 391         sscanf( s, "%f %f", &out.x, &out.y );
 392         return found;
 393 }
 394
 395 /*
 396 ================
 397 idDict::GetVec4
 398 ================
 399 */
 400 bool idDict::GetVec4( const char *key, const char *defaultString, idVec4 &out ) const {
 401         bool            found;
 402         const char      *s;
 403
 404         if ( !defaultString ) {
 405                 defaultString = "0 0 0 0";
 406         }
 407
 408         found = GetString( key, defaultString, &s );
 409         out.Zero();
 410         sscanf( s, "%f %f %f %f", &out.x, &out.y, &out.z, &out.w );
 411         return found;
 412 }
 413
 414 /*
 415 ================
 416 idDict::GetMatrix
 417 ================
 418 */
 419 bool idDict::GetMatrix( const char *key, const char *defaultString, idMat3 &out ) const {
 420         const char      *s;
 421         bool            found;
 422
 423         if ( !defaultString ) {
 424                 defaultString = "1 0 0 0 1 0 0 0 1";
 425         }
 426
 427         found = GetString( key, defaultString, &s );
 428         out.Identity();         // sccanf has a bug in it on Mac OS 9.  Sigh.
 429         sscanf( s, "%f %f %f %f %f %f %f %f %f", &out[0].x, &out[0].y, &out[0].z, &out[1].x, &out[1].y, &out[1].z, &out[2].x, &out[2].y, &out[2].z );
 430         return found;
 431 }
 432
 433 /*
 434 ================
 435 WriteString
 436 ================
 437 */
 438 static void WriteString( const char *s, idFile *f ) {
 439         int     len = strlen( s );
 440         if ( len >= MAX_STRING_CHARS-1 ) {
 441                 idLib::common->Error( "idDict::WriteToFileHandle: bad string" );
 442         }
 443         f->Write( s, strlen(s) + 1 );
 444 }
 445
 446 /*
 447 ================
 448 idDict::FindKey
 449 ================
 450 */
 451 const idKeyValue *idDict::FindKey( const char *key ) const {
 452         int i, hash;
 453
 454         if ( key == NULL || key[0] == '\0' ) {
 455                 idLib::common->DWarning( "idDict::FindKey: empty key" );
 456                 return NULL;
 457         }
 458
 459         hash = argHash.GenerateKey( key, false );
 460         for ( i = argHash.First( hash ); i != -1; i = argHash.Next( i ) ) {
 461                 if ( args[i].GetKey().Icmp( key ) == 0 ) {
 462                         return &args[i];
 463                 }
 464         }
 465
 466         return NULL;
 467 }
 468
 469 /*
 470 ================
 471 idDict::FindKeyIndex
 472 ================
 473 */
 474 int idDict::FindKeyIndex( const char *key ) const {
 475
 476         if ( key == NULL || key[0] == '\0' ) {
 477                 idLib::common->DWarning( "idDict::FindKeyIndex: empty key" );
 478                 return NULL;
 479         }
 480
 481         int hash = argHash.GenerateKey( key, false );
 482         for ( int i = argHash.First( hash ); i != -1; i = argHash.Next( i ) ) {
 483                 if ( args[i].GetKey().Icmp( key ) == 0 ) {
 484                         return i;
 485                 }
 486         }
 487
 488         return -1;
 489 }
 490
 491 /*
 492 ================
 493 idDict::Delete
 494 ================
 495 */
 496 void idDict::Delete( const char *key ) {
 497         int hash, i;
 498
 499         hash = argHash.GenerateKey( key, false );
 500         for ( i = argHash.First( hash ); i != -1; i = argHash.Next( i ) ) {
 501                 if ( args[i].GetKey().Icmp( key ) == 0 ) {
 502                         globalKeys.FreeString( args[i].key );
 503                         globalValues.FreeString( args[i].value );
 504                         args.RemoveIndex( i );
 505                         argHash.RemoveIndex( hash, i );
 506                         break;
 507                 }
 508         }
 509
 510 #if 0
 511         // make sure all keys can still be found in the hash index
 512         for ( i = 0; i < args.Num(); i++ ) {
 513                 assert( FindKey( args[i].GetKey() ) != NULL );
 514         }
 515 #endif
 516 }
 517
 518 /*
 519 ================
 520 idDict::MatchPrefix
 521 ================
 522 */
 523 const idKeyValue *idDict::MatchPrefix( const char *prefix, const idKeyValue *lastMatch ) const {
 524         int     i;
 525         int len;
 526         int start;
 527
 528         assert( prefix );
 529         len = strlen( prefix );
 530
 531         start = -1;
 532         if ( lastMatch ) {
 533                 start = args.FindIndex( *lastMatch );
 534                 assert( start >= 0 );
 535                 if ( start < 1 ) {
 536                         start = 0;
 537                 }
 538         }
 539
 540         for( i = start + 1; i < args.Num(); i++ ) {
 541                 if ( !args[i].GetKey().Icmpn( prefix, len ) ) {
 542                         return &args[i];
 543                 }
 544         }
 545         return NULL;
 546 }
 547
 548 /*
 549 ================
 550 idDict::RandomPrefix
 551 ================
 552 */
 553 const char *idDict::RandomPrefix( const char *prefix, idRandom &random ) const {
 554         int count;
 555         const int MAX_RANDOM_KEYS = 2048;
 556         const char *list[MAX_RANDOM_KEYS];
 557         const idKeyValue *kv;
 558
 559         list[0] = "";
 560         for ( count = 0, kv = MatchPrefix( prefix ); kv && count < MAX_RANDOM_KEYS; kv = MatchPrefix( prefix, kv ) ) {
 561                 list[count++] = kv->GetValue().c_str();
 562         }
 563         return list[random.RandomInt( count )];
 564 }
 565
 566 /*
 567 ================
 568 idDict::WriteToFileHandle
 569 ================
 570 */
 571 void idDict::WriteToFileHandle( idFile *f ) const {
 572         int c = LittleLong( args.Num() );
 573         f->Write( &c, sizeof( c ) );
 574         for ( int i = 0; i < args.Num(); i++ ) {        // don't loop on the swapped count use the original
 575                 WriteString( args[i].GetKey().c_str(), f );
 576                 WriteString( args[i].GetValue().c_str(), f );
 577         }
 578 }
 579
 580 /*
 581 ================
 582 ReadString
 583 ================
 584 */
 585 static idStr ReadString( idFile *f ) {
 586         char    str[MAX_STRING_CHARS];
 587         int             len;
 588
 589         for ( len = 0; len < MAX_STRING_CHARS; len++ ) {
 590                 f->Read( (void *)&str[len], 1 );
 591                 if ( str[len] == 0 ) {
 592                         break;
 593                 }
 594         }
 595         if ( len == MAX_STRING_CHARS ) {
 596                 idLib::common->Error( "idDict::ReadFromFileHandle: bad string" );
 597         }
 598
 599         return idStr( str );
 600 }
 601
 602 /*
 603 ================
 604 idDict::ReadFromFileHandle
 605 ================
 606 */
 607 void idDict::ReadFromFileHandle( idFile *f ) {
 608         int c;
 609         idStr key, val;
 610
 611         Clear();
 612
 613         f->Read( &c, sizeof( c ) );
 614         c = LittleLong( c );
 615         for ( int i = 0; i < c; i++ ) {
 616                 key = ReadString( f );
 617                 val = ReadString( f );
 618                 Set( key, val );
 619         }
 620 }
 621
 622 /*
 623 ================
 624 idDict::Init
 625 ================
 626 */
 627 void idDict::Init( void ) {
 628         globalKeys.SetCaseSensitive( false );
 629         globalValues.SetCaseSensitive( true );
 630 }
 631
 632 /*
 633 ================
 634 idDict::Shutdown
 635 ================
 636 */
 637 void idDict::Shutdown( void ) {
 638         globalKeys.Clear();
 639         globalValues.Clear();
 640 }
 641
 642 /*
 643 ================
 644 idDict::ShowMemoryUsage_f
 645 ================
 646 */
 647 void idDict::ShowMemoryUsage_f( const idCmdArgs &args ) {
 648         idLib::common->Printf( "%5d KB in %d keys\n", globalKeys.Size() >> 10, globalKeys.Num() );
 649         idLib::common->Printf( "%5d KB in %d values\n", globalValues.Size() >> 10, globalValues.Num() );
 650 }
 651
 652 /*
 653 ================
 654 idDictStringSortCmp
 655 ================
 656 */
 657 // NOTE: the const wonkyness is required to make msvc happy
 658 template<>
 659 ID_INLINE int idListSortCompare( const idPoolStr * const *a, const idPoolStr * const *b ) {
 660         return (*a)->Icmp( **b );
 661 }
 662
 663 /*
 664 ================
 665 idDict::ListKeys_f
 666 ================
 667 */
 668 void idDict::ListKeys_f( const idCmdArgs &args ) {
 669         int i;
 670         idList<const idPoolStr *> keyStrings;
 671
 672         for ( i = 0; i < globalKeys.Num(); i++ ) {
 673                 keyStrings.Append( globalKeys[i] );
 674         }
 675         keyStrings.Sort();
 676         for ( i = 0; i < keyStrings.Num(); i++ ) {
 677                 idLib::common->Printf( "%s\n", keyStrings[i]->c_str() );
 678         }
 679         idLib::common->Printf( "%5d keys\n", keyStrings.Num() );
 680 }
 681
 682 /*
 683 ================
 684 idDict::ListValues_f
 685 ================
 686 */
 687 void idDict::ListValues_f( const idCmdArgs &args ) {
 688         int i;
 689         idList<const idPoolStr *> valueStrings;
 690
 691         for ( i = 0; i < globalValues.Num(); i++ ) {
 692                 valueStrings.Append( globalValues[i] );
 693         }
 694         valueStrings.Sort();
 695         for ( i = 0; i < valueStrings.Num(); i++ ) {
 696                 idLib::common->Printf( "%s\n", valueStrings[i]->c_str() );
 697         }
 698         idLib::common->Printf( "%5d values\n", valueStrings.Num() );
 699 }