lib/libnisdb/db_index.cc

	db_index.cc revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 *  db_index.cc
 *
 *  Copyright 1988-2002 Sun Microsystems, Inc.  All rights reserved.
 *  Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

#include <stdio.h>
#include <malloc.h>
#include "db_headers.h"
#include "db_index.h"
#include "db_pickle.h"

#include "nisdb_mt.h"
#include "nisdb_rw.h"

static int hashsizes[] = {      /* hashtable sizes */
    11,
    113,
    337,
    977,
    2053,
    4073,
    8011,
    16001,
    0
};

// prevents wrap around numbers from being passed
#define CALLOC_LIMIT 536870911

/* Constructor: creates empty index. */
db_index::db_index()
{
    tab = NULL;
    table_size = 0;
    count = 0;
    case_insens = FALSE;
    INITRW(index);
/*  grow(); */
}


/* Destructor: deletes index, including all associated db_index_entry. */
db_index::~db_index()
{
    WRITELOCKV(this, "w db_index::~db_index");
    reset();
    DESTROYRW(index);
}

/* Get rid of table and all associated entries, and reset counters */
void
db_index::reset()
{
    db_index_entry * curr, *n;
    int i;

    WRITELOCKV(this, "w db_index::reset");
    /* Add sanity test in case table was corrupted */
    if (tab != NULL) {
        for (i = 0; i < table_size; i++) {  // go through table
            curr = tab[i];
            while (curr != NULL) {      // go through bucket
                n = curr->getnextentry();
                delete curr;
                curr = n;
            }
        }
    }

    delete tab;             // get rid of table itself

    tab = NULL;
    table_size = count = 0;
    WRITEUNLOCKV(this, "wu db_index::reset");
}


/*
 * Initialize index according to the specification of the key descriptor
 * Currently, only affects case_insens flag of index.
 */
void
db_index::init(db_key_desc * k)
{
    WRITELOCKV(this, "w db_index::init");
    if ((k->key_flags)&DB_KEY_CASE)
        case_insens = TRUE;
    WRITEUNLOCKV(this, "wu db_index::init");
}

/* Returns the next size to use for the hash table */
static long unsigned
get_next_hashsize(long unsigned oldsize)
{
    long unsigned newsize = 0, n;
    if (oldsize == 0)
        newsize = hashsizes[0];
    else {
        for (n = 0; newsize = hashsizes[n++]; )
            if (oldsize == newsize) {
                newsize = hashsizes[n]; /* get next size */
                break;
            }
        if (newsize == 0)
            newsize = oldsize * 2 + 1;  /* just double */
    }
    return (newsize);
}

/*
 * Grow the current hashtable upto the next size.
 *    The contents of the existing hashtable is copied to the new one and
 *    relocated according to its hashvalue relative to the new size.
 *    Old table is deleted after the relocation.
 */
void
db_index::grow()
{
    long unsigned oldsize = table_size, i;
    db_index_entry_p * oldtab = tab;

    WRITELOCKV(this, "w db_index::grow");
    table_size = get_next_hashsize(table_size);

#ifdef DEBUG
    if (debug > 3)
        fprintf(ddt, "savehash GROWING to %d\n", table_size);
#endif

    if (table_size > CALLOC_LIMIT) {
        table_size = oldsize;
        WRITEUNLOCKV(this,
            "wu db_index::grow: table size exceeds calloc limit");
        FATAL("db_index::grow: table size exceeds calloc limit",
            DB_MEMORY_LIMIT);
    }

    if ((tab = (db_index_entry_p*)
        calloc((unsigned int) table_size,
            sizeof (db_index_entry_p))) == NULL) {
        tab = oldtab;       // restore previous table info
        table_size = oldsize;
        WRITEUNLOCKV(this,
            "wu db_index::grow: cannot allocate space");
        FATAL("db_index::grow: cannot allocate space", DB_MEMORY_LIMIT);
    }

    if (oldtab != NULL) {       // must transfer contents of old to new
        for (i = 0; i < oldsize; i++) {
            oldtab[i]->relocate(tab, table_size);
        }
        delete oldtab;      // delete old hashtable
    }
    WRITEUNLOCKV(this, "wu db_index::grow");
}

/*
 * Look up given index value in hashtable.
 * Return pointer to db_index_entries that match the given value, linked
 * via the 'next_result' pointer.  Return in 'how_many_found' the size
 * of this list. Return NULL if not found.
 */
db_index_entry *
db_index::lookup(item *index_value, long *how_many_found,
        db_table *table, bool_t checkTTL)
{
    register unsigned long hval;
    unsigned long bucket;
    db_index_entry  *ret;

    READLOCK(this, NULL, "r db_index::lookup");
    if (index_value == NULL || table_size == 0 || tab == NULL) {
        READUNLOCK(this, NULL, "ru db_index::lookup");
        return (NULL);
    }
    hval = index_value->get_hashval(case_insens);
    bucket = hval % table_size;

    db_index_entry_p fst = tab[bucket ];

    if (fst != NULL)
        ret = fst->lookup(case_insens, hval,
                    index_value, how_many_found);
    else
        ret = NULL;

    if (ret != NULL && checkTTL && table != NULL) {
        if (!table->cacheValid(ret->getlocation()))
            ret = NULL;
    }

    READUNLOCK(this, ret, "ru db_index::lookup");
    return (ret);
}

