1 /* 2 ** 2013-02-28 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 ** 13 ** This file contains code to implement the next_char(A,T,F,W) SQL function. 14 ** 15 ** The next_char(A,T,F,H) function finds all valid "next" characters for 16 ** string A given the vocabulary in T.F. The T.F field should be indexed. 17 ** If the W value exists and is a non-empty string, then it is an SQL 18 ** expression that limits the entries in T.F that will be considered. 19 ** 20 ** For example, suppose an application has a dictionary like this: 21 ** 22 ** CREATE TABLE dictionary(word TEXT UNIQUE); 23 ** 24 ** Further suppose that for user keypad entry, it is desired to disable 25 ** (gray out) keys that are not valid as the next character. If the 26 ** the user has previously entered (say) 'cha' then to find all allowed 27 ** next characters (and thereby determine when keys should not be grayed 28 ** out) run the following query: 29 ** 30 ** SELECT next_char('cha','dictionary','word'); 31 */ 32 #include "sqlite3ext.h" 33 SQLITE_EXTENSION_INIT1 34 #include <string.h> 35 36 /* 37 ** A structure to hold context of the next_char() computation across 38 ** nested function calls. 39 */ 40 typedef struct nextCharContext nextCharContext; 41 struct nextCharContext { 42 sqlite3 *db; /* Database connection */ 43 sqlite3_stmt *pStmt; /* Prepared statement used to query */ 44 const unsigned char *zPrefix; /* Prefix to scan */ 45 int nPrefix; /* Size of zPrefix in bytes */ 46 int nAlloc; /* Space allocated to aResult */ 47 int nUsed; /* Space used in aResult */ 48 unsigned int *aResult; /* Array of next characters */ 49 int mallocFailed; /* True if malloc fails */ 50 int otherError; /* True for any other failure */ 51 }; 52 53 /* 54 ** Append a result character if the character is not already in the 55 ** result. 56 */ 57 static void nextCharAppend(nextCharContext *p, unsigned c){ 58 int i; 59 for(i=0; i<p->nUsed; i++){ 60 if( p->aResult[i]==c ) return; 61 } 62 if( p->nUsed+1 > p->nAlloc ){ 63 unsigned int *aNew; 64 int n = p->nAlloc*2 + 30; 65 aNew = sqlite3_realloc(p->aResult, n*sizeof(unsigned int)); 66 if( aNew==0 ){ 67 p->mallocFailed = 1; 68 return; 69 }else{ 70 p->aResult = aNew; 71 p->nAlloc = n; 72 } 73 } 74 p->aResult[p->nUsed++] = c; 75 } 76 77 /* 78 ** Write a character into z[] as UTF8. Return the number of bytes needed 79 ** to hold the character 80 */ 81 static int writeUtf8(unsigned char *z, unsigned c){ 82 if( c<0x00080 ){ 83 z[0] = (unsigned char)(c&0xff); 84 return 1; 85 } 86 if( c<0x00800 ){ 87 z[0] = 0xC0 + (unsigned char)((c>>6)&0x1F); 88 z[1] = 0x80 + (unsigned char)(c & 0x3F); 89 return 2; 90 } 91 if( c<0x10000 ){ 92 z[0] = 0xE0 + (unsigned char)((c>>12)&0x0F); 93 z[1] = 0x80 + (unsigned char)((c>>6) & 0x3F); 94 z[2] = 0x80 + (unsigned char)(c & 0x3F); 95 return 3; 96 } 97 z[0] = 0xF0 + (unsigned char)((c>>18) & 0x07); 98 z[1] = 0x80 + (unsigned char)((c>>12) & 0x3F); 99 z[2] = 0x80 + (unsigned char)((c>>6) & 0x3F); 100 z[3] = 0x80 + (unsigned char)(c & 0x3F); 101 return 4; 102 } 103 104 /* 105 ** Read a UTF8 character out of z[] and write it into *pOut. Return 106 ** the number of bytes in z[] that were used to construct the character. 107 */ 108 static int readUtf8(const unsigned char *z, unsigned *pOut){ 109 static const unsigned char validBits[] = { 110 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 111 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 112 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 113 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 114 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 115 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 116 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 117 0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00, 118 }; 119 unsigned c = z[0]; 120 if( c<0xc0 ){ 121 *pOut = c; 122 return 1; 123 }else{ 124 int n = 1; 125 c = validBits[c-0xc0]; 126 while( (z[n] & 0xc0)==0x80 ){ 127 c = (c<<6) + (0x3f & z[n++]); 128 } 129 if( c<0x80 || (c&0xFFFFF800)==0xD800 || (c&0xFFFFFFFE)==0xFFFE ){ 130 c = 0xFFFD; 131 } 132 *pOut = c; 133 return n; 134 } 135 } 136 137 /* 138 ** The nextCharContext structure has been set up. Add all "next" characters 139 ** to the result set. 140 */ 141 static void findNextChars(nextCharContext *p){ 142 unsigned cPrev = 0; 143 unsigned char zPrev[8]; 144 int n, rc; 145 146 for(;;){ 147 sqlite3_bind_text(p->pStmt, 1, (char*)p->zPrefix, p->nPrefix, 148 SQLITE_STATIC); 149 n = writeUtf8(zPrev, cPrev+1); 150 sqlite3_bind_text(p->pStmt, 2, (char*)zPrev, n, SQLITE_STATIC); 151 rc = sqlite3_step(p->pStmt); 152 if( rc==SQLITE_DONE ){ 153 sqlite3_reset(p->pStmt); 154 return; 155 }else if( rc!=SQLITE_ROW ){ 156 p->otherError = rc; 157 return; 158 }else{ 159 const unsigned char *zOut = sqlite3_column_text(p->pStmt, 0); 160 unsigned cNext; 161 n = readUtf8(zOut+p->nPrefix, &cNext); 162 sqlite3_reset(p->pStmt); 163 nextCharAppend(p, cNext); 164 cPrev = cNext; 165 if( p->mallocFailed ) return; 166 } 167 } 168 } 169 170 171 /* 172 ** next_character(A,T,F,W) 173 ** 174 ** Return a string composted of all next possible characters after 175 ** A for elements of T.F. If W is supplied, then it is an SQL expression 176 ** that limits the elements in T.F that are considered. 177 */ 178 static void nextCharFunc( 179 sqlite3_context *context, 180 int argc, 181 sqlite3_value **argv 182 ){ 183 nextCharContext c; 184 const unsigned char *zTable = sqlite3_value_text(argv[1]); 185 const unsigned char *zField = sqlite3_value_text(argv[2]); 186 const unsigned char *zWhere; 187 char *zSql; 188 int rc; 189 190 memset(&c, 0, sizeof(c)); 191 c.db = sqlite3_context_db_handle(context); 192 c.zPrefix = sqlite3_value_text(argv[0]); 193 c.nPrefix = sqlite3_value_bytes(argv[0]); 194 if( zTable==0 || zField==0 || c.zPrefix==0 ) return; 195 if( argc<4 196 || (zWhere = sqlite3_value_text(argv[3]))==0 197 || zWhere[0]==0 198 ){ 199 zSql = sqlite3_mprintf( 200 "SELECT \"%w\" FROM \"%w\"" 201 " WHERE \"%w\">=(?1 || ?2)" 202 " AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */ 203 " ORDER BY 1 ASC LIMIT 1", 204 zField, zTable, zField, zField); 205 }else{ 206 zSql = sqlite3_mprintf( 207 "SELECT \"%w\" FROM \"%w\"" 208 " WHERE \"%w\">=(?1 || ?2)" 209 " AND \"%w\"<=(?1 || char(1114111))" /* 1114111 == 0x10ffff */ 210 " AND (%s)" 211 " ORDER BY 1 ASC LIMIT 1", 212 zField, zTable, zField, zField, zWhere); 213 } 214 if( zSql==0 ){ 215 sqlite3_result_error_nomem(context); 216 return; 217 } 218 219 rc = sqlite3_prepare_v2(c.db, zSql, -1, &c.pStmt, 0); 220 sqlite3_free(zSql); 221 if( rc ){ 222 sqlite3_result_error(context, sqlite3_errmsg(c.db), -1); 223 return; 224 } 225 findNextChars(&c); 226 if( c.mallocFailed ){ 227 sqlite3_result_error_nomem(context); 228 }else{ 229 unsigned char *pRes; 230 pRes = sqlite3_malloc( c.nUsed*4 + 1 ); 231 if( pRes==0 ){ 232 sqlite3_result_error_nomem(context); 233 }else{ 234 int i; 235 int n = 0; 236 for(i=0; i<c.nUsed; i++){ 237 n += writeUtf8(pRes+n, c.aResult[i]); 238 } 239 pRes[n] = 0; 240 sqlite3_result_text(context, (const char*)pRes, n, sqlite3_free); 241 } 242 } 243 sqlite3_finalize(c.pStmt); 244 sqlite3_free(c.aResult); 245 } 246 247 #ifdef _WIN32 248 __declspec(dllexport) 249 #endif 250 int sqlite3_nextchar_init( 251 sqlite3 *db, 252 char **pzErrMsg, 253 const sqlite3_api_routines *pApi 254 ){ 255 int rc = SQLITE_OK; 256 SQLITE_EXTENSION_INIT2(pApi); 257 (void)pzErrMsg; /* Unused parameter */ 258 rc = sqlite3_create_function(db, "next_char", 3, SQLITE_UTF8, 0, 259 nextCharFunc, 0, 0); 260 if( rc==SQLITE_OK ){ 261 rc = sqlite3_create_function(db, "next_char", 4, SQLITE_UTF8, 0, 262 nextCharFunc, 0, 0); 263 } 264 return rc; 265 } 266