SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the implementation of generic hash-tables
** used in SQLite.
**
** $Id: hash.c,v 1.24 2007/09/04 14:31:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <assert.h>

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**

    assert( pH->first==0 );
    assert( pH->count==0 );
    sqlite3HashClear(pH);
  }
}

/* Attempt to locate an element of the hash table pH with a key
** that matches pKey,nKey.  Return a pointer to the corresponding 
** HashElem structure for this element if it is found, or NULL
** otherwise.
*/
HashElem *sqlite3HashFindElem(const Hash *pH, const void *pKey, int nKey){
  int h;             /* A hash on key */
  HashElem *elem;    /* The element that matches key */
  int (*xHash)(const void*,int);  /* The hash function */

  if( pH==0 || pH->ht==0 ) return 0;
  xHash = hashFunction(pH->keyClass);
  assert( xHash!=0 );
  h = (*xHash)(pKey,nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
  return elem;
}

/* Attempt to locate an element of the hash table pH with a key
** that matches pKey,nKey.  Return the data for this element if it is
** found, or NULL if there is no match.
*/
void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
  HashElem *elem;    /* The element that matches key */
  elem = sqlite3HashFindElem(pH, pKey, nKey);
  return elem ? elem->data : 0;
}

/* Insert an element into the hash table pH.  The key is pKey,nKey
** and the data is "data".
**
** If no element exists with a matching key, then a new

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.11 2007/09/04 14:31:47 danielk1977 Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;

/*
** Access routines.  To delete, insert a NULL pointer.
*/
void sqlite3HashInit(Hash*, int keytype, int copyKey);
void *sqlite3HashInsert(Hash*, const void *pKey, int nKey, void *pData);
void *sqlite3HashFind(const Hash*, const void *pKey, int nKey);
HashElem *sqlite3HashFindElem(const Hash*, const void *pKey, int nKey);
void sqlite3HashClear(Hash*);

/*
** Macros for looping over all elements of a hash table.  The idiom is
** like this:
**
**   Hash h;

**     Read operations. Both of these read from both the underlying file
**     first then adjust their result based on pending writes in the 
**     write-op queue.   So async.queueMutex is held for the duration
**     of these operations to prevent other threads from changing the
**     queue in mid operation.
**    
**
**         asyncLock, asyncUnlock, asyncCheckReservedLock
**    
**     These primitives implement in-process locking using a hash table
**     on the file name.  Files are locked correctly for connections coming
**     from the same process.  But other processes cannot see these locks
**     and will therefore not honor them.
**
**

/* Possible values of AsyncWrite.op */
#define ASYNC_NOOP          0
#define ASYNC_WRITE         1
#define ASYNC_SYNC          2
#define ASYNC_TRUNCATE      3
#define ASYNC_CLOSE         4


#define ASYNC_DELETE        5
#define ASYNC_OPENEXCLUSIVE 6


/* Names of opcodes.  Used for debugging only.
** Make sure these stay in sync with the macros above!
*/
static const char *azOpcodeName[] = {
  "NOOP", "WRITE", "SYNC", "TRUNCATE", "CLOSE", "DELETE", "OPENEX"

};

/*
** Entries on the write-op queue are instances of the AsyncWrite
** structure, defined here.
**
** The interpretation of the iOffset and nByte variables varies depending 
** on the value of AsyncWrite.op:
**
** ASYNC_NOOP:
**     No values used.
**
** ASYNC_WRITE:
**     iOffset -> Offset in file to write to.
**     nByte   -> Number of bytes of data to write (pointed to by zBuf).
**
** ASYNC_SYNC:
**     nByte   -> flags to pass to sqlite3OsSync().
**
** ASYNC_TRUNCATE:
**     iOffset -> Size to truncate file to.
**     nByte   -> Unused.
**
** ASYNC_CLOSE:
**     iOffset -> Unused.
**     nByte   -> Unused.









**
** ASYNC_DELETE:
**     iOffset -> Contains the "syncDir" flag.
**     nByte   -> Number of bytes of zBuf points to (file name).
**
** ASYNC_OPENEXCLUSIVE:
**     iOffset -> Value of "delflag".

  AsyncFileData *pFileData;    /* File to write data to or sync */
  int op;                      /* One of ASYNC_xxx etc. */
  i64 iOffset;        /* See above */
  int nByte;          /* See above */
  char *zBuf;         /* Data to write to file (or NULL if op!=ASYNC_WRITE) */
  AsyncWrite *pNext;  /* Next write operation (to any file) */
};

