cqdb.c

CRFsuite is a very fast implmentation of the Conditional Random Fields (CRF) algorithm. It handles t

            }

            /*
                Put hash elements to the bucket with the open-address method.
             */
            for (j = 0;j < ht->num;++j) {
                const bucket_t* src = &ht->bucket[j];
                int k = (src->hash >> 8) % n;

                /* Find a vacant element. */
                while (dst[k].offset != 0) {
                    k = (k+1) % n;
                }

                /* Store the hash element. */
                dst[k].hash = src->hash;
                dst[k].offset = src->offset;
            }

            /* Write the bucket. */
            for (k = 0;k < n;++k) {
                write_uint32(dbw, dst[k].hash);
                write_uint32(dbw, dst[k].offset);
            }

            /* Free the bucket. */
            free(dst);
        }
    }

    /* Write the backlink array if specified. */
    if (!(dbw->flag & CQDB_ONEWAY) && 0 < dbw->bwd_size) {
        /* Store the offset to the head of this array. */
        header.bwd_offset = ftell(dbw->fp) - dbw->begin;
        /* Store the contents of the backlink array. */
        for (i = 0;i < dbw->bwd_num;++i) {
            write_uint32(dbw, dbw->bwd[i]);
        }
    }

    /* Check for an occurrence of a file-related error. */
    if (ferror(dbw->fp)) {
        ret = CQDB_ERROR_FILEWRITE;
        goto error_exit;
    }

    /* Store the current position. */
    offset = ftell(dbw->fp);
    if (offset == -1) {
        ret = CQDB_ERROR_FILETELL;
        goto error_exit;
    }
    header.size = (uint32_t)offset - dbw->begin;

    /* Rewind the current position to the beginning. */
    if (fseek(dbw->fp, dbw->begin, SEEK_SET) != 0) {
        ret = CQDB_ERROR_FILESEEK;
        goto error_exit;
    }

    /* Write the file header. */
    write_data(dbw, header.chunkid, 4);
    write_uint32(dbw, header.size);
    write_uint32(dbw, header.flag);
    write_uint32(dbw, header.byteorder);
    write_uint32(dbw, header.bwd_size);
    write_uint32(dbw, header.bwd_offset);

    /*
        Write references to hash tables. At this moment, dbw->cur points
        to the offset succeeding the last key/data pair. 
     */
    for (i = 0;i < NUM_TABLES;++i) {
        /* Offset to the hash table (or zero for non-existent tables). */
        write_uint32(dbw, dbw->ht[i].num ? dbw->cur : 0);
        /* Bucket size is double to the number of elements. */
        write_uint32(dbw, dbw->ht[i].num * 2);
        /* Advance the offset counter. */
        dbw->cur += (dbw->ht[i].num * 2) * sizeof(bucket_t);
    }

    /* Check an occurrence of a file-related error. */
    if (ferror(dbw->fp)) {
        ret = CQDB_ERROR_FILEWRITE;
        goto error_exit;
    }

    /* Seek to the last position. */
    if (fseek(dbw->fp, offset, SEEK_SET) != 0) {
        ret = CQDB_ERROR_FILESEEK;
        goto error_exit;
    }

    cqdb_writer_delete(dbw);
    return ret;

error_exit:
    /* Seek to the first position. */
    fseek(dbw->fp, dbw->begin, SEEK_SET);
    cqdb_writer_delete(dbw);
    return ret;
}



static uint32_t read_uint32(uint8_t* p)
{
    uint32_t value;
    value  = ((uint32_t)p[0]);
    value |= ((uint32_t)p[1] << 8);
    value |= ((uint32_t)p[2] << 16);
    value |= ((uint32_t)p[3] << 24);
    return value;
}

static uint8_t *read_tableref(tableref_t* ref, uint8_t *p)
{
    ref->offset = read_uint32(p);
    p += sizeof(uint32_t);
    ref->num = read_uint32(p);
    p += sizeof(uint32_t);
    return p;
}

static bucket_t* read_bucket(uint8_t* p, uint32_t num)
{
    uint32_t i;
    bucket_t *bucket = (bucket_t*)calloc(num, sizeof(bucket_t));
    for (i = 0;i < num;++i) {
        bucket[i].hash = read_uint32(p);
        p += sizeof(uint32_t);
        bucket[i].offset = read_uint32(p);
        p += sizeof(uint32_t);
    }
    return bucket;
}

