Backed out changeset e05f5705283d (wrong name)

[unleashed.git] / usr / src / cmd / nscd / nscd_dbimpl.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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
 */
/*
 * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "nscd_db.h"

/*
 * This file implements the database functionality used by the
 * switch and configuration components. The implementation is
 * based on hash and has table. If the need arises in the future,
 * the code in this file can be changed to use other algorithms.
 * The following lists the functions implemented:
 *
 * _nscd_add_db_entry
 * _nscd_delete_db_entry
 * _nscd_get_db_entry
 * _nscd_alloc_db
 * _nscd_free_db
 * _nscd_walk_db
 * _nscd_delete_db_entry_cookie
 */

/*
 * This structure defines an instance of the hash entry
 * which implements the nscd database entry. The
 * db_entry field should always be the first one in
 * the structure.
 */
typedef struct nscd_hash {
        nscd_db_entry_t         db_entry;
        struct nscd_hash        *next_p;
        struct nscd_hash        *prev_p;
} nscd_hash_t;

/*
 * This structure defines a nscd database which
 * is implemented as an array of nscd_hash_t.
 */
struct nscd_db_s {
        int             array_size; /* number of elements in hash_tbl_p */
        nscd_hash_t     **hash_tbl_p;
};

/*
 * This cookie structure is used to iterate through the
 * database entries contained in a nscd database.
 */
struct cookie {
        int             idx;    /* the current bucket */
        nscd_hash_t     *hash;  /* the current hash entry */
        nscd_db_t       *db;    /* the database */
};

/*
 * FUNCTION: calc_hash
 *
 * Calculate a hash for a string based on the elf_hash
 * algorithm, hash is case insensitive. Uses tolower
 * instead of _tolower because of I18N.
 */
static unsigned long
calc_hash(
        const char      *str)
{
        unsigned int    hval = 0;
        char            ch;

        while (*str != NULL) {
                unsigned int    g;

                ch = (char)*str++;
                if (isupper(ch))
                        ch = _tolower(ch);
                hval = (hval << 4) + ch;
                if ((g = (hval & 0xf0000000)) != 0)
                        hval ^= g >> 24;
                hval &= ~g;
        }
        return ((unsigned long)hval);
}

/*
 * FUNCTION: scan_hash
 *
 * Scan a hash table for a matching hash entry. Assume 'str' is
 * not NULL. If option is NSCD_GET_NEXT_DB_ENTRY and id_num
 * is less than zero, then treats the option as NSCD_GET_FIRST_DB_ENTRY.
 */

static const nscd_hash_t *
scan_hash(
        int                     type,
        const char              *str,
        const nscd_hash_t       *idx_p,
        nscd_db_option_t        option,
        int                     id_num)
{
        int                     id_matched = 0;
        nscd_db_entry_t         *db_entry;

        while (idx_p != NULL) {
                db_entry = &((nscd_hash_t *)idx_p)->db_entry;
                if (db_entry->type == type) {
                        if (strcasecmp(str, db_entry->name) == 0) {
                                switch (option) {
                                case NSCD_GET_FIRST_DB_ENTRY:
                                        return (idx_p);
                                case NSCD_GET_EXACT_DB_ENTRY:
                                        if (id_num == db_entry->id_num)
                                                return (idx_p);
                                        break;
                                case NSCD_GET_NEXT_DB_ENTRY:
                                        if (id_num < 0)
                                                return (idx_p);
                                        if (id_matched == 1)
                                                return (idx_p);
                                        if (id_num == db_entry->id_num)
                                                id_matched = 1;
                                        break;
                                }
                        }
                }
                idx_p = idx_p->next_p;
        }
        return (NULL);
}

/*
 * FUNCTION: _nscd_get_db_entry
 *
 * Find a nscd database entry from a nscd database.
 */
