qwsdatabase.cpp

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

/**********************************************************************
** Copyright (C) 2000-2005 Trolltech AS.  All rights reserved.
**
** This file is part of the Qtopia Environment.
** 
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** A copy of the GNU GPL license version 2 is included in this package as 
** LICENSE.GPL.
**
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
** See the GNU General Public License for more details.
**
** In addition, as a special exception Trolltech gives permission to link
** the code of this program with Qtopia applications copyrighted, developed
** and distributed by Trolltech under the terms of the Qtopia Personal Use
** License Agreement. You must comply with the GNU General Public License
** in all respects for all of the code used other than the applications
** licensed under the Qtopia Personal Use License Agreement. If you modify
** this file, you may extend this exception to your version of the file,
** but you are not obligated to do so. If you do not wish to do so, delete
** this exception statement from your version.
** 
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact [e-mail] if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/
#include "qwsdatabase_p.h"

#include <qtopia/global.h>

#include <qlist.h>
#include <qmap.h>
#include <qfile.h>
#include <qdatastream.h>
#include <qmessagebox.h>

#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <errno.h>

/* TODO
   * Use more efficient data structures, e.g. QMap for the sort order could be
     considered overkill.
   * more complete performance tests.
*/

const QWSDatabaseOrderedSelection* comparisonidx;

// Normal bsearch(), but returns the element to insert before
// in order to maintain sorting. Only returns NULL if must append.
static void* bsearch2(const void *key, const void *base, size_t nmemb,
              size_t size, int (*compar)(const void *, const void *))
{
    size_t l, u, idx;
    const void *p=0;
    int comparison=0;

    l = 0;
    u = nmemb;
    while (l < u)
    {
	idx = (l + u) / 2;
	p = (void*) (((const char *) base) + (idx * size));
	comparison = (*compar)(key, p);
	if (comparison < 0)
	    u = idx;
	else if (comparison > 0)
	    l = idx + 1;
	else
	    return (void*) p;
    }

    if ( comparison > 0) {
	if ( l == nmemb )
	    return 0;
	else
	    return (void*)((char*)p+size);
    } else {
	return (void*)p;
    }
}

class RecordWithPos {
public:
    RecordWithPos(const QByteArray& r, int p=-1) : record(r), pos(p) {}

    const QByteArray& record;
    int pos;
};


QWSDatabaseIndex::QWSDatabaseIndex(const QString& indname, QWSDatabase* d) :
    QObject(d),
    db(d)
{
    dirty = FALSE;
    idxfile = new QFile(Global::applicationFileName("Database", db->databaseName() + "." + indname + ".idx")); // No tr
    if (idxfile->open(IO_ReadWrite)) {
	if ( idxfile->size() == 0 ) {
	    setDirty( TRUE ); 
	}
    }
    db->addIndex(this);
}

QWSDatabaseOrderedSelection::QWSDatabaseOrderedSelection(const QString& indname, QWSDatabase* d) :
    QWSDatabaseIndex(indname,d),
    capacity(64), n(0)
{
    index = (uint *)malloc(sizeof(uint) * capacity);

    if ( isDirty() ) {
	reindex();
    } else {
	uint c = 0;
	idxfile->flush();
	idxfile->at(0);
	QDataStream ds(idxfile);
	ds >> c; // dirty flag
	if ( c != 0x0 ) {
	    qDebug("index dirty!!!");
	    reindex();
	    setDirty( TRUE );
	} else {
	    ds >> c;
	    resize(c);

	    int pb = 0;
	    while(c-- > 0) {
		uint current = 0;
		int pos = idxfile->at();
		ds >> current;
		index[pb] = current;
		pb++;
	    }
	}
    }
}

void QWSDatabaseIndex::setDirty( bool d )
{
    if( dirty != d && idxfile->isOpen() ) {
	int pos = idxfile->at();
	idxfile->at( 0 );
	QDataStream ds( idxfile );
	uint invalid = 0xffffffff;
	ds << (int) (d ? invalid : 0x0);
	idxfile->flush();
	idxfile->at(pos);
    }
    dirty = d;
}


QWSDatabaseIndex::~QWSDatabaseIndex()
{
    flushIndex();
    setDirty( FALSE );
    if ( idxfile->isOpen() ) {
	idxfile->close();
    }
    db->removeIndex(this);
}

QWSDatabaseOrderedSelection::~QWSDatabaseOrderedSelection()
{
    flushIndex();
    free(index);
}

bool QWSDatabaseIndex::flushIndex()
{
    if ( !isDirty() )
	return FALSE;
    if ( idxfile->isOpen() )
	idxfile->close();
    idxfile->open(IO_WriteOnly);
    setDirty( TRUE );
    return TRUE;
}

bool QWSDatabaseOrderedSelection::flushIndex()
{
    if ( !QWSDatabaseIndex::flushIndex() )
	return FALSE;

    idxfile->at( 4 ); // skip dirty flag
    QDataStream ds(idxfile);

    ds << n;

    for(uint i = 0; i < n; i++) {
	ds << position(i);
    }
    setDirty( FALSE );

    return TRUE;
}