/*
** An instance of the following structure is allocated along with each
** AsyncFileData structure (see AsyncFileData.lock), but is only used if the
** file was opened with the SQLITE_OPEN_MAIN_DB.
**
** The global async.aLock[] hash table maps from database file-name to a
** linked-list of AsyncLock structures corresponding to handles opened on the
** file. The AsyncLock structures are linked into the list when the file is
** opened and removed when it is closed. Mutex async.lockMutex must be held
** before accessing any AsyncLock structure or the async.aLock[] table.
*/
typedef struct AsyncLock AsyncLock;
struct AsyncLock {
  int eLock;
  AsyncLock *pNext;
};

/* 
** The AsyncFile structure is a subclass of sqlite3_file used for 
** asynchronous IO. 
**
** All of the actual data for the structure is stored in the structure
** pointed to by AsyncFile.pData, which is allocated as part of the

  AsyncFileData *pData;
};
struct AsyncFileData {
  char *zName;               /* Underlying OS filename - used for debugging */
  int nName;                 /* Number of characters in zName */
  sqlite3_file *pBaseRead;   /* Read handle to the underlying Os file */
  sqlite3_file *pBaseWrite;  /* Write handle to the underlying Os file */
  AsyncLock lock;
};

/*
** Add an entry to the end of the global write-op list. pWrite should point 
** to an AsyncWrite structure allocated using sqlite3_malloc().  The writer
** thread will call sqlite3_free() to free the structure after the specified
** operation has been completed.

/*
** Close the file. This just adds an entry to the write-op list, the file is
** not actually closed.
*/
static int asyncClose(sqlite3_file *pFile){
  AsyncFileData *p = ((AsyncFile *)pFile)->pData;

  /* Unlock the file, if it is locked */
  pthread_mutex_lock(&async.lockMutex);
  p->lock.eLock = 0;
  pthread_mutex_unlock(&async.lockMutex);

  return addNewAsyncWrite(p, ASYNC_CLOSE, 0, 0, 0);
}

/*
** Implementation of sqlite3OsWrite() for asynchronous files. Instead of 
** writing to the underlying file, this function adds an entry to the end of
** the global AsyncWrite list. Either SQLITE_OK or SQLITE_NOMEM may be

      rc = sqlite3OsRead(pBase, zOut, nRead, iOffset);
      ASYNC_TRACE(("READ %s %d bytes at %d\n", p->zName, nRead, iOffset));
    }
  }

  if( rc==SQLITE_OK ){
    AsyncWrite *pWrite;
    char *zName = p->zName;

    for(pWrite=async.pQueueFirst; pWrite; pWrite = pWrite->pNext){
      if( pWrite->op==ASYNC_WRITE && pWrite->pFileData->zName==zName ){
        int iBeginOut = (pWrite->iOffset-iOffset);
        int iBeginIn = -iBeginOut;
        int nCopy;

        if( iBeginIn<0 ) iBeginIn = 0;
        if( iBeginOut<0 ) iBeginOut = 0;
        nCopy = MIN(pWrite->nByte-iBeginIn, iAmt-iBeginOut);

  if( pBase->pMethods ){
    rc = sqlite3OsFileSize(pBase, &s);
  }

  if( rc==SQLITE_OK ){
    AsyncWrite *pWrite;
    for(pWrite=async.pQueueFirst; pWrite; pWrite = pWrite->pNext){
      if( pWrite->op==ASYNC_DELETE && strcmp(p->zName, pWrite->zBuf)==0 ){
        s = 0;
      }else if( pWrite->pFileData && pWrite->pFileData->zName==p->zName){
        switch( pWrite->op ){
          case ASYNC_WRITE:
            s = MAX(pWrite->iOffset + (i64)(pWrite->nByte), s);
            break;
          case ASYNC_TRUNCATE:
            s = MIN(s, pWrite->iOffset);
            break;

** No disk locking is performed.  We keep track of locks locally in
** the async.aLock hash table.  Locking should appear to work the same
** as with standard (unmodified) SQLite as long as all connections 
** come from this one process.  Connections from external processes
** cannot see our internal hash table (obviously) and will thus not
** honor our locks.
*/
static int asyncLock(sqlite3_file *pFile, int eLock){
  int rc = SQLITE_OK;
  AsyncFileData *p = ((AsyncFile *)pFile)->pData;

  pthread_mutex_lock(&async.lockMutex);
  if( p->lock.eLock<eLock ){
    AsyncLock *pLock;
    pLock = (AsyncLock *)sqlite3HashFind(&async.aLock, p->zName, p->nName);
    assert(pLock);
    for(/*no-op*/; pLock; pLock=pLock->pNext){
      if( pLock!=&p->lock && (
        (eLock==SQLITE_LOCK_EXCLUSIVE && pLock->eLock>=SQLITE_LOCK_SHARED) ||
        (eLock==SQLITE_LOCK_PENDING && pLock->eLock>=SQLITE_LOCK_RESERVED) ||
        (eLock==SQLITE_LOCK_RESERVED && pLock->eLock>=SQLITE_LOCK_RESERVED) ||
        (eLock==SQLITE_LOCK_SHARED && pLock->eLock>=SQLITE_LOCK_PENDING)
      )){
        rc = SQLITE_BUSY;
      }
    }
    if( rc==SQLITE_OK ){
      p->lock.eLock = eLock;
    }
  }
  pthread_mutex_unlock(&async.lockMutex);

  ASYNC_TRACE(("LOCK %d (%s) rc=%d\n", eLock, p->zName, rc));
  return rc;
}
static int asyncUnlock(sqlite3_file *pFile, int eLock){
  AsyncFileData *p = ((AsyncFile *)pFile)->pData;
  AsyncLock *pLock = &p->lock;
  pthread_mutex_lock(&async.lockMutex);
  if( pLock->eLock>eLock ){
    pLock->eLock = eLock;
  }
  pthread_mutex_unlock(&async.lockMutex);
  return SQLITE_OK;
}




