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