1 /* 2 ** Copyright (c) 1999, 2000 D. Richard Hipp 3 ** 4 ** This program is free software; you can redistribute it and/or 5 ** modify it under the terms of the GNU General Public 6 ** License as published by the Free Software Foundation; either 7 ** version 2 of the License, or (at your option) any later version. 8 ** 9 ** This program is distributed in the hope that it will be useful, 10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of 11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 ** General Public License for more details. 13 ** 14 ** You should have received a copy of the GNU General Public 15 ** License along with this library; if not, write to the 16 ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 ** Boston, MA 02111-1307, USA. 18 ** 19 ** Author contact information: 20 ** [email protected] 21 ** http://www.hwaci.com/drh/ 22 ** 23 ************************************************************************* 24 ** Utility functions used throughout sqlite. 25 ** 26 ** This file contains functions for allocating memory, comparing 27 ** strings, and stuff like that. 28 ** 29 ** $Id: util.c,v 1.16 2000/10/11 19:28:52 drh Exp $ 30 */ 31 #include "sqliteInt.h" 32 #include <stdarg.h> 33 #include <ctype.h> 34 35 /* 36 ** If MEMORY_DEBUG is defined, then use versions of malloc() and 37 ** free() that track memory usage and check for buffer overruns. 38 */ 39 #ifdef MEMORY_DEBUG 40 41 /* 42 ** Allocate new memory and set it to zero. Return NULL if 43 ** no memory is available. 44 */ 45 void *sqliteMalloc_(int n, char *zFile, int line){ 46 void *p; 47 int *pi; 48 int k; 49 sqlite_nMalloc++; 50 if( sqlite_iMallocFail>=0 ){ 51 sqlite_iMallocFail--; 52 if( sqlite_iMallocFail==0 ) return 0; 53 } 54 k = (n+sizeof(int)-1)/sizeof(int); 55 pi = malloc( (3+k)*sizeof(int)); 56 if( pi==0 ) return 0; 57 pi[0] = 0xdead1122; 58 pi[1] = n; 59 pi[k+2] = 0xdead3344; 60 p = &pi[2]; 61 memset(p, 0, n); 62 #if MEMORY_DEBUG>1 63 fprintf(stderr,"malloc %d bytes at 0x%x from %s:%d\n", n, (int)p, zFile,line); 64 #endif 65 return p; 66 } 67 68 /* 69 ** Free memory previously obtained from sqliteMalloc() 70 */ 71 void sqliteFree_(void *p, char *zFile, int line){ 72 if( p ){ 73 int *pi, k, n; 74 pi = p; 75 pi -= 2; 76 sqlite_nFree++; 77 if( pi[0]!=0xdead1122 ){ 78 fprintf(stderr,"Low-end memory corruption at 0x%x\n", (int)p); 79 return; 80 } 81 n = pi[1]; 82 k = (n+sizeof(int)-1)/sizeof(int); 83 if( pi[k+2]!=0xdead3344 ){ 84 fprintf(stderr,"High-end memory corruption at 0x%x\n", (int)p); 85 return; 86 } 87 memset(pi, 0xff, (k+3)*sizeof(int)); 88 #if MEMORY_DEBUG>1 89 fprintf(stderr,"free %d bytes at 0x%x from %s:%d\n", n, (int)p, zFile,line); 90 #endif 91 free(pi); 92 } 93 } 94 95 /* 96 ** Resize a prior allocation. If p==0, then this routine 97 ** works just like sqliteMalloc(). If n==0, then this routine 98 ** works just like sqliteFree(). 99 */ 100 void *sqliteRealloc_(void *oldP, int n, char *zFile, int line){ 101 int *oldPi, *pi, k, oldN, oldK; 102 void *p; 103 if( oldP==0 ){ 104 return sqliteMalloc_(n,zFile,line); 105 } 106 if( n==0 ){ 107 sqliteFree_(oldP,zFile,line); 108 return 0; 109 } 110 oldPi = oldP; 111 oldPi -= 2; 112 if( oldPi[0]!=0xdead1122 ){ 113 fprintf(stderr,"Low-end memory corruption in realloc at 0x%x\n", (int)p); 114 return 0; 115 } 116 oldN = oldPi[1]; 117 oldK = (oldN+sizeof(int)-1)/sizeof(int); 118 if( oldPi[oldK+2]!=0xdead3344 ){ 119 fprintf(stderr,"High-end memory corruption in realloc at 0x%x\n", (int)p); 120 return 0; 121 } 122 k = (n + sizeof(int) - 1)/sizeof(int); 123 pi = malloc( (k+3)*sizeof(int) ); 124 pi[0] = 0xdead1122; 125 pi[1] = n; 126 pi[k+2] = 0xdead3344; 127 p = &pi[2]; 128 memcpy(p, oldP, n>oldN ? oldN : n); 129 if( n>oldN ){ 130 memset(&((char*)p)[oldN], 0, n-oldN); 131 } 132 memset(oldPi, 0, (oldK+3)*sizeof(int)); 133 free(oldPi); 134 #if MEMORY_DEBUG>1 135 fprintf(stderr,"realloc %d to %d bytes at 0x%x to 0x%x at %s:%d\n", oldN, n, 136 (int)oldP, (int)p, zFile, line); 137 #endif 138 return p; 139 } 140 141 /* 142 ** Make a duplicate of a string into memory obtained from malloc() 143 ** Free the original string using sqliteFree(). 144 */ 145 void sqliteStrRealloc(char **pz){ 146 char *zNew; 147 if( pz==0 || *pz==0 ) return; 148 zNew = malloc( strlen(*pz) + 1 ); 149 if( zNew ) strcpy(zNew, *pz); 150 sqliteFree(*pz); 151 *pz = zNew; 152 } 153 154 /* 155 ** Make a copy of a string in memory obtained from sqliteMalloc() 156 */ 157 char *sqliteStrDup_(const char *z, char *zFile, int line){ 158 char *zNew = sqliteMalloc_(strlen(z)+1, zFile, line); 159 if( zNew ) strcpy(zNew, z); 160 return zNew; 161 } 162 char *sqliteStrNDup_(const char *z, int n, char *zFile, int line){ 163 char *zNew = sqliteMalloc_(n+1, zFile, line); 164 if( zNew ){ 165 memcpy(zNew, z, n); 166 zNew[n] = 0; 167 } 168 return zNew; 169 } 170 #endif /* MEMORY_DEBUG */ 171 172 /* 173 ** The following versions of malloc() and free() are for use in a 174 ** normal build. 175 */ 176 #if !defined(MEMORY_DEBUG) 177 178 /* 179 ** Allocate new memory and set it to zero. Return NULL if 180 ** no memory is available. 181 */ 182 void *sqliteMalloc(int n){ 183 void *p = malloc(n); 184 if( p==0 ) return 0; 185 memset(p, 0, n); 186 return p; 187 } 188 189 /* 190 ** Free memory previously obtained from sqliteMalloc() 191 */ 192 void sqliteFree(void *p){ 193 if( p ){ 194 free(p); 195 } 196 } 197 198 /* 199 ** Resize a prior allocation. If p==0, then this routine 200 ** works just like sqliteMalloc(). If n==0, then this routine 201 ** works just like sqliteFree(). 202 */ 203 void *sqliteRealloc(void *p, int n){ 204 if( p==0 ){ 205 return sqliteMalloc(n); 206 } 207 if( n==0 ){ 208 sqliteFree(p); 209 return 0; 210 } 211 return realloc(p, n); 212 } 213 214 /* 215 ** Make a copy of a string in memory obtained from sqliteMalloc() 216 */ 217 char *sqliteStrDup(const char *z){ 218 char *zNew = sqliteMalloc(strlen(z)+1); 219 if( zNew ) strcpy(zNew, z); 220 return zNew; 221 } 222 char *sqliteStrNDup(const char *z, int n){ 223 char *zNew = sqliteMalloc(n+1); 224 if( zNew ){ 225 memcpy(zNew, z, n); 226 zNew[n] = 0; 227 } 228 return zNew; 229 } 230 #endif /* !defined(MEMORY_DEBUG) */ 231 232 /* 233 ** Create a string from the 2nd and subsequent arguments (up to the 234 ** first NULL argument), store the string in memory obtained from 235 ** sqliteMalloc() and make the pointer indicated by the 1st argument 236 ** point to that string. 237 */ 238 void sqliteSetString(char **pz, const char *zFirst, ...){ 239 va_list ap; 240 int nByte; 241 const char *z; 242 char *zResult; 243 244 if( pz==0 ) return; 245 nByte = strlen(zFirst) + 1; 246 va_start(ap, zFirst); 247 while( (z = va_arg(ap, const char*))!=0 ){ 248 nByte += strlen(z); 249 } 250 va_end(ap); 251 sqliteFree(*pz); 252 *pz = zResult = sqliteMalloc( nByte ); 253 if( zResult==0 ) return; 254 strcpy(zResult, zFirst); 255 zResult += strlen(zResult); 256 va_start(ap, zFirst); 257 while( (z = va_arg(ap, const char*))!=0 ){ 258 strcpy(zResult, z); 259 zResult += strlen(zResult); 260 } 261 va_end(ap); 262 #ifdef MEMORY_DEBUG 263 #if MEMORY_DEBUG>1 264 fprintf(stderr,"string at 0x%x is %s\n", (int)*pz, *pz); 265 #endif 266 #endif 267 } 268 269 /* 270 ** Works like sqliteSetString, but each string is now followed by 271 ** a length integer. -1 means use the whole string. 272 */ 273 void sqliteSetNString(char **pz, ...){ 274 va_list ap; 275 int nByte; 276 const char *z; 277 char *zResult; 278 int n; 279 280 if( pz==0 ) return; 281 nByte = 0; 282 va_start(ap, pz); 283 while( (z = va_arg(ap, const char*))!=0 ){ 284 n = va_arg(ap, int); 285 if( n<=0 ) n = strlen(z); 286 nByte += n; 287 } 288 va_end(ap); 289 sqliteFree(*pz); 290 *pz = zResult = sqliteMalloc( nByte + 1 ); 291 if( zResult==0 ) return; 292 va_start(ap, pz); 293 while( (z = va_arg(ap, const char*))!=0 ){ 294 n = va_arg(ap, int); 295 if( n<=0 ) n = strlen(z); 296 strncpy(zResult, z, n); 297 zResult += n; 298 } 299 *zResult = 0; 300 #ifdef MEMORY_DEBUG 301 #if MEMORY_DEBUG>1 302 fprintf(stderr,"string at 0x%x is %s\n", (int)*pz, *pz); 303 #endif 304 #endif 305 va_end(ap); 306 } 307 308 /* 309 ** Convert an SQL-style quoted string into a normal string by removing 310 ** the quote characters. The conversion is done in-place. If the 311 ** input does not begin with a quote character, then this routine 312 ** is a no-op. 313 */ 314 void sqliteDequote(char *z){ 315 int quote; 316 int i, j; 317 quote = z[0]; 318 if( quote!='\'' && quote!='"' ) return; 319 for(i=1, j=0; z[i]; i++){ 320 if( z[i]==quote ){ 321 if( z[i+1]==quote ){ 322 z[j++] = quote; 323 i++; 324 }else{ 325 z[j++] = 0; 326 break; 327 } 328 }else{ 329 z[j++] = z[i]; 330 } 331 } 332 } 333 334 /* An array to map all upper-case characters into their corresponding 335 ** lower-case character. 336 */ 337 static unsigned char UpperToLower[] = { 338 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 339 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 340 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 341 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 97, 98, 99,100,101,102,103, 342 104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121, 343 122, 91, 92, 93, 94, 95, 96, 97, 98, 99,100,101,102,103,104,105,106,107, 344 108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125, 345 126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, 346 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161, 347 162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179, 348 180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197, 349 198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215, 350 216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233, 351 234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251, 352 252,253,254,255 353 }; 354 355 /* 356 ** This function computes a hash on the name of a keyword. 357 ** Case is not significant. 358 */ 359 int sqliteHashNoCase(const char *z, int n){ 360 int h = 0; 361 int c; 362 if( n<=0 ) n = strlen(z); 363 while( n-- > 0 && (c = *z++)!=0 ){ 364 h = h<<3 ^ h ^ UpperToLower[c]; 365 } 366 if( h<0 ) h = -h; 367 return h; 368 } 369 370 /* 371 ** Some systems have stricmp(). Others have strcasecmp(). Because 372 ** there is no consistency, we will define our own. 373 */ 374 int sqliteStrICmp(const char *zLeft, const char *zRight){ 375 register unsigned char *a, *b; 376 a = (unsigned char *)zLeft; 377 b = (unsigned char *)zRight; 378 while( *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; } 379 return *a - *b; 380 } 381 int sqliteStrNICmp(const char *zLeft, const char *zRight, int N){ 382 register unsigned char *a, *b; 383 a = (unsigned char *)zLeft; 384 b = (unsigned char *)zRight; 385 while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; } 386 return N<0 ? 0 : *a - *b; 387 } 388 389 /* Notes on string comparisions. 390 ** 391 ** We want the main string comparision function used for sorting to 392 ** sort both numbers and alphanumeric words into the correct sequence. 393 ** The same routine should do both without prior knowledge of which 394 ** type of text the input represents. It should even work for strings 395 ** which are a mixture of text and numbers. 396 ** 397 ** To accomplish this, we keep track of a state number while scanning 398 ** the two strings. The states are as follows: 399 ** 400 ** 1 Beginning of word 401 ** 2 Arbitrary text 402 ** 3 Integer 403 ** 4 Negative integer 404 ** 5 Real number 405 ** 6 Negative real 406 ** 407 ** The scan begins in state 1, beginning of word. Transitions to other 408 ** states are determined by characters seen, as shown in the following 409 ** chart: 410 ** 411 ** Current State Character Seen New State 412 ** -------------------- -------------- ------------------- 413 ** 0 Beginning of word "-" 3 Negative integer 414 ** digit 2 Integer 415 ** space 0 Beginning of word 416 ** otherwise 1 Arbitrary text 417 ** 418 ** 1 Arbitrary text space 0 Beginning of word 419 ** digit 2 Integer 420 ** otherwise 1 Arbitrary text 421 ** 422 ** 2 Integer space 0 Beginning of word 423 ** "." 4 Real number 424 ** digit 2 Integer 425 ** otherwise 1 Arbitrary text 426 ** 427 ** 3 Negative integer space 0 Beginning of word 428 ** "." 5 Negative Real num 429 ** digit 3 Negative integer 430 ** otherwise 1 Arbitrary text 431 ** 432 ** 4 Real number space 0 Beginning of word 433 ** digit 4 Real number 434 ** otherwise 1 Arbitrary text 435 ** 436 ** 5 Negative real num space 0 Beginning of word 437 ** digit 5 Negative real num 438 ** otherwise 1 Arbitrary text 439 ** 440 ** To implement this state machine, we first classify each character 441 ** into on of the following categories: 442 ** 443 ** 0 Text 444 ** 1 Space 445 ** 2 Digit 446 ** 3 "-" 447 ** 4 "." 448 ** 449 ** Given an arbitrary character, the array charClass[] maps that character 450 ** into one of the atove categories. 451 */ 452 static const unsigned char charClass[] = { 453 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */ 454 /* 0x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 455 /* 1x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 456 /* 2x */ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 0, 457 /* 3x */ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 458 /* 4x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 459 /* 5x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 460 /* 6x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 461 /* 7x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 462 /* 8x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 463 /* 9x */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 464 /* Ax */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 465 /* Bx */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 466 /* Cx */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 467 /* Dx */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 468 /* Ex */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 469 /* Fx */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 470 }; 471 #define N_CHAR_CLASS 5 472 473 /* 474 ** Given the current state number (0 thru 5), this array figures 475 ** the new state number given the character class. 476 */ 477 static const unsigned char stateMachine[] = { 478 /* Text, Space, Digit, "-", "." */ 479 1, 0, 2, 3, 1, /* State 0: Beginning of word */ 480 1, 0, 2, 1, 1, /* State 1: Arbitrary text */ 481 1, 0, 2, 1, 4, /* State 2: Integer */ 482 1, 0, 3, 1, 5, /* State 3: Negative integer */ 483 1, 0, 4, 1, 1, /* State 4: Real number */ 484 1, 0, 5, 1, 1, /* State 5: Negative real num */ 485 }; 486 487 /* This routine does a comparison of two strings. Case is used only 488 ** if useCase!=0. Numbers compare in numerical order. 489 */ 490 static int privateStrCmp(const char *atext, const char *btext, int useCase){ 491 register unsigned char *a, *b, *map, ca, cb; 492 int result; 493 register int cclass = 0; 494 495 a = (unsigned char *)atext; 496 b = (unsigned char *)btext; 497 if( useCase ){ 498 do{ 499 if( (ca= *a++)!=(cb= *b++) ) break; 500 cclass = stateMachine[cclass*N_CHAR_CLASS + charClass[ca]]; 501 }while( ca!=0 ); 502 }else{ 503 map = UpperToLower; 504 do{ 505 if( (ca=map[*a++])!=(cb=map[*b++]) ) break; 506 cclass = stateMachine[cclass*N_CHAR_CLASS + charClass[ca]]; 507 }while( ca!=0 ); 508 } 509 switch( cclass ){ 510 case 0: 511 case 1: { 512 if( isdigit(ca) && isdigit(cb) ){ 513 cclass = 2; 514 } 515 break; 516 } 517 default: { 518 break; 519 } 520 } 521 switch( cclass ){ 522 case 2: 523 case 3: { 524 if( isdigit(ca) ){ 525 if( isdigit(cb) ){ 526 int acnt, bcnt; 527 acnt = bcnt = 0; 528 while( isdigit(*a++) ) acnt++; 529 while( isdigit(*b++) ) bcnt++; 530 result = acnt - bcnt; 531 if( result==0 ) result = ca-cb; 532 }else{ 533 result = 1; 534 } 535 }else if( isdigit(cb) ){ 536 result = -1; 537 }else if( ca=='.' ){ 538 result = 1; 539 }else if( cb=='.' ){ 540 result = -1; 541 }else{ 542 result = ca - cb; 543 cclass = 2; 544 } 545 if( cclass==3 ) result = -result; 546 break; 547 } 548 case 0: 549 case 1: 550 case 4: { 551 result = ca - cb; 552 break; 553 } 554 case 5: { 555 result = cb - ca; 556 }; 557 } 558 return result; 559 } 560 561 /* 562 ** Do a comparison of pure numerics. If either string is not a pure 563 ** numeric, then return 0. Otherwise return 1 and set *pResult to be 564 ** negative, zero or positive if the first string are numerially less than 565 ** equal to, or greater than the second. 566 */ 567 static int privateCompareNum(const char *a, const char *b, int *pResult){ 568 char *endPtr; 569 double rA, rB; 570 int isNumA, isNumB; 571 if( isdigit(*a) || ((*a=='-' || *a=='+') && isdigit(a[1])) ){ 572 rA = strtod(a, &endPtr); 573 isNumA = *endPtr==0; 574 }else{ 575 isNumA = 0; 576 } 577 if( isdigit(*b) || ((*b=='-' || *b=='+') && isdigit(b[1])) ){ 578 rB = strtod(b, &endPtr); 579 isNumB = *endPtr==0; 580 }else{ 581 isNumB = 0; 582 } 583 if( isNumB==0 && isNumA==0 ) return 0; 584 if( isNumA!=isNumB ){ 585 *pResult = isNumA - isNumB; 586 }else if( rA<rB ){ 587 *pResult = -1; 588 }else if( rA>rB ){ 589 *pResult = 1; 590 }else{ 591 *pResult = 0; 592 } 593 return 1; 594 } 595 596 /* This comparison routine is what we use for comparison operations 597 ** in an SQL expression. (Ex: name<'Hello' or value<5). Compare two 598 ** strings. Use case only as a tie-breaker. Numbers compare in 599 ** numerical order. 600 */ 601 int sqliteCompare(const char *atext, const char *btext){ 602 int result; 603 if( !privateCompareNum(atext, btext, &result) || result==0 ){ 604 result = privateStrCmp(atext, btext, 0); 605 if( result==0 ) result = privateStrCmp(atext, btext, 1); 606 } 607 return result; 608 } 609 610 /* 611 ** If you compile just this one file with the -DTEST_COMPARE=1 option, 612 ** it generates a program to test the comparisons routines. 613 */ 614 #ifdef TEST_COMPARE 615 #include <stdlib.h> 616 #include <stdio.h> 617 int sortCmp(const char **a, const char **b){ 618 return sqliteCompare(*a, *b); 619 } 620 int main(int argc, char **argv){ 621 int i, j, k, n, cnt; 622 static char *azStr[] = { 623 "abc", "aBc", "abcd", "aBcd", 624 "123", "124", "1234", "-123", "-124", "-1234", "+124", 625 "123.45", "123.456", "123.46", "-123.45", "-123.46", "-123.456", 626 "x9", "x10", "x-9", "x-10", "X9", "X10", 627 "1.234e+02", "+123", "1.23E2", "1.2345e+2", "-1.2345e2", "+w" 628 }; 629 n = sizeof(azStr)/sizeof(azStr[0]); 630 qsort(azStr, n, sizeof(azStr[0]), sortCmp); 631 for(i=0; i<n; i++){ 632 printf("%s\n", azStr[i]); 633 } 634 printf("Sanity1..."); 635 fflush(stdout); 636 cnt = 0; 637 for(i=0; i<n-1; i++){ 638 char *a = azStr[i]; 639 for(j=i+1; j<n; j++){ 640 char *b = azStr[j]; 641 if( sqliteCompare(a,b) != -sqliteCompare(b,a) ){ 642 printf("Failed! \"%s\" vs \"%s\"\n", a, b); 643 i = j = n; 644 } 645 cnt++; 646 } 647 } 648 if( i<n ){ 649 printf(" OK (%d)\n", cnt); 650 } 651 printf("Sanity2..."); 652 fflush(stdout); 653 cnt = 0; 654 for(i=0; i<n; i++){ 655 char *a = azStr[i]; 656 for(j=0; j<n; j++){ 657 char *b = azStr[j]; 658 for(k=0; k<n; k++){ 659 char *c = azStr[k]; 660 int x1, x2, x3, success; 661 x1 = sqliteCompare(a,b); 662 x2 = sqliteCompare(b,c); 663 x3 = sqliteCompare(a,c); 664 if( x1==0 ){ 665 success = x2==x3; 666 }else if( x1<0 ){ 667 success = (x2<=0 && x3<=0) || x2>0; 668 }else{ 669 success = (x2>=0 && x3>=0) || x2<0; 670 } 671 if( !success ){ 672 printf("Failed! \"%s\" vs \"%s\" vs \"%s\"\n", a, b, c); 673 i = j = k = n+1; 674 } 675 cnt++; 676 } 677 } 678 } 679 if( i<n+1 ){ 680 printf(" OK (%d)\n", cnt); 681 } 682 return 0; 683 } 684 #endif 685 686 /* 687 ** This routine is used for sorting. Each key is a list of one or more 688 ** null-terminated strings. The list is terminated by two nulls in 689 ** a row. For example, the following text is key with three strings: 690 ** 691 ** +one\000-two\000+three\000\000 692 ** 693 ** Both arguments will have the same number of strings. This routine 694 ** returns negative, zero, or positive if the first argument is less 695 ** than, equal to, or greater than the first. (Result is a-b). 696 ** 697 ** Every string begins with either a "+" or "-" character. If the 698 ** character is "-" then the return value is negated. This is done 699 ** to implement a sort in descending order. 700 */ 701 int sqliteSortCompare(const char *a, const char *b){ 702 int len; 703 int res = 0; 704 705 while( res==0 && *a && *b ){ 706 res = sqliteCompare(&a[1], &b[1]); 707 if( res==0 ){ 708 len = strlen(a) + 1; 709 a += len; 710 b += len; 711 } 712 } 713 if( *a=='-' ) res = -res; 714 return res; 715 } 716 717 /* 718 ** Compare two strings for equality where the first string can 719 ** potentially be a "glob" expression. Return true (1) if they 720 ** are the same and false (0) if they are different. 721 ** 722 ** Globbing rules: 723 ** 724 ** '*' Matches any sequence of zero or more characters. 725 ** 726 ** '?' Matches exactly one character. 727 ** 728 ** [...] Matches one character from the enclosed list of 729 ** characters. 730 ** 731 ** [^...] Matches one character not in the enclosed list. 732 ** 733 ** With the [...] and [^...] matching, a ']' character can be included 734 ** in the list by making it the first character after '[' or '^'. A 735 ** range of characters can be specified using '-'. Example: 736 ** "[a-z]" matches any single lower-case letter. To match a '-', make 737 ** it the last character in the list. 738 ** 739 ** This routine is usually quick, but can be N**2 in the worst case. 740 ** 741 ** Hints: to match '*' or '?', put them in "[]". Like this: 742 ** 743 ** abc[*]xyz Matches "abc*xyz" only 744 */ 745 int sqliteGlobCompare(const char *zPattern, const char *zString){ 746 register char c; 747 int invert; 748 int seen; 749 char c2; 750 751 while( (c = *zPattern)!=0 ){ 752 switch( c ){ 753 case '*': 754 while( zPattern[1]=='*' ) zPattern++; 755 if( zPattern[1]==0 ) return 1; 756 c = zPattern[1]; 757 if( c=='[' || c=='?' ){ 758 while( *zString && sqliteGlobCompare(&zPattern[1],zString)==0 ){ 759 zString++; 760 } 761 return *zString!=0; 762 }else{ 763 while( (c2 = *zString)!=0 ){ 764 while( c2 != 0 && c2 != c ){ c2 = *++zString; } 765 if( c2==0 ) return 0; 766 if( sqliteGlobCompare(&zPattern[1],zString) ) return 1; 767 zString++; 768 } 769 return 0; 770 } 771 case '?': 772 if( *zString==0 ) return 0; 773 break; 774 case '[': 775 seen = 0; 776 invert = 0; 777 c = *zString; 778 if( c==0 ) return 0; 779 c2 = *++zPattern; 780 if( c2=='^' ){ invert = 1; c2 = *++zPattern; } 781 if( c2==']' ){ 782 if( c==']' ) seen = 1; 783 c2 = *++zPattern; 784 } 785 while( (c2 = *zPattern)!=0 && c2!=']' ){ 786 if( c2=='-' && zPattern[1]!=']' && zPattern[1]!=0 ){ 787 if( c>zPattern[-1] && c<zPattern[1] ) seen = 1; 788 }else if( c==c2 ){ 789 seen = 1; 790 } 791 zPattern++; 792 } 793 if( c2==0 || (seen ^ invert)==0 ) return 0; 794 break; 795 default: 796 if( c != *zString ) return 0; 797 break; 798 } 799 zPattern++; 800 zString++; 801 } 802 return *zString==0; 803 } 804 805 /* 806 ** Compare two strings for equality using the "LIKE" operator of 807 ** SQL. The '%' character matches any sequence of 0 or more 808 ** characters and '_' matches any single character. Case is 809 ** not significant. 810 ** 811 ** This routine is just an adaptation of the sqliteGlobCompare() 812 ** routine above. 813 */ 814 int 815 sqliteLikeCompare(const unsigned char *zPattern, const unsigned char *zString){ 816 register char c; 817 char c2; 818 819 while( (c = UpperToLower[*zPattern])!=0 ){ 820 switch( c ){ 821 case '%': 822 while( zPattern[1]=='%' ) zPattern++; 823 if( zPattern[1]==0 ) return 1; 824 c = UpperToLower[0xff & zPattern[1]]; 825 if( c=='_' ){ 826 while( *zString && sqliteLikeCompare(&zPattern[1],zString)==0 ){ 827 zString++; 828 } 829 return *zString!=0; 830 }else{ 831 while( (c2 = UpperToLower[*zString])!=0 ){ 832 while( c2 != 0 && c2 != c ){ c2 = UpperToLower[*++zString]; } 833 if( c2==0 ) return 0; 834 if( sqliteLikeCompare(&zPattern[1],zString) ) return 1; 835 zString++; 836 } 837 return 0; 838 } 839 case '_': 840 if( *zString==0 ) return 0; 841 break; 842 default: 843 if( c != UpperToLower[*zString] ) return 0; 844 break; 845 } 846 zPattern++; 847 zString++; 848 } 849 return *zString==0; 850 } 851