monotone

monotone Mtn Source Tree

Root/sqlite/util.c

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

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status