xref: /illumos-gate/usr/src/lib/libsqlite/src/util.c (revision c5c4113d)
1 
2 #pragma ident	"%Z%%M%	%I%	%E% SMI"
3 
4 /*
5 ** 2001 September 15
6 **
7 ** The author disclaims copyright to this source code.  In place of
8 ** a legal notice, here is a blessing:
9 **
10 **    May you do good and not evil.
11 **    May you find forgiveness for yourself and forgive others.
12 **    May you share freely, never taking more than you give.
13 **
14 *************************************************************************
15 ** Utility functions used throughout sqlite.
16 **
17 ** This file contains functions for allocating memory, comparing
18 ** strings, and stuff like that.
19 **
20 ** $Id: util.c,v 1.74.2.1 2004/07/15 13:08:41 drh Exp $
21 */
22 #include "sqliteInt.h"
23 #include <stdarg.h>
24 #include <ctype.h>
25 
26 /*
27 ** If malloc() ever fails, this global variable gets set to 1.
28 ** This causes the library to abort and never again function.
29 */
30 int sqlite_malloc_failed = 0;
31 
32 /*
33 ** If MEMORY_DEBUG is defined, then use versions of malloc() and
34 ** free() that track memory usage and check for buffer overruns.
35 */
36 #ifdef MEMORY_DEBUG
37 
38 /*
39 ** For keeping track of the number of mallocs and frees.   This
40 ** is used to check for memory leaks.
41 */
42 int sqlite_nMalloc;         /* Number of sqliteMalloc() calls */
43 int sqlite_nFree;           /* Number of sqliteFree() calls */
44 int sqlite_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
45 #if MEMORY_DEBUG>1
46 static int memcnt = 0;
47 #endif
48 
49 /*
50 ** Number of 32-bit guard words
51 */
52 #define N_GUARD 1
53 
54 /*
55 ** Allocate new memory and set it to zero.  Return NULL if
56 ** no memory is available.
57 */
sqliteMalloc_(int n,int bZero,char * zFile,int line)58 void *sqliteMalloc_(int n, int bZero, char *zFile, int line){
59   void *p;
60   int *pi;
61   int i, k;
62   if( sqlite_iMallocFail>=0 ){
63     sqlite_iMallocFail--;
64     if( sqlite_iMallocFail==0 ){
65       sqlite_malloc_failed++;
66 #if MEMORY_DEBUG>1
67       fprintf(stderr,"**** failed to allocate %d bytes at %s:%d\n",
68               n, zFile,line);
69 #endif
70       sqlite_iMallocFail--;
71       return 0;
72     }
73   }
74   if( n==0 ) return 0;
75   k = (n+sizeof(int)-1)/sizeof(int);
76   pi = malloc( (N_GUARD*2+1+k)*sizeof(int));
77   if( pi==0 ){
78     sqlite_malloc_failed++;
79     return 0;
80   }
81   sqlite_nMalloc++;
82   for(i=0; i<N_GUARD; i++) pi[i] = 0xdead1122;
83   pi[N_GUARD] = n;
84   for(i=0; i<N_GUARD; i++) pi[k+1+N_GUARD+i] = 0xdead3344;
85   p = &pi[N_GUARD+1];
86   memset(p, bZero==0, n);
87 #if MEMORY_DEBUG>1
88   fprintf(stderr,"%06d malloc %d bytes at 0x%x from %s:%d\n",
89       ++memcnt, n, (int)p, zFile,line);
90 #endif
91   return p;
92 }
93 
94 /*
95 ** Check to see if the given pointer was obtained from sqliteMalloc()
96 ** and is able to hold at least N bytes.  Raise an exception if this
97 ** is not the case.
98 **
99 ** This routine is used for testing purposes only.
100 */
sqliteCheckMemory(void * p,int N)101 void sqliteCheckMemory(void *p, int N){
102   int *pi = p;
103   int n, i, k;
104   pi -= N_GUARD+1;
105   for(i=0; i<N_GUARD; i++){
106     assert( pi[i]==0xdead1122 );
107   }
108   n = pi[N_GUARD];
109   assert( N>=0 && N<n );
110   k = (n+sizeof(int)-1)/sizeof(int);
111   for(i=0; i<N_GUARD; i++){
112     assert( pi[k+N_GUARD+1+i]==0xdead3344 );
113   }
114 }
115 
116 /*
117 ** Free memory previously obtained from sqliteMalloc()
118 */
sqliteFree_(void * p,char * zFile,int line)119 void sqliteFree_(void *p, char *zFile, int line){
120   if( p ){
121     int *pi, i, k, n;
122     pi = p;
123     pi -= N_GUARD+1;
124     sqlite_nFree++;
125     for(i=0; i<N_GUARD; i++){
126       if( pi[i]!=0xdead1122 ){
127         fprintf(stderr,"Low-end memory corruption at 0x%x\n", (int)p);
128         return;
129       }
130     }
131     n = pi[N_GUARD];
132     k = (n+sizeof(int)-1)/sizeof(int);
133     for(i=0; i<N_GUARD; i++){
134       if( pi[k+N_GUARD+1+i]!=0xdead3344 ){
135         fprintf(stderr,"High-end memory corruption at 0x%x\n", (int)p);
136         return;
137       }
138     }
139     memset(pi, 0xff, (k+N_GUARD*2+1)*sizeof(int));
140 #if MEMORY_DEBUG>1
141     fprintf(stderr,"%06d free %d bytes at 0x%x from %s:%d\n",
142          ++memcnt, n, (int)p, zFile,line);
143 #endif
144     free(pi);
145   }
146 }
147 
148 /*
149 ** Resize a prior allocation.  If p==0, then this routine
150 ** works just like sqliteMalloc().  If n==0, then this routine
151 ** works just like sqliteFree().
152 */
sqliteRealloc_(void * oldP,int n,char * zFile,int line)153 void *sqliteRealloc_(void *oldP, int n, char *zFile, int line){
154   int *oldPi, *pi, i, k, oldN, oldK;
155   void *p;
156   if( oldP==0 ){
157     return sqliteMalloc_(n,1,zFile,line);
158   }
159   if( n==0 ){
160     sqliteFree_(oldP,zFile,line);
161     return 0;
162   }
163   oldPi = oldP;
164   oldPi -= N_GUARD+1;
165   if( oldPi[0]!=0xdead1122 ){
166     fprintf(stderr,"Low-end memory corruption in realloc at 0x%x\n", (int)oldP);
167     return 0;
168   }
169   oldN = oldPi[N_GUARD];
170   oldK = (oldN+sizeof(int)-1)/sizeof(int);
171   for(i=0; i<N_GUARD; i++){
172     if( oldPi[oldK+N_GUARD+1+i]!=0xdead3344 ){
173       fprintf(stderr,"High-end memory corruption in realloc at 0x%x\n",
174               (int)oldP);
175       return 0;
176     }
177   }
178   k = (n + sizeof(int) - 1)/sizeof(int);
179   pi = malloc( (k+N_GUARD*2+1)*sizeof(int) );
180   if( pi==0 ){
181     sqlite_malloc_failed++;
182     return 0;
183   }
184   for(i=0; i<N_GUARD; i++) pi[i] = 0xdead1122;
185   pi[N_GUARD] = n;
186   for(i=0; i<N_GUARD; i++) pi[k+N_GUARD+1+i] = 0xdead3344;
187   p = &pi[N_GUARD+1];
188   memcpy(p, oldP, n>oldN ? oldN : n);
189   if( n>oldN ){
190     memset(&((char*)p)[oldN], 0, n-oldN);
191   }
192   memset(oldPi, 0xab, (oldK+N_GUARD+2)*sizeof(int));
193   free(oldPi);
194 #if MEMORY_DEBUG>1
195   fprintf(stderr,"%06d realloc %d to %d bytes at 0x%x to 0x%x at %s:%d\n",
196     ++memcnt, oldN, n, (int)oldP, (int)p, zFile, line);
197 #endif
198   return p;
199 }
200 
201 /*
202 ** Make a duplicate of a string into memory obtained from malloc()
203 ** Free the original string using sqliteFree().
204 **
205 ** This routine is called on all strings that are passed outside of
206 ** the SQLite library.  That way clients can free the string using free()
207 ** rather than having to call sqliteFree().
208 */
sqliteStrRealloc(char ** pz)209 void sqliteStrRealloc(char **pz){
210   char *zNew;
211   if( pz==0 || *pz==0 ) return;
212   zNew = malloc( strlen(*pz) + 1 );
213   if( zNew==0 ){
214     sqlite_malloc_failed++;
215     sqliteFree(*pz);
216     *pz = 0;
217   }
218   strcpy(zNew, *pz);
219   sqliteFree(*pz);
220   *pz = zNew;
221 }
222 
223 /*
224 ** Make a copy of a string in memory obtained from sqliteMalloc()
225 */
sqliteStrDup_(const char * z,char * zFile,int line)226 char *sqliteStrDup_(const char *z, char *zFile, int line){
227   char *zNew;
228   if( z==0 ) return 0;
229   zNew = sqliteMalloc_(strlen(z)+1, 0, zFile, line);
230   if( zNew ) strcpy(zNew, z);
231   return zNew;
232 }
sqliteStrNDup_(const char * z,int n,char * zFile,int line)233 char *sqliteStrNDup_(const char *z, int n, char *zFile, int line){
234   char *zNew;
235   if( z==0 ) return 0;
236   zNew = sqliteMalloc_(n+1, 0, zFile, line);
237   if( zNew ){
238     memcpy(zNew, z, n);
239     zNew[n] = 0;
240   }
241   return zNew;
242 }
243 #endif /* MEMORY_DEBUG */
244 
245 /*
246 ** The following versions of malloc() and free() are for use in a
247 ** normal build.
248 */
249 #if !defined(MEMORY_DEBUG)
250 
251 /*
252 ** Allocate new memory and set it to zero.  Return NULL if
253 ** no memory is available.  See also sqliteMallocRaw().
254 */
sqliteMalloc(int n)255 void *sqliteMalloc(int n){
256   void *p;
257   if( (p = malloc(n))==0 ){
258     if( n>0 ) sqlite_malloc_failed++;
259   }else{
260     memset(p, 0, n);
261   }
262   return p;
263 }
264 
265 /*
266 ** Allocate new memory but do not set it to zero.  Return NULL if
267 ** no memory is available.  See also sqliteMalloc().
268 */
sqliteMallocRaw(int n)269 void *sqliteMallocRaw(int n){
270   void *p;
271   if( (p = malloc(n))==0 ){
272     if( n>0 ) sqlite_malloc_failed++;
273   }
274   return p;
275 }
276 
277 /*
278 ** Free memory previously obtained from sqliteMalloc()
279 */
sqliteFree(void * p)280 void sqliteFree(void *p){
281   if( p ){
282     free(p);
283   }
284 }
285 
286 /*
287 ** Resize a prior allocation.  If p==0, then this routine
288 ** works just like sqliteMalloc().  If n==0, then this routine
289 ** works just like sqliteFree().
290 */
sqliteRealloc(void * p,int n)291 void *sqliteRealloc(void *p, int n){
292   void *p2;
293   if( p==0 ){
294     return sqliteMalloc(n);
295   }
296   if( n==0 ){
297     sqliteFree(p);
298     return 0;
299   }
300   p2 = realloc(p, n);
301   if( p2==0 ){
302     sqlite_malloc_failed++;
303   }
304   return p2;
305 }
306 
307 /*
308 ** Make a copy of a string in memory obtained from sqliteMalloc()
309 */
sqliteStrDup(const char * z)310 char *sqliteStrDup(const char *z){
311   char *zNew;
312   if( z==0 ) return 0;
313   zNew = sqliteMallocRaw(strlen(z)+1);
314   if( zNew ) strcpy(zNew, z);
315   return zNew;
316 }
sqliteStrNDup(const char * z,int n)317 char *sqliteStrNDup(const char *z, int n){
318   char *zNew;
319   if( z==0 ) return 0;
320   zNew = sqliteMallocRaw(n+1);
321   if( zNew ){
322     memcpy(zNew, z, n);
323     zNew[n] = 0;
324   }
325   return zNew;
326 }
327 #endif /* !defined(MEMORY_DEBUG) */
328 
329 /*
330 ** Create a string from the 2nd and subsequent arguments (up to the
331 ** first NULL argument), store the string in memory obtained from
332 ** sqliteMalloc() and make the pointer indicated by the 1st argument
333 ** point to that string.  The 1st argument must either be NULL or
334 ** point to memory obtained from sqliteMalloc().
335 */
sqliteSetString(char ** pz,const char * zFirst,...)336 void sqliteSetString(char **pz, const char *zFirst, ...){
337   va_list ap;
338   int nByte;
339   const char *z;
340   char *zResult;
341 
342   if( pz==0 ) return;
343   nByte = strlen(zFirst) + 1;
344   va_start(ap, zFirst);
345   while( (z = va_arg(ap, const char*))!=0 ){
346     nByte += strlen(z);
347   }
348   va_end(ap);
349   sqliteFree(*pz);
350   *pz = zResult = sqliteMallocRaw( nByte );
351   if( zResult==0 ){
352     return;
353   }
354   strcpy(zResult, zFirst);
355   zResult += strlen(zResult);
356   va_start(ap, zFirst);
357   while( (z = va_arg(ap, const char*))!=0 ){
358     strcpy(zResult, z);
359     zResult += strlen(zResult);
360   }
361   va_end(ap);
362 #ifdef MEMORY_DEBUG
363 #if MEMORY_DEBUG>1
364   fprintf(stderr,"string at 0x%x is %s\n", (int)*pz, *pz);
365 #endif
366 #endif
367 }
368 
369 /*
370 ** Works like sqliteSetString, but each string is now followed by
371 ** a length integer which specifies how much of the source string
372 ** to copy (in bytes).  -1 means use the whole string.  The 1st
373 ** argument must either be NULL or point to memory obtained from
374 ** sqliteMalloc().
375 */
sqliteSetNString(char ** pz,...)376 void sqliteSetNString(char **pz, ...){
377   va_list ap;
378   int nByte;
379   const char *z;
380   char *zResult;
381   int n;
382 
383   if( pz==0 ) return;
384   nByte = 0;
385   va_start(ap, pz);
386   while( (z = va_arg(ap, const char*))!=0 ){
387     n = va_arg(ap, int);
388     if( n<=0 ) n = strlen(z);
389     nByte += n;
390   }
391   va_end(ap);
392   sqliteFree(*pz);
393   *pz = zResult = sqliteMallocRaw( nByte + 1 );
394   if( zResult==0 ) return;
395   va_start(ap, pz);
396   while( (z = va_arg(ap, const char*))!=0 ){
397     n = va_arg(ap, int);
398     if( n<=0 ) n = strlen(z);
399     strncpy(zResult, z, n);
400     zResult += n;
401   }
402   *zResult = 0;
403 #ifdef MEMORY_DEBUG
404 #if MEMORY_DEBUG>1
405   fprintf(stderr,"string at 0x%x is %s\n", (int)*pz, *pz);
406 #endif
407 #endif
408   va_end(ap);
409 }
410 
411 /*
412 ** Add an error message to pParse->zErrMsg and increment pParse->nErr.
413 ** The following formatting characters are allowed:
414 **
415 **      %s      Insert a string
416 **      %z      A string that should be freed after use
417 **      %d      Insert an integer
418 **      %T      Insert a token
419 **      %S      Insert the first element of a SrcList
420 */
sqliteErrorMsg(Parse * pParse,const char * zFormat,...)421 void sqliteErrorMsg(Parse *pParse, const char *zFormat, ...){
422   va_list ap;
423   pParse->nErr++;
424   sqliteFree(pParse->zErrMsg);
425   va_start(ap, zFormat);
426   pParse->zErrMsg = sqliteVMPrintf(zFormat, ap);
427   va_end(ap);
428 }
429 
430 /*
431 ** Convert an SQL-style quoted string into a normal string by removing
432 ** the quote characters.  The conversion is done in-place.  If the
433 ** input does not begin with a quote character, then this routine
434 ** is a no-op.
435 **
436 ** 2002-Feb-14: This routine is extended to remove MS-Access style
437 ** brackets from around identifers.  For example:  "[a-b-c]" becomes
438 ** "a-b-c".
439 */
sqliteDequote(char * z)440 void sqliteDequote(char *z){
441   int quote;
442   int i, j;
443   if( z==0 ) return;
444   quote = z[0];
445   switch( quote ){
446     case '\'':  break;
447     case '"':   break;
448     case '[':   quote = ']';  break;
449     default:    return;
450   }
451   for(i=1, j=0; z[i]; i++){
452     if( z[i]==quote ){
453       if( z[i+1]==quote ){
454         z[j++] = quote;
455         i++;
456       }else{
457         z[j++] = 0;
458         break;
459       }
460     }else{
461       z[j++] = z[i];
462     }
463   }
464 }
465 
466 /* An array to map all upper-case characters into their corresponding
467 ** lower-case character.
468 */
469 static unsigned char UpperToLower[] = {
470       0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17,
471      18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
472      36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
473      54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 97, 98, 99,100,101,102,103,
474     104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,
475     122, 91, 92, 93, 94, 95, 96, 97, 98, 99,100,101,102,103,104,105,106,107,
476     108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,
477     126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
478     144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,
479     162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,
480     180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,
481     198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,
482     216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,
483     234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,
484     252,253,254,255
485 };
486 
487 /*
488 ** This function computes a hash on the name of a keyword.
489 ** Case is not significant.
490 */
sqliteHashNoCase(const char * z,int n)491 int sqliteHashNoCase(const char *z, int n){
492   int h = 0;
493   if( n<=0 ) n = strlen(z);
494   while( n > 0  ){
495     h = (h<<3) ^ h ^ UpperToLower[(unsigned char)*z++];
496     n--;
497   }
498   return h & 0x7fffffff;
499 }
500 
501 /*
502 ** Some systems have stricmp().  Others have strcasecmp().  Because
503 ** there is no consistency, we will define our own.
504 */
sqliteStrICmp(const char * zLeft,const char * zRight)505 int sqliteStrICmp(const char *zLeft, const char *zRight){
506   register unsigned char *a, *b;
507   a = (unsigned char *)zLeft;
508   b = (unsigned char *)zRight;
509   while( *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
510   return UpperToLower[*a] - UpperToLower[*b];
511 }
sqliteStrNICmp(const char * zLeft,const char * zRight,int N)512 int sqliteStrNICmp(const char *zLeft, const char *zRight, int N){
513   register unsigned char *a, *b;
514   a = (unsigned char *)zLeft;
515   b = (unsigned char *)zRight;
516   while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
517   return N<0 ? 0 : UpperToLower[*a] - UpperToLower[*b];
518 }
519 
520 /*
521 ** Return TRUE if z is a pure numeric string.  Return FALSE if the
522 ** string contains any character which is not part of a number.
523 **
524 ** Am empty string is considered non-numeric.
525 */
sqliteIsNumber(const char * z)526 int sqliteIsNumber(const char *z){
527   if( *z=='-' || *z=='+' ) z++;
528   if( !isdigit(*z) ){
529     return 0;
530   }
531   z++;
532   while( isdigit(*z) ){ z++; }
533   if( *z=='.' ){
534     z++;
535     if( !isdigit(*z) ) return 0;
536     while( isdigit(*z) ){ z++; }
537   }
538   if( *z=='e' || *z=='E' ){
539     z++;
540     if( *z=='+' || *z=='-' ) z++;
541     if( !isdigit(*z) ) return 0;
542     while( isdigit(*z) ){ z++; }
543   }
544   return *z==0;
545 }
546 
547 /*
548 ** The string z[] is an ascii representation of a real number.
549 ** Convert this string to a double.
550 **
551 ** This routine assumes that z[] really is a valid number.  If it
552 ** is not, the result is undefined.
553 **
554 ** This routine is used instead of the library atof() function because
555 ** the library atof() might want to use "," as the decimal point instead
556 ** of "." depending on how locale is set.  But that would cause problems
557 ** for SQL.  So this routine always uses "." regardless of locale.
558 */
sqliteAtoF(const char * z,const char ** pzEnd)559 double sqliteAtoF(const char *z, const char **pzEnd){
560   int sign = 1;
561   LONGDOUBLE_TYPE v1 = 0.0;
562   if( *z=='-' ){
563     sign = -1;
564     z++;
565   }else if( *z=='+' ){
566     z++;
567   }
568   while( isdigit(*z) ){
569     v1 = v1*10.0 + (*z - '0');
570     z++;
571   }
572   if( *z=='.' ){
573     LONGDOUBLE_TYPE divisor = 1.0;
574     z++;
575     while( isdigit(*z) ){
576       v1 = v1*10.0 + (*z - '0');
577       divisor *= 10.0;
578       z++;
579     }
580     v1 /= divisor;
581   }
582   if( *z=='e' || *z=='E' ){
583     int esign = 1;
584     int eval = 0;
585     LONGDOUBLE_TYPE scale = 1.0;
586     z++;
587     if( *z=='-' ){
588       esign = -1;
589       z++;
590     }else if( *z=='+' ){
591       z++;
592     }
593     while( isdigit(*z) ){
594       eval = eval*10 + *z - '0';
595       z++;
596     }
597     while( eval>=64 ){ scale *= 1.0e+64; eval -= 64; }
598     while( eval>=16 ){ scale *= 1.0e+16; eval -= 16; }
599     while( eval>=4 ){ scale *= 1.0e+4; eval -= 4; }
600     while( eval>=1 ){ scale *= 1.0e+1; eval -= 1; }
601     if( esign<0 ){
602       v1 /= scale;
603     }else{
604       v1 *= scale;
605     }
606   }
607   if( pzEnd ) *pzEnd = z;
608   return sign<0 ? -v1 : v1;
609 }
610 
611 /*
612 ** The string zNum represents an integer.  There might be some other
613 ** information following the integer too, but that part is ignored.
614 ** If the integer that the prefix of zNum represents will fit in a
615 ** 32-bit signed integer, return TRUE.  Otherwise return FALSE.
616 **
617 ** This routine returns FALSE for the string -2147483648 even that
618 ** that number will, in theory fit in a 32-bit integer.  But positive
619 ** 2147483648 will not fit in 32 bits.  So it seems safer to return
620 ** false.
621 */
sqliteFitsIn32Bits(const char * zNum)622 int sqliteFitsIn32Bits(const char *zNum){
623   int i, c;
624   if( *zNum=='-' || *zNum=='+' ) zNum++;
625   for(i=0; (c=zNum[i])>='0' && c<='9'; i++){}
626   return i<10 || (i==10 && memcmp(zNum,"2147483647",10)<=0);
627 }
628 
629 /* This comparison routine is what we use for comparison operations
630 ** between numeric values in an SQL expression.  "Numeric" is a little
631 ** bit misleading here.  What we mean is that the strings have a
632 ** type of "numeric" from the point of view of SQL.  The strings
633 ** do not necessarily contain numbers.  They could contain text.
634 **
635 ** If the input strings both look like actual numbers then they
636 ** compare in numerical order.  Numerical strings are always less
637 ** than non-numeric strings so if one input string looks like a
638 ** number and the other does not, then the one that looks like
639 ** a number is the smaller.  Non-numeric strings compare in
640 ** lexigraphical order (the same order as strcmp()).
641 */
sqliteCompare(const char * atext,const char * btext)642 int sqliteCompare(const char *atext, const char *btext){
643   int result;
644   int isNumA, isNumB;
645   if( atext==0 ){
646     return -1;
647   }else if( btext==0 ){
648     return 1;
649   }
650   isNumA = sqliteIsNumber(atext);
651   isNumB = sqliteIsNumber(btext);
652   if( isNumA ){
653     if( !isNumB ){
654       result = -1;
655     }else{
656       double rA, rB;
657       rA = sqliteAtoF(atext, 0);
658       rB = sqliteAtoF(btext, 0);
659       if( rA<rB ){
660         result = -1;
661       }else if( rA>rB ){
662         result = +1;
663       }else{
664         result = 0;
665       }
666     }
667   }else if( isNumB ){
668     result = +1;
669   }else {
670     result = strcmp(atext, btext);
671   }
672   return result;
673 }
674 
675 /*
676 ** This routine is used for sorting.  Each key is a list of one or more
677 ** null-terminated elements.  The list is terminated by two nulls in
678 ** a row.  For example, the following text is a key with three elements
679 **
680 **            Aone\000Dtwo\000Athree\000\000
681 **
682 ** All elements begin with one of the characters "+-AD" and end with "\000"
683 ** with zero or more text elements in between.  Except, NULL elements
684 ** consist of the special two-character sequence "N\000".
685 **
686 ** Both arguments will have the same number of elements.  This routine
687 ** returns negative, zero, or positive if the first argument is less
688 ** than, equal to, or greater than the first.  (Result is a-b).
689 **
690 ** Each element begins with one of the characters "+", "-", "A", "D".
691 ** This character determines the sort order and collating sequence:
692 **
693 **     +      Sort numerically in ascending order
694 **     -      Sort numerically in descending order
695 **     A      Sort as strings in ascending order
696 **     D      Sort as strings in descending order.
697 **
698 ** For the "+" and "-" sorting, pure numeric strings (strings for which the
699 ** isNum() function above returns TRUE) always compare less than strings
700 ** that are not pure numerics.  Non-numeric strings compare in memcmp()
701 ** order.  This is the same sort order as the sqliteCompare() function
702 ** above generates.
703 **
704 ** The last point is a change from version 2.6.3 to version 2.7.0.  In
705 ** version 2.6.3 and earlier, substrings of digits compare in numerical
706 ** and case was used only to break a tie.
707 **
708 ** Elements that begin with 'A' or 'D' compare in memcmp() order regardless
709 ** of whether or not they look like a number.
710 **
711 ** Note that the sort order imposed by the rules above is the same
712 ** from the ordering defined by the "<", "<=", ">", and ">=" operators
713 ** of expressions and for indices.  This was not the case for version
714 ** 2.6.3 and earlier.
715 */
sqliteSortCompare(const char * a,const char * b)716 int sqliteSortCompare(const char *a, const char *b){
717   int res = 0;
718   int isNumA, isNumB;
719   int dir = 0;
720 
721   while( res==0 && *a && *b ){
722     if( a[0]=='N' || b[0]=='N' ){
723       if( a[0]==b[0] ){
724         a += 2;
725         b += 2;
726         continue;
727       }
728       if( a[0]=='N' ){
729         dir = b[0];
730         res = -1;
731       }else{
732         dir = a[0];
733         res = +1;
734       }
735       break;
736     }
737     assert( a[0]==b[0] );
738     if( (dir=a[0])=='A' || a[0]=='D' ){
739       res = strcmp(&a[1],&b[1]);
740       if( res ) break;
741     }else{
742       isNumA = sqliteIsNumber(&a[1]);
743       isNumB = sqliteIsNumber(&b[1]);
744       if( isNumA ){
745         double rA, rB;
746         if( !isNumB ){
747           res = -1;
748           break;
749         }
750         rA = sqliteAtoF(&a[1], 0);
751         rB = sqliteAtoF(&b[1], 0);
752         if( rA<rB ){
753           res = -1;
754           break;
755         }
756         if( rA>rB ){
757           res = +1;
758           break;
759         }
760       }else if( isNumB ){
761         res = +1;
762         break;
763       }else{
764         res = strcmp(&a[1],&b[1]);
765         if( res ) break;
766       }
767     }
768     a += strlen(&a[1]) + 2;
769     b += strlen(&b[1]) + 2;
770   }
771   if( dir=='-' || dir=='D' ) res = -res;
772   return res;
773 }
774 
775 /*
776 ** Some powers of 64.  These constants are needed in the
777 ** sqliteRealToSortable() routine below.
778 */
779 #define _64e3  (64.0 * 64.0 * 64.0)
780 #define _64e4  (64.0 * 64.0 * 64.0 * 64.0)
781 #define _64e15 (_64e3 * _64e4 * _64e4 * _64e4)
782 #define _64e16 (_64e4 * _64e4 * _64e4 * _64e4)
783 #define _64e63 (_64e15 * _64e16 * _64e16 * _64e16)
784 #define _64e64 (_64e16 * _64e16 * _64e16 * _64e16)
785 
786 /*
787 ** The following procedure converts a double-precision floating point
788 ** number into a string.  The resulting string has the property that
789 ** two such strings comparied using strcmp() or memcmp() will give the
790 ** same results as a numeric comparison of the original floating point
791 ** numbers.
792 **
793 ** This routine is used to generate database keys from floating point
794 ** numbers such that the keys sort in the same order as the original
795 ** floating point numbers even though the keys are compared using
796 ** memcmp().
797 **
798 ** The calling function should have allocated at least 14 characters
799 ** of space for the buffer z[].
800 */
sqliteRealToSortable(double r,char * z)801 void sqliteRealToSortable(double r, char *z){
802   int neg;
803   int exp;
804   int cnt = 0;
805 
806   /* This array maps integers between 0 and 63 into base-64 digits.
807   ** The digits must be chosen such at their ASCII codes are increasing.
808   ** This means we can not use the traditional base-64 digit set. */
809   static const char zDigit[] =
810      "0123456789"
811      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
812      "abcdefghijklmnopqrstuvwxyz"
813      "|~";
814   if( r<0.0 ){
815     neg = 1;
816     r = -r;
817     *z++ = '-';
818   } else {
819     neg = 0;
820     *z++ = '0';
821   }
822   exp = 0;
823 
824   if( r==0.0 ){
825     exp = -1024;
826   }else if( r<(0.5/64.0) ){
827     while( r < 0.5/_64e64 && exp > -961  ){ r *= _64e64;  exp -= 64; }
828     while( r < 0.5/_64e16 && exp > -1009 ){ r *= _64e16;  exp -= 16; }
829     while( r < 0.5/_64e4  && exp > -1021 ){ r *= _64e4;   exp -= 4; }
830     while( r < 0.5/64.0   && exp > -1024 ){ r *= 64.0;    exp -= 1; }
831   }else if( r>=0.5 ){
832     while( r >= 0.5*_64e63 && exp < 960  ){ r *= 1.0/_64e64; exp += 64; }
833     while( r >= 0.5*_64e15 && exp < 1008 ){ r *= 1.0/_64e16; exp += 16; }
834     while( r >= 0.5*_64e3  && exp < 1020 ){ r *= 1.0/_64e4;  exp += 4; }
835     while( r >= 0.5        && exp < 1023 ){ r *= 1.0/64.0;   exp += 1; }
836   }
837   if( neg ){
838     exp = -exp;
839     r = -r;
840   }
841   exp += 1024;
842   r += 0.5;
843   if( exp<0 ) return;
844   if( exp>=2048 || r>=1.0 ){
845     strcpy(z, "~~~~~~~~~~~~");
846     return;
847   }
848   *z++ = zDigit[(exp>>6)&0x3f];
849   *z++ = zDigit[exp & 0x3f];
850   while( r>0.0 && cnt<10 ){
851     int digit;
852     r *= 64.0;
853     digit = (int)r;
854     assert( digit>=0 && digit<64 );
855     *z++ = zDigit[digit & 0x3f];
856     r -= digit;
857     cnt++;
858   }
859   *z = 0;
860 }
861 
862 #ifdef SQLITE_UTF8
863 /*
864 ** X is a pointer to the first byte of a UTF-8 character.  Increment
865 ** X so that it points to the next character.  This only works right
866 ** if X points to a well-formed UTF-8 string.
867 */
868 #define sqliteNextChar(X)  while( (0xc0&*++(X))==0x80 ){}
869 #define sqliteCharVal(X)   sqlite_utf8_to_int(X)
870 
871 #else /* !defined(SQLITE_UTF8) */
872 /*
873 ** For iso8859 encoding, the next character is just the next byte.
874 */
875 #define sqliteNextChar(X)  (++(X));
876 #define sqliteCharVal(X)   ((int)*(X))
877 
878 #endif /* defined(SQLITE_UTF8) */
879 
880 
881 #ifdef SQLITE_UTF8
882 /*
883 ** Convert the UTF-8 character to which z points into a 31-bit
884 ** UCS character.  This only works right if z points to a well-formed
885 ** UTF-8 string.
886 */
sqlite_utf8_to_int(const unsigned char * z)887 static int sqlite_utf8_to_int(const unsigned char *z){
888   int c;
889   static const int initVal[] = {
890       0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,
891      15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,
892      30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,
893      45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,
894      60,  61,  62,  63,  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,
895      75,  76,  77,  78,  79,  80,  81,  82,  83,  84,  85,  86,  87,  88,  89,
896      90,  91,  92,  93,  94,  95,  96,  97,  98,  99, 100, 101, 102, 103, 104,
897     105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
898     120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134,
899     135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
900     150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164,
901     165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
902     180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,   0,   1,   2,
903       3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,
904      18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,   0,
905       1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
906       0,   1,   2,   3,   4,   5,   6,   7,   0,   1,   2,   3,   0,   1, 254,
907     255,
908   };
909   c = initVal[*(z++)];
910   while( (0xc0&*z)==0x80 ){
911     c = (c<<6) | (0x3f&*(z++));
912   }
913   return c;
914 }
915 #endif
916 
917 /*
918 ** Compare two UTF-8 strings for equality where the first string can
919 ** potentially be a "glob" expression.  Return true (1) if they
920 ** are the same and false (0) if they are different.
921 **
922 ** Globbing rules:
923 **
924 **      '*'       Matches any sequence of zero or more characters.
925 **
926 **      '?'       Matches exactly one character.
927 **
928 **     [...]      Matches one character from the enclosed list of
929 **                characters.
930 **
931 **     [^...]     Matches one character not in the enclosed list.
932 **
933 ** With the [...] and [^...] matching, a ']' character can be included
934 ** in the list by making it the first character after '[' or '^'.  A
935 ** range of characters can be specified using '-'.  Example:
936 ** "[a-z]" matches any single lower-case letter.  To match a '-', make
937 ** it the last character in the list.
938 **
939 ** This routine is usually quick, but can be N**2 in the worst case.
940 **
941 ** Hints: to match '*' or '?', put them in "[]".  Like this:
942 **
943 **         abc[*]xyz        Matches "abc*xyz" only
944 */
945 int
sqliteGlobCompare(const unsigned char * zPattern,const unsigned char * zString)946 sqliteGlobCompare(const unsigned char *zPattern, const unsigned char *zString){
947   register int c;
948   int invert;
949   int seen;
950   int c2;
951 
952   while( (c = *zPattern)!=0 ){
953     switch( c ){
954       case '*':
955         while( (c=zPattern[1]) == '*' || c == '?' ){
956           if( c=='?' ){
957             if( *zString==0 ) return 0;
958             sqliteNextChar(zString);
959           }
960           zPattern++;
961         }
962         if( c==0 ) return 1;
963         if( c=='[' ){
964           while( *zString && sqliteGlobCompare(&zPattern[1],zString)==0 ){
965             sqliteNextChar(zString);
966           }
967           return *zString!=0;
968         }else{
969           while( (c2 = *zString)!=0 ){
970             while( c2 != 0 && c2 != c ){ c2 = *++zString; }
971             if( c2==0 ) return 0;
972             if( sqliteGlobCompare(&zPattern[1],zString) ) return 1;
973             sqliteNextChar(zString);
974           }
975           return 0;
976         }
977       case '?': {
978         if( *zString==0 ) return 0;
979         sqliteNextChar(zString);
980         zPattern++;
981         break;
982       }
983       case '[': {
984         int prior_c = 0;
985         seen = 0;
986         invert = 0;
987         c = sqliteCharVal(zString);
988         if( c==0 ) return 0;
989         c2 = *++zPattern;
990         if( c2=='^' ){ invert = 1; c2 = *++zPattern; }
991         if( c2==']' ){
992           if( c==']' ) seen = 1;
993           c2 = *++zPattern;
994         }
995         while( (c2 = sqliteCharVal(zPattern))!=0 && c2!=']' ){
996           if( c2=='-' && zPattern[1]!=']' && zPattern[1]!=0 && prior_c>0 ){
997             zPattern++;
998             c2 = sqliteCharVal(zPattern);
999             if( c>=prior_c && c<=c2 ) seen = 1;
1000             prior_c = 0;
1001           }else if( c==c2 ){
1002             seen = 1;
1003             prior_c = c2;
1004           }else{
1005             prior_c = c2;
1006           }
1007           sqliteNextChar(zPattern);
1008         }
1009         if( c2==0 || (seen ^ invert)==0 ) return 0;
1010         sqliteNextChar(zString);
1011         zPattern++;
1012         break;
1013       }
1014       default: {
1015         if( c != *zString ) return 0;
1016         zPattern++;
1017         zString++;
1018         break;
1019       }
1020     }
1021   }
1022   return *zString==0;
1023 }
1024 
1025 /*
1026 ** Compare two UTF-8 strings for equality using the "LIKE" operator of
1027 ** SQL.  The '%' character matches any sequence of 0 or more
1028 ** characters and '_' matches any single character.  Case is
1029 ** not significant.
1030 **
1031 ** This routine is just an adaptation of the sqliteGlobCompare()
1032 ** routine above.
1033 */
1034 int
sqliteLikeCompare(const unsigned char * zPattern,const unsigned char * zString)1035 sqliteLikeCompare(const unsigned char *zPattern, const unsigned char *zString){
1036   register int c;
1037   int c2;
1038 
1039   while( (c = UpperToLower[*zPattern])!=0 ){
1040     switch( c ){
1041       case '%': {
1042         while( (c=zPattern[1]) == '%' || c == '_' ){
1043           if( c=='_' ){
1044             if( *zString==0 ) return 0;
1045             sqliteNextChar(zString);
1046           }
1047           zPattern++;
1048         }
1049         if( c==0 ) return 1;
1050         c = UpperToLower[c];
1051         while( (c2=UpperToLower[*zString])!=0 ){
1052           while( c2 != 0 && c2 != c ){ c2 = UpperToLower[*++zString]; }
1053           if( c2==0 ) return 0;
1054           if( sqliteLikeCompare(&zPattern[1],zString) ) return 1;
1055           sqliteNextChar(zString);
1056         }
1057         return 0;
1058       }
1059       case '_': {
1060         if( *zString==0 ) return 0;
1061         sqliteNextChar(zString);
1062         zPattern++;
1063         break;
1064       }
1065       default: {
1066         if( c != UpperToLower[*zString] ) return 0;
1067         zPattern++;
1068         zString++;
1069         break;
1070       }
1071     }
1072   }
1073   return *zString==0;
1074 }
1075 
1076 /*
1077 ** Change the sqlite.magic from SQLITE_MAGIC_OPEN to SQLITE_MAGIC_BUSY.
1078 ** Return an error (non-zero) if the magic was not SQLITE_MAGIC_OPEN
1079 ** when this routine is called.
1080 **
1081 ** This routine is a attempt to detect if two threads use the
1082 ** same sqlite* pointer at the same time.  There is a race
1083 ** condition so it is possible that the error is not detected.
1084 ** But usually the problem will be seen.  The result will be an
1085 ** error which can be used to debug the application that is
1086 ** using SQLite incorrectly.
1087 **
1088 ** Ticket #202:  If db->magic is not a valid open value, take care not
1089 ** to modify the db structure at all.  It could be that db is a stale
1090 ** pointer.  In other words, it could be that there has been a prior
1091 ** call to sqlite_close(db) and db has been deallocated.  And we do
1092 ** not want to write into deallocated memory.
1093 */
sqliteSafetyOn(sqlite * db)1094 int sqliteSafetyOn(sqlite *db){
1095   if( db->magic==SQLITE_MAGIC_OPEN ){
1096     db->magic = SQLITE_MAGIC_BUSY;
1097     return 0;
1098   }else if( db->magic==SQLITE_MAGIC_BUSY || db->magic==SQLITE_MAGIC_ERROR
1099              || db->want_to_close ){
1100     db->magic = SQLITE_MAGIC_ERROR;
1101     db->flags |= SQLITE_Interrupt;
1102   }
1103   return 1;
1104 }
1105 
1106 /*
1107 ** Change the magic from SQLITE_MAGIC_BUSY to SQLITE_MAGIC_OPEN.
1108 ** Return an error (non-zero) if the magic was not SQLITE_MAGIC_BUSY
1109 ** when this routine is called.
1110 */
sqliteSafetyOff(sqlite * db)1111 int sqliteSafetyOff(sqlite *db){
1112   if( db->magic==SQLITE_MAGIC_BUSY ){
1113     db->magic = SQLITE_MAGIC_OPEN;
1114     return 0;
1115   }else if( db->magic==SQLITE_MAGIC_OPEN || db->magic==SQLITE_MAGIC_ERROR
1116              || db->want_to_close ){
1117     db->magic = SQLITE_MAGIC_ERROR;
1118     db->flags |= SQLITE_Interrupt;
1119   }
1120   return 1;
1121 }
1122 
1123 /*
1124 ** Check to make sure we are not currently executing an sqlite_exec().
1125 ** If we are currently in an sqlite_exec(), return true and set
1126 ** sqlite.magic to SQLITE_MAGIC_ERROR.  This will cause a complete
1127 ** shutdown of the database.
1128 **
1129 ** This routine is used to try to detect when API routines are called
1130 ** at the wrong time or in the wrong sequence.
1131 */
sqliteSafetyCheck(sqlite * db)1132 int sqliteSafetyCheck(sqlite *db){
1133   if( db->pVdbe!=0 ){
1134     db->magic = SQLITE_MAGIC_ERROR;
1135     return 1;
1136   }
1137   return 0;
1138 }
1139