void QWSDatabaseOrderedSelection::resize(uint newsize)
{
    /* powers of two, later swap *=,/= for shifts. */
    uint c = capacity;
    n = newsize;
    if (newsize > 64) {
	while (newsize > c) 
	    c *= 2;

	/* the shrink test */
	uint doublenew = newsize * 2;
	while (doublenew < c)
	    c /= 2;

	if (c != capacity) {
	    /* we need to resize and memcpy */

	    uint* ind = (uint *)malloc(sizeof(uint) * c);
	    if (!ind) {
		qWarning("could not allocate memory for index");
		return;
	    }
	    if(index) {
		if (c > capacity) 
		    memcpy(ind, index, capacity * sizeof(uint));
		else 
		    memcpy(ind, index, c * sizeof(uint));
		free(index);
	    }
	    capacity = c;
	    index = ind;
	}
    }
}

int QWSDatabaseOrderedSelection::count() const
{
    return n;
}

QByteArray QWSDatabaseOrderedSelection::at(uint r) const
{
    return db->atOffset(position(r));
}

int QWSDatabaseOrderedSelection::find(const QByteArray &r, uint pos) const 
{
    comparisonidx = this;
    RecordWithPos rp(r,pos);
    const uint* p = (const uint*)bsearch(&rp, index, n, sizeof(*index), externKeyCompare);
    comparisonidx = 0;
    return p ? p-index : -1;
}


uint QWSDatabaseOrderedSelection::position(uint pos) const
{
    if (pos >= n)
	return 0;
    return index[pos];
}

void QWSDatabaseOrderedSelection::replace(uint pos, uint value) 
{
    if (pos >= n)
	return ;
    index[pos] = value;
    setDirty( TRUE );
}

bool QWSDatabaseOrderedSelection::removeAt(uint r)
{
    if (r >= n)
	return FALSE;
    int pos = index[r];
    // removeDirect(r); - can't since we want to see it in remove(r,pos)
    db->removeRecordAt(pos,0); // can't skip, we want to see it
    return TRUE;
}

void QWSDatabaseOrderedSelection::removeDirect(uint r)
{
    setDirty( TRUE );
    // + 1 as because although it is valid, it does not affect the memmove
    if (r + 1 != n) {
	memmove(index + r,
		index + (r + 1),
		(n - (r + 1)) * sizeof(uint));
    }

    resize(n-1);
}

void QWSDatabaseOrderedSelection::remove(const QByteArray& r, uint pos)
{
    if ( select(r,FALSE) ) {
	int i=find(r,pos);
	if ( i>=0 )
	    removeDirect(i);
    }
}

int QWSDatabaseOrderedSelection::add(const QByteArray& r)
{
    last = -1;
    db->add(r);
    return last;
}

void QWSDatabaseOrderedSelection::insert(const QByteArray& r, uint pos)
{
    if ( select(r,TRUE) ) {
	resize(n+1);
	comparisonidx = this;
	RecordWithPos rp(r,pos);
	uint* p = (uint*)bsearch2(&rp, index, n-1, sizeof(*index), externKeyCompare);
	comparisonidx = 0;
	if ( p ) {
	    int i = p-index;
	    memmove(index + i + 1, index + i, (n - i - 1) * sizeof(uint));
	    index[last=i] = pos;
	} else {
	    index[last=n-1] = pos;
	}
	setDirty( TRUE );
    }
}

void QWSDatabaseOrderedSelection::insertDirect(const QByteArray& r, uint pos)
{
    if ( select(r,TRUE) ) {
	resize(n+1);
	index[n-1] = pos;
    }
}

void QWSDatabaseOrderedSelection::reindex()
{
    qDebug("reindexing");
    n = 0;
    db->reinsertDirect(this);
    comparisonidx = this;
    qsort(index, n, sizeof(uint), externCompare);
    comparisonidx = 0;
    setDirty( TRUE );
}

int QWSDatabaseOrderedSelection::externCompare(const void *a, const void*b)
{
    return comparisonidx->compare(a, b);
}

int QWSDatabaseOrderedSelection::externKeyCompare(const void *a, const void*b)
{
    return comparisonidx->compareKey(a, b);
}

struct FreeList {
    uint size;
    uint start;
    uint count;
};

static const uint number_lists = 4;
static const uint smallest_list = 32;

class QWSDatabasePrivate
{
public:
    QWSDatabasePrivate() : indexed(TRUE)
    { 
	keys.setAutoDelete(TRUE);

	// initialize the free lists.
	for (uint i = 0; i < number_lists; i++) 
	{
	    freelists[i].size = smallest_list << i;
	    freelists[i].start = 0;
	    freelists[i].count = 0;
	}
    }

    ~QWSDatabasePrivate() 
    {
    }

    uint dbend;

    bool indexed;

    void indexify(const QByteArray& r, uint pos)
    {
	if ( indexed ) {
	    QWSDatabaseIndex* idx;
	    for (QListIterator<QWSDatabaseIndex> it(indices); (idx=it.current()); ++it)
		idx->insert(r,pos);
	}
    }