/*
** This function is called when the pager layer first opens a database file
** and is checking for a hot-journal.
*/
static int asyncCheckReservedLock(sqlite3_file *pFile){
  int ret = 0;
  AsyncLock *pLock;
  AsyncFileData *p = ((AsyncFile *)pFile)->pData;

  pthread_mutex_lock(&async.lockMutex);
  pLock = (AsyncLock *)sqlite3HashFind(&async.aLock, p->zName, p->nName);
  for(/*no-op*/; pLock; pLock=pLock->pNext){
    if( pLock->eLock>=SQLITE_LOCK_RESERVED ){
      ret = 1;
    }
  }
  pthread_mutex_unlock(&async.lockMutex);

  ASYNC_TRACE(("CHECK-LOCK %d (%s)\n", ret, p->zName));
  return ret;
}

/* 
** This is a no-op, as the asynchronous backend does not support locking.
*/
static int asyncFileControl(sqlite3_file *id, int op, void *pArg){
  return SQLITE_ERROR;

    asyncFileControl,                /* xFileControl */
    asyncSectorSize,                 /* xSectorSize */
    asyncDeviceCharacteristics       /* xDeviceCharacteristics */
  };

  sqlite3_vfs *pVfs = (sqlite3_vfs *)pAsyncVfs->pAppData;
  AsyncFile *p = (AsyncFile *)pFile;
  int nName = strlen(zName)+1;
  int rc;
  int nByte;
  AsyncFileData *pData;

  nByte = (
    sizeof(AsyncFileData) +        /* AsyncFileData structure */
    2 * pVfs->szOsFile +           /* AsyncFileData.pBaseRead and pBaseWrite */
    nName                          /* AsyncFileData.zName */
  ); 
  pData = sqlite3_malloc(nByte);
  if( !pData ){
    return SQLITE_NOMEM;
  }
  memset(pData, 0, nByte);
  pData->zName = (char *)&pData[1];
  pData->nName = nName;
  pData->pBaseRead = (sqlite3_file *)&pData->zName[nName];
  pData->pBaseWrite = (sqlite3_file *)&pData->zName[nName+pVfs->szOsFile];
  memcpy(pData->zName, zName, nName);

  if( flags&SQLITE_OPEN_EXCLUSIVE ){
    rc = addNewAsyncWrite(pData, ASYNC_OPENEXCLUSIVE, (i64)flags, 0, 0);
    if( pOutFlags ) *pOutFlags = flags;
  }else{
    rc = sqlite3OsOpen(pVfs, zName, pData->pBaseRead, flags, pOutFlags);
    if( rc==SQLITE_OK && ((*pOutFlags)&SQLITE_OPEN_READWRITE) ){
      rc = sqlite3OsOpen(pVfs, zName, pData->pBaseWrite, flags, 0);
    }
  }

  if( rc==SQLITE_OK ){
    HashElem *pElem;
    p->pMethod = &async_methods;
    p->pData = pData;
    incrOpenFileCount();

    /* Link AsyncFileData.lock into the linked list of AsyncLock structures
    ** for this file. Obtain the async.lockMutex mutex before doing so.
    */
    AsyncLock *pNext;
    pthread_mutex_lock(&async.lockMutex);
    pNext = sqlite3HashInsert(
        &async.aLock, pData->zName, pData->nName, (void *)&pData->lock
    );
    pData->lock.pNext = pNext;
    pElem = sqlite3HashFindElem(&async.aLock, pData->zName, pData->nName);
    pData->zName = (char *)sqliteHashKey(pElem);
    pthread_mutex_unlock(&async.lockMutex);
  }else{
    sqlite3OsClose(pData->pBaseRead);
    sqlite3OsClose(pData->pBaseWrite);
    sqlite3_free(pData);
  }

  return rc;

  return ret;
}

