SQLite

  memset(p, 0, sizeof(*p));
}
static void editDist3ConfigDelete(void *pIn){
  EditDist3Config *p = (EditDist3Config*)pIn;
  editDist3ConfigClear(p);
  sqlite3_free(p);
}

/* Compare the FROM values of two EditDist3Cost objects, for sorting.
** Return negative, zero, or positive if the A is less than, equal to,
** or greater than B.
*/
static int editDist3CostCompare(EditDist3Cost *pA, EditDist3Cost *pB){
  int n = pA->nFrom;
  int rc;
  if( n>pB->nFrom ) n = pB->nFrom;
  rc = strncmp(pA->a, pB->a, n);
  if( rc==0 ) rc = pA->nFrom - pB->nFrom;
  return rc;
}

/*
** Merge together two sorted lists of EditDist3Cost objects, in order
** of increasing FROM.
*/
static EditDist3Cost *editDist3CostMerge(
  EditDist3Cost *pA,
  EditDist3Cost *pB
){
  EditDist3Cost *pHead = 0;
  EditDist3Cost **ppTail = &pHead;
  EditDist3Cost *p;
  while( pA && pB ){
    if( editDist3CostCompare(pA,pB)<=0 ){
      p = pA;
      pA = pA->pNext;
    }else{
      p = pB;
      pB = pB->pNext;
    }
    *ppTail = p;
    ppTail =  &p->pNext;
  }
  if( pA ){
    *ppTail = pA;
  }else{
    *ppTail = pB;
  }
  return pHead;
}

/*
** Sort a list of EditDist3Cost objects into order of increasing FROM
*/
static EditDist3Cost *editDist3CostSort(EditDist3Cost *pList){
  EditDist3Cost *ap[60], *p;
  int i;
  int mx = 0;
  ap[0] = 0;
  ap[1] = 0;
  while( pList ){
    p = pList;
    pList = p->pNext;
    p->pNext = 0;
    for(i=0; ap[i]; i++){
      p = editDist3CostMerge(ap[i],p);
      ap[i] = 0;
    }
    ap[i] = p;
    if( i>mx ){
      mx = i;
      ap[i+1] = 0;
    }
  }
  p = 0;
  for(i=0; i<=mx; i++){
    if( ap[i] ) p = editDist3CostMerge(p,ap[i]);
  }
  return p;
}

/*
** Load all edit-distance weights from a table.
*/
static int editDist3ConfigLoad(
  EditDist3Config *p,      /* The edit distance configuration to load */
  sqlite3 *db,            /* Load from this database */

      memcpy(pCost->a + nFrom, zTo, nTo);
      pCost->pNext = pLang->pCost;
      pLang->pCost = pCost; 
    }
  }
  rc2 = sqlite3_finalize(pStmt);
  if( rc==SQLITE_OK ) rc = rc2;
  if( rc==SQLITE_OK ){
    int iLang;
    for(iLang=0; iLang<p->nLang; iLang++){
      p->a[iLang].pCost = editDist3CostSort(p->a[iLang].pCost);
    }
  }
  return rc;
}

/*
** Return the length (in bytes) of a utf-8 character.  Or return a maximum
** of N.
*/

  memset(a2, 0, sizeof(a2[0])*n2);

  /* Fill in the a1[] matrix for all characters of the TO string */
  for(i2=0; i2<n2; i2++){
    a2[i2].nByte = utf8Len((unsigned char)z2[i2], n2-i2);
    for(p=pLang->pCost; p; p=p->pNext){
      EditDist3Cost **apNew;
      if( p->nFrom>0 ) break;
      if( i2+p->nTo>n2 ) continue;
      if( p->a[0]>z2[i2] ) break;
      if( matchTo(p, z2+i2, n2-i2)==0 ) continue;
      a2[i2].nIns++;
      apNew = sqlite3_realloc64(a2[i2].apIns, sizeof(*apNew)*a2[i2].nIns);
      if( apNew==0 ){
        res = -1;  /* Out of memory */
        goto editDist3Abort;
      }

  INSERT INTO cost1 VALUES
    (0, '', '?',  97),
    (0, '?', '',  98),
    (0, '?', '?', 99),
    (0, 'a', 'e', 50),
    (0, 'a', 'i', 70),
    (0, 'a', 'o', 75),
    (0, 'a', 'u', 81),
    (0, 'e', 'a', 50),
    (0, 'e', 'i', 52),
    (0, 'e', 'o', 72),
    (0, 'e', 'u', 82),
    (0, 'i', 'a', 70),
    (0, 'i', 'e', 52),
    (0, 'i', 'o', 75),
    (0, 'i', 'u', 83),
    (0, 'o', 'a', 75),
    (0, 'o', 'e', 72),
    (0, 'o', 'i', 75),
    (0, 'o', 'u', 40),
    (0, 'u', 'a', 81),
    (0, 'u', 'e', 82),
    (0, 'u', 'i', 83),
    (0, 'u', 'o', 40),
    (0, 'm', 'n', 45),
    (0, 'n', 'm', 45)
  ;
  CREATE TABLE words(x TEXT);
  INSERT INTO words VALUES
   ('abraham'),

} {{}}
do_execsql_test 310 {
  SELECT editdist3(a.x,b.x), a.x, b.x
    FROM words a, words b
   WHERE a.x<b.x
   ORDER BY 1, 2
   LIMIT 20
} {139 bucket pocket 144 meter motor 149 manual mental 169 crack trick 173 sinatra sonata 174 edition emotion 174 major motor 174 risk rose 174 state stone 194 deal detail 196 alert talent 196 analog catalog 196 deal legal 196 ford forum 196 risk trick 196 stone strong 197 china tina 197 congo logo 197 diana tina 197 florida gloria}
do_execsql_test 320 {
  SELECT md5sum(ed||'/'||sx||'/'||sy||',') FROM (
      SELECT editdist3(a.x,b.x) AS ed, a.x AS sx, b.x AS sy
        FROM words a, words b
       WHERE a.x<b.x
       ORDER BY 1, 2
  )
} {69d0a31872203a775e19325ea98cd053}

finish_test