static uint32_t* read_backward_links(uint8_t* p, uint32_t num)
{
    uint32_t i;
    uint32_t *bwd = (uint32_t*)calloc(num, sizeof(uint32_t));
    for (i = 0;i < num;++i) {
        bwd[i] = read_uint32(p);
        p += sizeof(uint32_t);
    }
    return bwd;
}

cqdb_t* cqdb_reader(void *buffer, size_t size)
{
    int i;
    cqdb_t* db = NULL;

    /* The minimum size of a valid CQDB is OFFSET_DATA. */
    if (size < OFFSET_DATA) {
        return NULL;
    }

    /* Check the file chunkid. */
    if (memcmp(buffer, CHUNKID, 4) != 0) {
        return NULL;
    }
    
    db = (cqdb_t*)calloc(1, sizeof(cqdb_t));
    if (db != NULL) {
        uint8_t* p = NULL;

        /* Set memory block and size. */
        db->buffer = buffer;
        db->size = size;

        /* Read the database header. */
        p = db->buffer;
        strncpy((char*)db->header.chunkid, (const char*)p, 4);
        p += sizeof(uint32_t);
        db->header.size = read_uint32(p);
        p += sizeof(uint32_t);
        db->header.flag = read_uint32(p);
        p += sizeof(uint32_t);
        db->header.byteorder = read_uint32(p);
        p += sizeof(uint32_t);
        db->header.bwd_size = read_uint32(p);
        p += sizeof(uint32_t);
        db->header.bwd_offset = read_uint32(p);
        p += sizeof(uint32_t);

        /* Check the consistency of byte order. */
        if (db->header.byteorder != BYTEORDER_CHECK) {
            free(db);
            return NULL;
        }

        /* Check the chunk size. */
        if (size < db->header.size) {
            free(db);
            return NULL;
        }

        /* Set pointers to the hash tables. */
        db->num = 0;    /* Number of records. */
        p = (db->buffer + OFFSET_REFS);
        for (i = 0;i < NUM_TABLES;++i) {
            tableref_t ref;
            p = read_tableref(&ref, p);
            if (ref.offset) {
                /* Set buckets. */
                db->ht[i].bucket = read_bucket(db->buffer + ref.offset, ref.num);
                db->ht[i].num = ref.num;
            } else {
                /* An empty hash table. */
                db->ht[i].bucket = NULL;
                db->ht[i].num = 0;
            }

            /* The number of records is the half of the table size.*/
            db->num += ref.num / 2;
        }

        /* Set the pointer to the backlink array if any. */
        if (db->header.bwd_offset) {
            db->bwd = read_backward_links(db->buffer + db->header.bwd_offset, db->num);
        } else {
            db->bwd = NULL;
        }
    }

    return db;
}

void cqdb_delete(cqdb_t* db)
{
    int i;

    if (db != NULL) {
        for (i = 0;i < NUM_TABLES;++i) {
            free(db->ht[i].bucket);
        }
        free(db->bwd);
        free(db);
    }
}

int cqdb_to_id(cqdb_t* db, const char *str)
{
    uint32_t hv = hashlittle(str, strlen(str)+1, 0);
    int t = hv % 256;
    table_t* ht = &db->ht[t];

    if (ht->num && ht->bucket != NULL) {
        int n = ht->num;
        int k = (hv >> 8) % n;
        bucket_t* p = NULL;

        while (p = &ht->bucket[k], p->offset) {
            if (p->hash == hv) {
                int value;
                uint32_t ksize;
                uint8_t *q = db->buffer + p->offset;
                value = (int)read_uint32(q);
                q += sizeof(uint32_t);
                ksize = read_uint32(q);
                q += sizeof(uint32_t);
                if (strcmp(str, (const char *)q) == 0) {
                    return value;
                }
            }
            k = (k+1) % n;
        }
    }

    return CQDB_ERROR_NOTFOUND;
}

const char* cqdb_to_string(cqdb_t* db, int id)
{
    /* Check if the current database supports the backward look-up. */
    if (db->bwd != NULL && (uint32_t)id < db->header.bwd_size) {
        uint32_t offset = db->bwd[id];
        if (offset) {
            uint8_t *p = db->buffer + offset;
            p += sizeof(uint32_t);  /* Skip key data. */
            p += sizeof(uint32_t);  /* Skip value size. */
            return (const char *)p;
        }
    }

    return NULL;
}

int cqdb_num(cqdb_t* db)
{
    return db->num;
}