static int asyncGetTempName(sqlite3_vfs *pAsyncVfs, char *zBufOut){
  sqlite3_vfs *pVfs = (sqlite3_vfs *)pAsyncVfs->pAppData;
  return pVfs->xGetTempName(pVfs, zBufOut);
}

/*
** Fill in zPathOut with the full path to the file identified by zPath.
*/
static int asyncFullPathname(
  sqlite3_vfs *pAsyncVfs, 
  const char *zPath, 
  char *zPathOut
){
  int rc;
  sqlite3_vfs *pVfs = (sqlite3_vfs *)pAsyncVfs->pAppData;
  rc = sqlite3OsFullPathname(pVfs, zPath, zPathOut);

  /* Because of the way intra-process file locking works, this backend
  ** needs to return a canonical path. The following block assumes the
  ** file-system uses unix style paths. 
  */
  if( rc==SQLITE_OK ){
    int iIn;
    int iOut = 0;
    int nPathOut = strlen(zPathOut);

    for(iIn=0; iIn<nPathOut; iIn++){

      /* Replace any occurences of "//" with "/" */
      if( iIn<=(nPathOut-2) && zPathOut[iIn]=='/' && zPathOut[iIn+1]=='/'
      ){
        continue;
      }

      /* Replace any occurences of "/./" with "/" */
      if( iIn<=(nPathOut-3) 
       && zPathOut[iIn]=='/' && zPathOut[iIn+1]=='.' && zPathOut[iIn+2]=='/'
      ){
        iIn++;
        continue;
      }

      /* Replace any occurences of "<path-component>/../" with "" */
      if( iOut>0 && iIn<=(nPathOut-4) 
       && zPathOut[iIn]=='/' && zPathOut[iIn+1]=='.' 
       && zPathOut[iIn+2]=='.' && zPathOut[iIn+2]=='/'
      ){
        iIn += 3;
        iOut--;
        for( ; iOut>0 && zPathOut[iOut]!='/'; iOut--);
        continue;
      }

      zPathOut[iOut++] = zPathOut[iIn];
    }
    zPathOut[iOut] = '\0';
  }

  return rc;
}
static void *asyncDlOpen(sqlite3_vfs *pAsyncVfs, const char *zPath){
  sqlite3_vfs *pVfs = (sqlite3_vfs *)pAsyncVfs->pAppData;
  return pVfs->xDlOpen(pVfs, zPath);
}
static void asyncDlError(sqlite3_vfs *pAsyncVfs, int nByte, char *zErrMsg){
  sqlite3_vfs *pVfs = (sqlite3_vfs *)pAsyncVfs->pAppData;

      case ASYNC_TRUNCATE:
        assert( pBase );
        ASYNC_TRACE(("TRUNCATE %s to %d bytes\n", 
                p->pFileData->zName, p->iOffset));
        rc = sqlite3OsTruncate(pBase, p->iOffset);
        break;

      case ASYNC_CLOSE: {
        AsyncLock *pLock;
        AsyncFileData *pData = p->pFileData;
        ASYNC_TRACE(("CLOSE %s\n", p->pFileData->zName));
        sqlite3OsClose(pData->pBaseWrite);
        sqlite3OsClose(pData->pBaseRead);

        /* Unlink AsyncFileData.lock from the linked list of AsyncLock 
        ** structures for this file. Obtain the async.lockMutex mutex 
        ** before doing so.
        */
        pthread_mutex_lock(&async.lockMutex);
        pLock = sqlite3HashFind(&async.aLock, pData->zName, pData->nName);
        if( pLock==&pData->lock ){
          sqlite3HashInsert(
              &async.aLock, pData->zName, pData->nName, (void *)pLock->pNext 
          );
        }else{
          for( ; pLock && pLock->pNext!=&pData->lock; pLock=pLock->pNext);
          if( pLock ){
            pLock->pNext = pData->lock.pNext;
          }
        }
        pthread_mutex_unlock(&async.lockMutex);

        sqlite3_free(pData);
        break;
      }

      case ASYNC_DELETE:
        ASYNC_TRACE(("DELETE %s\n", p->zBuf));
        rc = sqlite3OsDelete(pVfs, p->zBuf, (int)p->iOffset);
        break;

      case ASYNC_OPENEXCLUSIVE: {

#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file runs all tests.
#
# $Id: async.test,v 1.8 2007/09/04 14:31:47 danielk1977 Exp $


if {[catch {sqlite3async_enable}]} {
  # The async logic is not built into this system
  return
}

  select2.test
  select3.test
  select4.test
  insert.test
  insert2.test
  insert3.test
  trans.test
  lock.test
  lock3.test
}


# Enable asynchronous IO.
sqlite3async_enable 1

rename do_test really_do_test
proc do_test {name args} {
  uplevel really_do_test async_io-$name $args