const nscd_db_entry_t *
_nscd_get_db_entry(
        const nscd_db_t         *db,
        int                     type,
        const char              *str,
        nscd_db_option_t        option,
        int                     id_num)
{
        unsigned long           hash;
        const nscd_hash_t       *idx_p, *hash_p;

        if (db == NULL || str == NULL)
                return (NULL);

        hash = calc_hash(str);
        idx_p = db->hash_tbl_p[hash % db->array_size];

        hash_p = scan_hash(type, str, idx_p, option, id_num);

        return (&hash_p->db_entry);
}

/*
 * FUNCTION: _nscd_add_db_entry
 *
 * Add a nscd database entry to a nscd database. This function
 * is not MT safe. The caller should lock the database to
 * prevent concurrent updates done by other threads.
 */
nscd_rc_t
_nscd_add_db_entry(
        nscd_db_t               *db,
        const char              *str,
        nscd_db_entry_t         *entry,
        nscd_db_option_t        option)
{
        int                     i;
        unsigned long           hash;
        nscd_hash_t             *next_p = NULL, *prev_p = NULL;
        nscd_hash_t             *idx_p, *hash_entry;
        nscd_db_entry_t         *db_entry;

        /* find the bucket */
        hash = calc_hash(str);
        i = hash % db->array_size;
        idx_p = db->hash_tbl_p[i];

        /* can not replace nothing */
        if (idx_p == NULL)
                if (option == NSCD_ADD_DB_ENTRY_REPLACE)
                        return (NSCD_DB_ENTRY_NOT_FOUND);

        while (idx_p != NULL) {
                db_entry = &idx_p->db_entry;
                switch (option) {

                case NSCD_ADD_DB_ENTRY_FIRST:
                        next_p = idx_p;
                        goto add_entry;

                case NSCD_ADD_DB_ENTRY_REPLACE:
                        if (db_entry->type != entry->type)
                                goto cont;
                        if (strcasecmp(db_entry->name, str) != 0)
                                goto cont;

                        if (db_entry->id_num == entry->id_num) {
                                prev_p = idx_p->prev_p;
                                next_p = idx_p->next_p;
                                free(idx_p);
                                goto add_entry;
                        }
                        goto cont;

                case NSCD_ADD_DB_ENTRY_IF_NONE:
                        if (db_entry->type != entry->type)
                                break;
                        if (strcasecmp(db_entry->name, str) != 0)
                                break;
                        return (NSCD_DB_ENTRY_FOUND);
                }

                if (idx_p->next_p == NULL) {
                        if (option == NSCD_ADD_DB_ENTRY_LAST ||
                                option == NSCD_ADD_DB_ENTRY_IF_NONE) {
                                prev_p = idx_p;
                                goto add_entry;
                        }
                }

                cont:
                idx_p = idx_p->next_p;
        }

        add_entry:

        /*
         * the nscd_entry_t field should be the first field
         * in a nscd_hash_t
         */
        hash_entry = (nscd_hash_t *)entry;

        /* update the prev link list */
        hash_entry->prev_p = prev_p;
        if (prev_p == NULL)
                db->hash_tbl_p[i] = hash_entry;
        else
                prev_p->next_p = hash_entry;

        /* update the next link list */
        hash_entry->next_p = next_p;
        if (next_p != NULL)
                next_p->prev_p = hash_entry;

        return (NSCD_SUCCESS);
}

/*
 * FUNCTION: _nscd_delete_db_entry
 *
 * Delete a nscd database entry from a nscd database. This
 * function is not MT safe. The caller should lock the
 * database to prevent concurrent updates done by other
 * threads.
 */