    void unindexify(uint pos, QWSDatabaseIndex* skip, QWSDatabase* db)
    {
	// remove from all indexes except "skip".

	if ( indexed ) {
	    if ( indices.count() &&
		    (!skip || indices.count() != 1 || skip != indices.first()) )
	    {
		QByteArray r = db->atOffset(pos);
		QWSDatabaseIndex* idx;
		for (QListIterator<QWSDatabaseIndex> it(indices); (idx=it.current()); ++it)
		    if ( idx != skip )
			idx->remove(r,pos);
	    }
	}
    }

    void reindex()
    {
	if (indexed) {
	    QWSDatabaseIndex* idx;
	    for (QListIterator<QWSDatabaseIndex> it(indices); (idx=it.current()); ++it)
		idx->reindex();
	}
    }

    QIntDict<QString> keys;

    QList<QWSDatabaseIndex> indices;

    FreeList freelists[number_lists];
};

bool QWSDatabaseOrderedSelection::select(const QByteArray&, bool)
{
    return TRUE;
}

int QWSDatabaseOrderedSelection::compare(const QByteArray&, const QByteArray&) const
{
    return 0;
}

int QWSDatabaseOrderedSelection::compare(const void *a, const void *b) const
{
    const uint pa = *((uint *)a);
    const uint pb = *((uint *)b);
    QByteArray first = db->atOffset(pa);
    QByteArray second = db->atOffset(pb);
    int o = compare(first,second);
    if ( o ) return o;
    return pa-pb;
}

int QWSDatabaseOrderedSelection::compareKey(const void *a, const void *b) const
{
    RecordWithPos* key = (RecordWithPos*)a;
    int pos = *(int *)b;
    QByteArray value = db->atOffset(pos);
    int order = compare(key->record, value);
    if ( !order && key->pos != -1 )
	return key->pos-pos;
    return order;
}


const unsigned char type_invalid = 0xff; // this file is wrecked, 
					 // any data past this point is
					 // suspect.
const unsigned char type_unknown = 0xfe; // the size field following is
					 // correct, but the data 
					 // stored is indeterminate.

const unsigned char type_record = 0x01;  // this is a record
const unsigned char type_free = 0x02;    // this is an element of a free
					 // list (during regen, ignore the
				 	 // next pointer).

/*!
  \internal
  \class QWSDatabase
  \brief The Database class keeps an unordered list of Record on disk.

  The Database class keeps an unordered list of Records on disk.  It 
  also ensure file consistency in the face of both sudden killing of the 
  program and the possiblity of running out of disk space.  There is a 
  moderate attempt to keep space wastage down but it is not very aggressive 
  in reclaiming lost space.

  Records placed in the database a written and flushed to disk before the
  database returns.  If for whatever reason the operation fails, it should
  alter the accessability of the remaining data.  

  Also if there is a gap in the Database big enough to accomidate the added 
  data, then the data will be inserted into this gap rather than at the end 
  of the file.
*/
QWSDatabase::QWSDatabase(const QString& nm, QObject* parent, const char* name) :
    QObject(parent, name)
{
    dbname = nm;
    QString base = Global::applicationFileName("Database", nm); // No tr
    dbfile = new QFile(base + ".dat");
    hdrfile = new QFile(base + ".hdr");

    d = 0;

    if (!dbfile->open(IO_ReadWrite)) {
	return;
    }
    dbfile->at(0);
    if (dbfile->size() == 0) {
	dirty = 0;
	if (!writeUint(dirty)) {
	    // couln't even write 4 bytes
	    while (recoverableError() == 0) {
		if (writeUint(dirty))
		    break;
	    }
	}
    } else {
	dirty = readUint();
    }

    d = new QWSDatabasePrivate;

    if (!readHeader()) {
	// we don't have enough info to continue, TODO
    }
}

QWSDatabase::~QWSDatabase()
{
    dbfile->close();
    writeHeader();

    if (d)
	delete d;
}

/*!
  Adds \a r to the database, and if currently index, also inserts it
  into any active indexes.
  */
void QWSDatabase::add(const QByteArray& r) 
{
    if (!d)
	return;
    
    uint index = writeRecord(r);
    if (index)
	d->indexify(r,index);
}

/*! 
  Scans the database for valid records, and for each valid record inserts
  it into the index \a i.
  */ 
void QWSDatabase::reinsertDirect(QWSDatabaseIndex* i)
{
    recover(i, FALSE, FALSE);
}

/*! 
  Scans the database, and tries to reconstruct records, freelists, and
  file integrity.  Unless diskspace runs out or the process is killed 
  the will be no uknown or invalid records remaining when this function 
  completes.
 */
void QWSDatabase::recover(QWSDatabaseIndex* i, 
	bool recoverFreeLists, bool truncate)
{
    uint offset = sizeof(uint);
    bool stillErrors = FALSE;
    dbfile->at(offset);

    if (recoverFreeLists) {
	for (uint ind = 0; ind < number_lists; ind++) {
	    d->freelists[ind].start = 0;
	    d->freelists[ind].count = 0;
	}