xref: /illumos-gate/usr/src/lib/libnisdb/db_index_entry.cc (revision 1da57d55)

/*
 * 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_entry.cc
 *
 *	Copyright (c) 1988-2000 by Sun Microsystems, Inc.
 *	All Rights Reserved.
 */

#include <stdio.h>

#include "db_headers.h"
#include "db_index_entry.h"
#include "nisdb_mt.h"

/* Constructor:  create an entry using given string and location info. */
db_index_entry::db_index_entry(char* name, int nlen, entryp ep)
{
	if ((key = new item(name, nlen)) == NULL)
		FATAL("db_index_entry::db_index_entry: cannot allocate space",
			DB_MEMORY_LIMIT);
	location = ep;
	next_result = next = NULL;
	/* what about hashval ? */
}

/*
 * Constructor:  create an entry using the given info.
 * A copy of the item is made.  New entry is added to head of list of 'n'.
*/
db_index_entry::db_index_entry(unsigned long hval, item* k,
				entryp ep, db_index_entry_p rest)
{
	if ((key = new item(k)) == NULL)
		FATAL(
		"db_index_entry::db_index_entry: cannot allocate space (2)",
		DB_MEMORY_LIMIT);
	location = ep;
	next = rest;
	next_result = NULL;
	hashval = hval;
}

/*
 * Join two lists (entry as identified by its 'location' occurs on both list,
 * then it is included in the list returned).
 * Returns pointer to resulting list; size of list
 * returned in 'newsize'.  List is chained using the 'nextresult' pointer.
 */
db_index_entry_p
db_index_entry::join(long /* size1 */, long /* size2 */,
	db_index_entry_p list2, long * newsize)
{
	db_index_entry_p mergedlist = NULL, // records that occur on both lists
		mergedtail = NULL, 	// tail pointer of mergedlist
		current,		// current pointer of this list
		other,			// current pointer of updated list2
		otherprev,		// previous pointer of updated list2
		otherstart = list2;	// head of updated list2
	int count = 0;

	/*
	 * algorithm is straightforward:
	 * traverse this list,
	 * for each item, traverse list2,
	 * if item on list1 matches item on list2,
	 * add to merged list and delete it from list2.
	 */

	for (current = this; (current != NULL) && (otherstart != NULL);
					current = current->next_result) {
		/* find 'current' in 'other' list */
		otherprev = NULL;
		for (other = otherstart;
			other != NULL;
			other = other->next_result) {
			if (current->location == other->location)
				break;
			else
				otherprev = other;
		}
		if (other != NULL) { /* found */
			/* delete 'other' from future consideration */
			if (otherprev == NULL) {
				/* new head */
				otherstart = otherstart->next_result;
			} else {
				/* bypass 'other' */
				otherprev->next_result = other->next_result;
			}
			/* add 'current' to list of items found so far */
			if (mergedlist == NULL)
				mergedlist = current;	/* first one found */
			else
				mergedtail->next_result = current; /* append */
			mergedtail = current; /* point to last entry found */
			++count;
		}
	}
	if (mergedtail) mergedtail->next_result = NULL;  /* set end to null */
	*newsize = count;
	return (mergedlist);
}

/* Relocate bucket starting with this entry to new hashtable 'new_tab'. */
void
db_index_entry::relocate(db_index_entry_p *new_tab, unsigned long hashsize)
{
	db_index_entry_p np, next_np, *hp;

	for (np = this; np != NULL; np = next_np) {
		next_np = np->next;
		hp = &new_tab[np->hashval % hashsize];
		np->next = *hp;
		*hp = np;
	}
}

/* Return the next entry in the bucket starting with this entry
	    with the same hashvalue, key and location as this entry. */
db_index_entry_p
db_index_entry::getnext(bool_t casein, unsigned long hval, item *i, entryp l)
{
	db_index_entry_p np;

	for (np = this; np != NULL; np = np->next) {
		if ((np->hashval == hval) &&
	(np->key->equal(i, casein)) && l == location) {
			break;
		}
	}

	if (np != NULL)
		return (np->next);
	else
		return (NULL);
}

/*
 * Return pointer to index entry with same hash value, same key,
 * and same record number as those supplied.  Returns NULL if not found.
 */
db_index_entry_p
db_index_entry::lookup(bool_t casein, unsigned long hval,
			item *i, entryp recnum)
{
	db_index_entry_p np;

	for (np = this; np != NULL; np = np->next) {
		if (np->hashval == hval && np->key->equal(i, casein) &&
			np->location == recnum) {
			break;
		}
	}
	if (np) np->next_result = NULL;  /* should only be 1 */
	return (np);
}