nscd_rc_t
_nscd_delete_db_entry(
        nscd_db_t               *db,
        int                     type,
        const char              *str,
        nscd_db_option_t        option,
        int                     id_num)
{
        int                     i;
        int                     del_more = 0;
        unsigned long           hash;
        nscd_hash_t             *idx_p, *next_p = NULL, *prev_p = NULL;
        nscd_db_entry_t         *db_entry;

        /* find the bucket */
        hash = calc_hash(str);
        i = hash % db->array_size;
        idx_p = db->hash_tbl_p[i];

        /* delete nothing always works */
        if (idx_p == NULL)
                return (NSCD_SUCCESS);

        while (idx_p != NULL) {
                db_entry = &idx_p->db_entry;
                if (db_entry->type != type)
                        goto cont;
                if (strcasecmp(db_entry->name, str) != 0)
                        goto cont;

                switch (option) {

                case NSCD_DEL_FIRST_DB_ENTRY:
                        prev_p = idx_p->prev_p;
                        next_p = idx_p->next_p;
                        del_more = 0;
                        break;

                case NSCD_DEL_EXACT_DB_ENTRY:
                        if (db_entry->id_num == id_num) {
                                prev_p = idx_p->prev_p;
                                next_p = idx_p->next_p;
                                del_more = 0;
                        } else
                                goto cont;
                        break;

                case NSCD_DEL_ALL_DB_ENTRY:
                        prev_p = idx_p->prev_p;
                        next_p = idx_p->next_p;
                        break;
                }

                if (prev_p == NULL)
                        db->hash_tbl_p[i] = next_p;
                else
                        prev_p->next_p = next_p;

                if (next_p != NULL)
                        next_p->prev_p = prev_p;

                free(idx_p);

                if (del_more == 0)
                        break;
                /*
                 * only when option == NSCD_DEL_ALL_DB_ENTRY
                 * will we get here. next_p should be set to
                 * idx_p->next_p beforehand
                 */
                idx_p = next_p;
                continue;

                cont:

                idx_p = idx_p->next_p;
        }

        return (NSCD_SUCCESS);
}

/*
 * FUNCTION: _nscd_alloc_db_entry
 *
 * Allocate and return the memory for a database entry
 * so the caller can insert data and then add it to the
 * database.
 */
nscd_db_entry_t *
_nscd_alloc_db_entry(
        int                     type,
        const char              *name,
        int                     dataSize,
        int                     num_data,
        int                     num_array)
{
        int                     size;
        int                     array_o, data_o;
        nscd_hash_t             *hash;
        void                    *p;

        /* first part: hash data structure and name string */
        size = sizeof (*hash) + strlen(name) + 1;
        array_o = size = roundup(size);

        /* second part: pointer array to data */
        size += (num_data  + num_array) * sizeof (void **);
        size = roundup(size);

        /* third part: actual data */
        data_o = size;
        size += dataSize;

        /* allocate the memory */
        hash = (nscd_hash_t *)calloc(1, size);

        if (hash == NULL)
                return (NULL);

        /* init the entry based on caller's input */
        hash->db_entry.num_data = num_data;
        hash->db_entry.num_array = num_array;
        hash->db_entry.type = type;
        hash->db_entry.name = (char *)hash + sizeof (*hash);
        p = (char *)hash + array_o;
        hash->db_entry.data_array = (void **)p;
        *(hash->db_entry.data_array) = (char *)hash + data_o;
        (void) strcpy(hash->db_entry.name, name);

        return (&hash->db_entry);
}

/*
 * FUNCTION: _nscd_delete_db_entry_cookie
 *
 * Delete a database entry using the information from
 * the input 'cookie'.
 */
void
_nscd_delete_db_entry_cookie(
        nscd_db_t       *db,
        void            **cookie)
{
        nscd_hash_t     *hp;
        struct cookie   *c;

        /* snaity check */
        if (cookie == NULL || *cookie == NULL || db == NULL)
                return;
        c = *cookie;

        /* more snaity check */
        if (db != c->db || c->hash == NULL ||
                c->idx < 0 || c->idx >= db->array_size)
                return;

        /* retrieve the hash entry from the cookie */
        hp = c->hash;

        /*
         * Update the next/previous link list.
         * Need to update c->hash as well, in case
         * the cookie is also used in a walk-db
         * loop. This is to make sure that the
         * next _nscd_walk_db() call will
         * find the (updated) next hash entry in line.
         */
        if (hp->prev_p == NULL) {
                /*
                 * make sure the current bucket will be
                 * walked again if _nscd_walk_db is
                 * called next
                 */
                c->hash = NULL;
                db->hash_tbl_p[c->idx] = hp->next_p;
                c->idx--;

        } else {
                c->hash = hp->prev_p;
                hp->prev_p->next_p = hp->next_p;
        }
        if (hp->next_p != NULL)
                hp->next_p->prev_p = hp->prev_p;

        /* delete the entry */
        free(hp);
}

