ext/misc/prefixes.c

   1 /*
   2 ** 2018-04-19
   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 implements a table-valued function:
  14 **
  15 **      prefixes('abcdefg')
  16 **
  17 ** The function has a single (non-HIDDEN) column named prefix that takes
  18 ** on all prefixes of the string in its argument, including an empty string
  19 ** and the input string itself.  The order of prefixes is from longest
  20 ** to shortest.
  21 */
  22 #if !defined(SQLITE_CORE) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  23 #if !defined(SQLITEINT_H)
  24 #include "sqlite3ext.h"
  25 #endif
  26 SQLITE_EXTENSION_INIT1
  27 #include <string.h>
  28 #include <assert.h>
  29
  30 /* prefixes_vtab is a subclass of sqlite3_vtab which is
  31 ** underlying representation of the virtual table
  32 */
  33 typedef struct prefixes_vtab prefixes_vtab;
  34 struct prefixes_vtab {
  35   sqlite3_vtab base;  /* Base class - must be first */
  36   /* No additional fields are necessary */
  37 };
  38
  39 /* prefixes_cursor is a subclass of sqlite3_vtab_cursor which will
  40 ** serve as the underlying representation of a cursor that scans
  41 ** over rows of the result
  42 */
  43 typedef struct prefixes_cursor prefixes_cursor;
  44 struct prefixes_cursor {
  45   sqlite3_vtab_cursor base;  /* Base class - must be first */
  46   sqlite3_int64 iRowid;      /* The rowid */
  47   char *zStr;                /* Original string to be prefixed */
  48   int nStr;                  /* Length of the string in bytes */
  49 };
  50
  51 /*
  52 ** The prefixesConnect() method is invoked to create a new
  53 ** template virtual table.
  54 **
  55 ** Think of this routine as the constructor for prefixes_vtab objects.
  56 **
  57 ** All this routine needs to do is:
  58 **
  59 **    (1) Allocate the prefixes_vtab object and initialize all fields.
  60 **
  61 **    (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
  62 **        result set of queries against the virtual table will look like.
  63 */
  64 static int prefixesConnect(
  65   sqlite3 *db,
  66   void *pAux,
  67   int argc, const char *const*argv,
  68   sqlite3_vtab **ppVtab,
  69   char **pzErr
  70 ){
  71   prefixes_vtab *pNew;
  72   int rc;
  73
  74   rc = sqlite3_declare_vtab(db,
  75            "CREATE TABLE prefixes(prefix TEXT, original_string TEXT HIDDEN)"
  76        );
  77   if( rc==SQLITE_OK ){
  78     pNew = sqlite3_malloc( sizeof(*pNew) );
  79     *ppVtab = (sqlite3_vtab*)pNew;
  80     if( pNew==0 ) return SQLITE_NOMEM;
  81     memset(pNew, 0, sizeof(*pNew));
  82     sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
  83   }
  84   return rc;
  85 }
  86
  87 /*
  88 ** This method is the destructor for prefixes_vtab objects.
  89 */
  90 static int prefixesDisconnect(sqlite3_vtab *pVtab){
  91   prefixes_vtab *p = (prefixes_vtab*)pVtab;
  92   sqlite3_free(p);
  93   return SQLITE_OK;
  94 }
  95
  96 /*
  97 ** Constructor for a new prefixes_cursor object.
  98 */
  99 static int prefixesOpen(sqlite3_vtab *p, sqlite3_vtab_cursor **ppCursor){
 100   prefixes_cursor *pCur;
 101   pCur = sqlite3_malloc( sizeof(*pCur) );
 102   if( pCur==0 ) return SQLITE_NOMEM;
 103   memset(pCur, 0, sizeof(*pCur));
 104   *ppCursor = &pCur->base;
 105   return SQLITE_OK;
 106 }
 107
 108 /*
 109 ** Destructor for a prefixes_cursor.
 110 */
 111 static int prefixesClose(sqlite3_vtab_cursor *cur){
 112   prefixes_cursor *pCur = (prefixes_cursor*)cur;
 113   sqlite3_free(pCur->zStr);
 114   sqlite3_free(pCur);
 115   return SQLITE_OK;
 116 }
 117
 118
 119 /*
 120 ** Advance a prefixes_cursor to its next row of output.
 121 */
 122 static int prefixesNext(sqlite3_vtab_cursor *cur){
 123   prefixes_cursor *pCur = (prefixes_cursor*)cur;
 124   pCur->iRowid++;
 125   return SQLITE_OK;
 126 }
 127
 128 /*
 129 ** Return values of columns for the row at which the prefixes_cursor
 130 ** is currently pointing.
 131 */
 132 static int prefixesColumn(
 133   sqlite3_vtab_cursor *cur,   /* The cursor */
 134   sqlite3_context *ctx,       /* First argument to sqlite3_result_...() */
 135   int i                       /* Which column to return */
 136 ){
 137   prefixes_cursor *pCur = (prefixes_cursor*)cur;
 138   switch( i ){
 139     case 0:
 140       sqlite3_result_text(ctx, pCur->zStr, pCur->nStr - (int)pCur->iRowid,
 141                           0);
 142       break;
 143     default:
 144       sqlite3_result_text(ctx, pCur->zStr, pCur->nStr, 0);
 145       break;
 146   }
 147   return SQLITE_OK;
 148 }
 149
 150 /*
 151 ** Return the rowid for the current row.  In this implementation, the
 152 ** rowid is the same as the output value.
 153 */
 154 static int prefixesRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
 155   prefixes_cursor *pCur = (prefixes_cursor*)cur;
 156   *pRowid = pCur->iRowid;
 157   return SQLITE_OK;
 158 }
 159
 160 /*
 161 ** Return TRUE if the cursor has been moved off of the last
 162 ** row of output.
 163 */
 164 static int prefixesEof(sqlite3_vtab_cursor *cur){
 165   prefixes_cursor *pCur = (prefixes_cursor*)cur;
 166   return pCur->iRowid>pCur->nStr;
 167 }
 168
 169 /*
 170 ** This method is called to "rewind" the prefixes_cursor object back
 171 ** to the first row of output.  This method is always called at least
 172 ** once prior to any call to prefixesColumn() or prefixesRowid() or
 173 ** prefixesEof().
 174 */
 175 static int prefixesFilter(
 176   sqlite3_vtab_cursor *pVtabCursor,
 177   int idxNum, const char *idxStr,
 178   int argc, sqlite3_value **argv
 179 ){
 180   prefixes_cursor *pCur = (prefixes_cursor *)pVtabCursor;
 181   sqlite3_free(pCur->zStr);
 182   if( argc>0 ){
 183     pCur->zStr = sqlite3_mprintf("%s", sqlite3_value_text(argv[0]));
 184     pCur->nStr = pCur->zStr ? (int)strlen(pCur->zStr) : 0;
 185   }else{
 186     pCur->zStr = 0;
 187     pCur->nStr = 0;
 188   }
 189   pCur->iRowid = 0;
 190   return SQLITE_OK;
 191 }
 192
 193 /*
 194 ** SQLite will invoke this method one or more times while planning a query
 195 ** that uses the virtual table.  This routine needs to create
 196 ** a query plan for each invocation and compute an estimated cost for that
 197 ** plan.
 198 */
 199 static int prefixesBestIndex(
 200   sqlite3_vtab *tab,
 201   sqlite3_index_info *pIdxInfo
 202 ){
 203   /* Search for a usable equality constraint against column 1
 204   ** (original_string) and use it if at all possible */
 205   int i;
 206   const struct sqlite3_index_constraint *p;
 207
 208   for(i=0, p=pIdxInfo->aConstraint; i<pIdxInfo->nConstraint; i++, p++){
 209     if( p->iColumn!=1 ) continue;
 210     if( p->op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
 211     if( !p->usable ) continue;
 212     pIdxInfo->aConstraintUsage[i].argvIndex = 1;
 213     pIdxInfo->aConstraintUsage[i].omit = 1;
 214     pIdxInfo->estimatedCost = (double)10;
 215     pIdxInfo->estimatedRows = 10;
 216     return SQLITE_OK;
 217   }
 218   pIdxInfo->estimatedCost = (double)1000000000;
 219   pIdxInfo->estimatedRows = 1000000000;
 220   return SQLITE_OK;
 221 }
 222
 223 /*
 224 ** This following structure defines all the methods for the
 225 ** virtual table.
 226 */
 227 static sqlite3_module prefixesModule = {
 228   /* iVersion    */ 0,
 229   /* xCreate     */ 0,
 230   /* xConnect    */ prefixesConnect,
 231   /* xBestIndex  */ prefixesBestIndex,
 232   /* xDisconnect */ prefixesDisconnect,
 233   /* xDestroy    */ 0,
 234   /* xOpen       */ prefixesOpen,
 235   /* xClose      */ prefixesClose,
 236   /* xFilter     */ prefixesFilter,
 237   /* xNext       */ prefixesNext,
 238   /* xEof        */ prefixesEof,
 239   /* xColumn     */ prefixesColumn,
 240   /* xRowid      */ prefixesRowid,
 241   /* xUpdate     */ 0,
 242   /* xBegin      */ 0,
 243   /* xSync       */ 0,
 244   /* xCommit     */ 0,
 245   /* xRollback   */ 0,
 246   /* xFindMethod */ 0,
 247   /* xRename     */ 0,
 248   /* xSavepoint  */ 0,
 249   /* xRelease    */ 0,
 250   /* xRollbackTo */ 0,
 251   /* xShadowName */ 0,
 252   /* xIntegrity  */ 0
 253 };
 254
 255 /*
 256 ** This is a copy of the SQLITE_SKIP_UTF8(zIn) macro in sqliteInt.h.
 257 **
 258 ** Assuming zIn points to the first byte of a UTF-8 character,
 259 ** advance zIn to point to the first byte of the next UTF-8 character.
 260 */
 261 #define PREFIX_SKIP_UTF8(zIn) {                        \
 262   if( (*(zIn++))>=0xc0 ){                              \
 263     while( (*zIn & 0xc0)==0x80 ){ zIn++; }             \
 264   }                                                    \
 265 }
 266
 267 /*
 268 ** Implementation of function prefix_length(). This function accepts two
 269 ** strings as arguments and returns the length in characters (not bytes),
 270 ** of the longest prefix shared by the two strings. For example:
 271 **
 272 **   prefix_length('abcdxxx', 'abcyy') == 3
 273 **   prefix_length('abcdxxx', 'bcyyy') == 0
 274 **   prefix_length('abcdxxx', 'ab')    == 2
 275 **   prefix_length('ab',      'abcd')  == 2
 276 **
 277 ** This function assumes the input is well-formed utf-8. If it is not,
 278 ** it is possible for this function to return -1.
 279 */
 280 static void prefixLengthFunc(
 281   sqlite3_context *ctx,
 282   int nVal,
 283   sqlite3_value **apVal
 284 ){
 285   int nByte;                      /* Number of bytes to compare */
 286   int nRet = 0;                   /* Return value */
 287   const unsigned char *zL = sqlite3_value_text(apVal[0]);
 288   const unsigned char *zR = sqlite3_value_text(apVal[1]);
 289   int nL = sqlite3_value_bytes(apVal[0]);
 290   int nR = sqlite3_value_bytes(apVal[1]);
 291   int i;
 292
 293   nByte = (nL > nR ? nL : nR);
 294   for(i=0; i<nByte; i++){
 295     if( zL[i]!=zR[i] ) break;
 296     if( (zL[i] & 0xC0)!=0x80 ) nRet++;
 297   }
 298
 299   if( (zL[i] & 0xC0)==0x80 ) nRet--;
 300   sqlite3_result_int(ctx, nRet);
 301 }
 302
 303 #ifdef _WIN32
 304 __declspec(dllexport)
 305 #endif
 306 int sqlite3_prefixes_init(
 307   sqlite3 *db,
 308   char **pzErrMsg,
 309   const sqlite3_api_routines *pApi
 310 ){
 311   int rc = SQLITE_OK;
 312   SQLITE_EXTENSION_INIT2(pApi);
 313   rc = sqlite3_create_module(db, "prefixes", &prefixesModule, 0);
 314   if( rc==SQLITE_OK ){
 315     rc = sqlite3_create_function(
 316         db, "prefix_length", 2, SQLITE_UTF8, 0, prefixLengthFunc, 0, 0
 317     );
 318   }
 319   return rc;
 320 }
 321 #endif /* !defined(SQLITE_CORE) || !defined(SQLITE_OMIT_VIRTUALTABLE) */