/*
 * Returns pointer to a list of index entries with the same hash value and
 * key as those given.  Returns in 'how_many' the number of entries in the
 * list returned.  The list is linked by the 'next_result' field of the
 * index entries.  These may be changed after the next call to 'lookup'
 * or 'join'.
 */
db_index_entry_p
db_index_entry::lookup(bool_t casein, unsigned long hval,
			item *i, long * how_many)
{
	db_index_entry_p fst, prev, curr;
	long count = 0;

	for (fst = this; fst != NULL; fst = fst->next) {
		if ((fst->hashval == hval) && (fst->key->equal(i, casein))) {
			++count;
			break;
		}
	}
	/*
	 * gather all the ones with the same key; assume that all entries
	 * with same key are located contiguously.
	 */
	if (fst != NULL) {
		prev = fst;
		for (curr = fst->next; curr != NULL; curr = curr->next) {
			if ((curr->hashval == hval) &&
				(curr->key->equal(i, casein))) {
	prev->addresult(curr);
	prev = curr;
	++count;
			}
			else
	break;
		}
		prev->addresult(NULL); /* terminate the list -CM */
	}
	*how_many = count;
	return (fst);
}

/*
 * Remove entry with the specified hashvalue, key, and record number.
 * Returns 'TRUE' if successful, FALSE otherwise.
 * If the entry being removed is at the head of the list, then
 * the head is updated to reflect the removal. The storage for the index
 * entry is freed. The record pointed to by 'recnum' must be removed
 * through another means.  All that is updated in this operation is the
 * index.
 */
bool_t
db_index_entry::remove(db_index_entry_p *head, bool_t casein,
			unsigned long hval, item *i, entryp recnum)
{
	db_index_entry_p np, dp;

	/* Search for it in the bucket */
	for (dp = np = this; np != NULL; np = np->next) {
		if (np->hashval == hval && np->key->equal(i, casein) &&
			np->location == recnum) {
			break;
		} else {
			dp = np;
		}
	}

	if (np == NULL) return FALSE;	// cannot delete if it is not there

	if (dp == np) {
		*head = np->next;	// deleting head of bucket
	} else {
		dp->next = np->next;	// deleting interior link
		}
	delete np;

	return (TRUE);
}

/* Replace the 'location' field of the index entry with the given one. */
/*
void
db_index_entry::replace(entryp ep)
{
	location = ep;
}
*/

/*
 * Create and add an entry with the given hashvalue, key value, and record
 * location, to the bucket pointed to by 'hashvalue'.
 * If an entry with the same hashvalue and key value is found,
 * the entry is added after the first entry with this property.  Otherwise,
 * the entry is added to the head of the bucket.  This way, entries
 * with the same hashvalue and key are not scattered throughout the bucket
 * but they occur together. Copy is made of given key.
 */
bool_t
db_index_entry::add(db_index_entry **head, bool_t casein,
			unsigned long hval, item *i, entryp recnum)

{
	db_index_entry_p curr, prev, rp, save;

	/* Search for it in the bucket */
	for (prev = curr = this; curr != NULL; curr = curr->next) {
		if (curr->hashval == hval && curr->key->equal(i, casein)) {
			break;
		} else {
			prev = curr;
		}
	}



	if (curr == NULL) {
		/* none with same hashvalue/key found. Add to head of list. */
		save = *head;
		*head = new db_index_entry(hval, i, recnum, * head);
		if (*head == NULL) {
			*head = save;	// restore previous state
			FATAL3(
			"db_index_entry::add: cannot allocate space for head",
			DB_MEMORY_LIMIT, FALSE);
		}
	} else {
		/* Found same hashvalue/key.  Add entry after that one. */
		save = prev->next;
		prev->next = new db_index_entry(hval, i, recnum, prev->next);
		if (prev->next == NULL) {
			prev->next = save; // restore previous state
			FATAL3(
			"db_index_entry::add: cannot allocate space for entry",
			DB_MEMORY_LIMIT, FALSE);
		}
	}

	return (TRUE);
}

/* Print this entry to stdout. */
void
db_index_entry::print()
{
	if (key != NULL) {
			key->print();
			printf("\t");
		}
	printf(": %d\n", location);
}

/* Print bucket starting with this entry. */
void
db_index_entry::print_all()
{
	db_index_entry *np;
	for (np = this; np != NULL; np = np->next) {
		np->print();
		}
}

/* Print result list starting with this entry. */
void
db_index_entry::print_results()
{
	db_index_entry *np;
	for (np = this; np != NULL; np = np->next_result) {
		np->print();
		}
}