/*
 * FUNCTION: _nscd_alloc_db
 *
 * Allocate the space for a nscd database.
 *
 * The input argument, size, indicates the size of the database.
 * NSCD_DB_SIZE_LARGE specifies an bucket array of size 67,
 * NSCD_DB_SIZE_MEDIUM specifies an bucket array of size 37,
 * NSCD_DB_SIZE_SMALL specifies an bucket array of size 13,
 * NSCD_DB_SIZE_TINY specifies an bucket array of size 3.
 */
nscd_db_t *
_nscd_alloc_db(
        int             size)
{
        int             sz;
        nscd_db_t       *db;

        /* allocate the database */
        db = (nscd_db_t *)calloc(1, sizeof (nscd_db_t));
        if (db == NULL)
                return (NULL);

        /* allocate the bucket array */
        if (size == NSCD_DB_SIZE_LARGE)
                sz = 67;
        else if (size == NSCD_DB_SIZE_MEDIUM)
                sz = 37;
        else if (size == NSCD_DB_SIZE_SMALL)
                sz = 13;
        else if (size == NSCD_DB_SIZE_TINY)
                sz = 3;
        db->hash_tbl_p = (nscd_hash_t  **)calloc(sz + 1,
                        sizeof (nscd_hash_t *));
        if (db->hash_tbl_p == NULL) {
                free(db);
                return (NULL);
        }

        db->array_size = sz;

        return (db);
}

/*
 * FUNCTION: _nscd_free_db
 *
 * Delete a nscd database.
 */
void
_nscd_free_db(
        nscd_db_t       *db)
{
        int             i;
        nscd_hash_t     *hp, *next_p;

        /*
         * find non-empty buckets and for each one of them,
         * delete all the database entries in it's link list
         */
        for (i = 0; i < db->array_size; i++) {

                hp = db->hash_tbl_p[i];

                while (hp != NULL) {
                        next_p = hp->next_p;
                        free(hp);
                        hp = next_p;
                }
        }

        /* free the bucket array */
        free(db->hash_tbl_p);

        free(db);
}

/*
 * FUNCTION: _nscd_walk_db
 *
 * Iterate through the database entries contained in
 * a nscd database and return one entry at a time.
 * The cookie structure is used to indicate the
 * location of the returned entry for the next call
 * to this function. For the very first call, *cookie
 * should be set to NULL. For subsequent calls, the one
 * returned by the previous call sould be used.
 */
nscd_db_entry_t *
_nscd_walk_db(
        nscd_db_t       *db,
        void            **cookie)
{
        struct cookie   *c;

        /* sanity check */
        if (cookie == NULL || db == NULL)
                return (NULL);

        if (*cookie != NULL) {

                c = *cookie;

                /*
                 * More sanity check. _nscd_delete_db_entry_cookie()
                 * could change c->idx to -1.
                 */
                if (db != c->db ||
                        c->idx < -1 || c->idx >= db->array_size)
                        return (NULL);

                /* is there a next entry ? */
                if (c->hash != NULL)
                        c->hash = c->hash->next_p;

                /* yes, return it */
                if (c->hash != NULL) {
                        return (&c->hash->db_entry);
                }
        } else {
                c = (struct cookie *)calloc(1, sizeof (*c));
                if (c == NULL)
                        return (NULL);
                c->idx = -1;
                c->hash = NULL;
                c->db = db;
        }

        /* find the first non-empty bucket */
        for (c->idx++; c->idx < db->array_size; c->idx++) {
                c->hash = db->hash_tbl_p[c->idx];
                if (c->hash != NULL)
                        break;
        }

        /* no (more) non-empty bucket, we are done */
        if (c->hash == NULL) {
                free(c);
                *cookie = NULL;
                return (NULL);
        }

        *cookie = c;
        return (&c->hash->db_entry);
}