/*
 * Remove the entry with the given index value and location 'recnum'.
 * If successful, return DB_SUCCESS; otherwise DB_NOTUNIQUE if index_value
 * is null; DB_NOTFOUND if entry is not found.
 * If successful, decrement count of number of entries in hash table.
 */
db_status
db_index::remove(item* index_value, entryp recnum)
{
    register unsigned long hval;
    unsigned long bucket;
    register db_index_entry *fst;
    db_status   ret;

    if (index_value == NULL)
        return (DB_NOTUNIQUE);
    WRITELOCK(this, DB_LOCK_ERROR, "w db_index::remove");
    if (table_size == 0 || tab == NULL) {
        WRITEUNLOCK(this, DB_NOTFOUND, "wu db_index::remove");
        return (DB_NOTFOUND);
    }
    hval = index_value->get_hashval(case_insens);

    bucket = hval % table_size;

    fst = tab[bucket];
    if (fst == NULL)
        ret = DB_NOTFOUND;
    else if (fst->remove(&tab[bucket], case_insens, hval, index_value,
            recnum)) {
        --count;
        ret = DB_SUCCESS;
    } else
        ret = DB_NOTFOUND;
    WRITEUNLOCK(this, ret, "wu db_index::remove");
    return (ret);
}

/*
 * Add a new index entry with the given index value and location 'recnum'.
 * Return DB_NOTUNIQUE, if entry with identical index_value and recnum
 * already exists.  If entry is added, return DB_SUCCESS.
 * Increment count of number of entries in index table and grow table
 * if number of entries equals size of table.
 * Note that a copy of index_value is made for new entry.
 */
db_status
db_index::add(item* index_value, entryp recnum)
{
    register unsigned long hval;

    if (index_value == NULL)
        return (DB_NOTUNIQUE);

    hval = index_value->get_hashval(case_insens);

    WRITELOCK(this, DB_LOCK_ERROR, "w db_index::add");
    if (tab == NULL) grow();

    db_index_entry_p fst, newbucket;
    unsigned long bucket;
    bucket = hval %table_size;
    fst = tab[bucket];
    if (fst == NULL)  { /* Empty bucket */
        if ((newbucket = new db_index_entry(hval, index_value,
                recnum, tab[bucket])) == NULL) {
            WRITEUNLOCK(this, DB_MEMORY_LIMIT,
                "wu db_index::add");
            FATAL3("db_index::add: cannot allocate space",
                DB_MEMORY_LIMIT, DB_MEMORY_LIMIT);
        }
        tab[bucket] = newbucket;
    } else if (fst->add(&tab[bucket], case_insens,
                hval, index_value, recnum)) {
        /* do nothing */
    } else {
        WRITEUNLOCK(this, DB_NOTUNIQUE, "wu db_index::add");
        return (DB_NOTUNIQUE);
    }

    /* increase hash table size if number of entries equals table size */
    if (++count > table_size)
        grow();

    WRITEUNLOCK(this, DB_SUCCESS, "wu db_index::add");
    return (DB_SUCCESS);
}

/* ************************* pickle_index ********************* */

/* Does the actual writing to/from file specific for db_index structure. */
static bool_t
transfer_aux(XDR* x, pptr ip)
{
    return (xdr_db_index(x, (db_index*) ip));
}

class pickle_index: public pickle_file {
    public:
    pickle_index(char *f, pickle_mode m) : pickle_file(f, m) {}

    /* Transfers db_index structure pointed to by dp to/from file. */
    int transfer(db_index* dp)
        { return (pickle_file::transfer((pptr) dp, &transfer_aux)); }
};

/* Dumps this index to named file. */
int
db_index::dump(char *file)
{
    int ret;
    pickle_index f(file, PICKLE_WRITE);

    WRITELOCK(this, -1, "w db_index::dump");
    int status =  f.transfer(this);

    if (status == 1)
        ret = -1; /* cannot open for write */
    else
        ret = status;
    WRITEUNLOCK(this, ret, "wu db_index::dump");
}

/*
 * Constructor: creates index by loading it from the specified file.
 * If loading fails, creates empty index.
 */
db_index::db_index(char *file)
{
    pickle_index f(file, PICKLE_READ);
    tab = NULL;
    table_size = count = 0;

    /* load new hashbuf */
    if (f.transfer(this) < 0) {
        /* Load failed; reset. */
        tab = NULL;
        table_size = count = 0;
    }

    INITRW(index);
}


/*
 * Return in 'tsize' the table_size, and 'tcount' the number of entries
 * in the table.
 */
void
db_index::stats(long *tsize, long *tcount)
{
    READLOCKV(this, "r db_index::stats");
    *tsize = table_size;
    *tcount = count;
    READUNLOCKV(this, "ru db_index::stats");
}

/* Print all entries in the table. */
void
db_index::print()
{
    long i;

    READLOCKV(this, "r db_index::print");
    /* Add sanity check in case table corrupted */
    if (tab != NULL) {
        for (i = 0; i < table_size; i++) {
            if (tab[i] != NULL)
                tab[i]->print_all();
        }
    }
    READUNLOCKV(this, "ru db_index::print");
}

/*
 * Moves an index from an xdr index. Upon completion, original index's tab
 * will be NULL.
 */

db_status
db_index::move_xdr_db_index(db_index *orig)
{
    table_size = orig->table_size;
    orig->table_size = 0;
    count = orig->count;
    orig->count = 0;
    case_insens = orig->case_insens;
    tab = orig->tab;
    orig->tab = NULL;

    return (DB_SUCCESS);
}