pair.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* sdbm - ndbm work-alike hashed database library
* based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
* author: oz@nexus.yorku.ca
* status: public domain.
*
* page-level routines
*/
#include "config.h"
#ifdef __CYGWIN__
# define EXTCONST extern const
#else
# include "EXTERN.h"
#endif
#include "sdbm.h"
#include "tune.h"
#include "pair.h"
/*
* forward
*/
/*
* page format:
* +------------------------------+
* ino | n | keyoff | datoff | keyoff |
* +------------+--------+--------+
* | datoff | - - - ----> |
* +--------+---------------------+
* | F R E E A R E A |
* +--------------+---------------+
* | <---- - - - | data |
* +--------+-----+----+----------+
* | key | data | key |
* +--------+----------+----------+
*
* calculating the offsets for free area: if the number
* of entries (ino[0]) is zero, the offset to the END of
* the free area is the block size. Otherwise, it is the
* nth (ino[ino[0]]) entry's offset.
*/
int
{
register int n;
register int off;
register int free;
need += 2 * sizeof(short);
}
void
{
register int n;
register int off;
/*
* enter the key first
*/
/*
* now the data
*/
/*
* adjust item count
*/
ino[0] += 2;
}
{
register int i;
register int n;
if ((n = ino[0]) == 0)
return nullitem;
return nullitem;
return val;
}
int
{
if (ino[0] == 0)
return 0;
}
#ifdef SEEDUPS
int
{
}
#endif
{
register int off;
return nullitem;
return key;
}
int
{
register int n;
register int i;
if ((n = ino[0]) == 0)
return 0;
return 0;
/*
* found the key. if it is the last entry
* [i.e. i == n - 1] we just adjust the entry count.
* hard case: move all data down onto the deleted pair,
* shift offsets onto deleted offsets, and adjust them.
* [note: 0 < i < n]
*/
if (i < n - 1) {
register int m;
/*
*/
#ifdef DUFF
if (m > 0) {
switch (m & (8 - 1)) {
case 0: do {
} while (--loop);
}
}
#else
#ifdef HAS_MEMMOVE
dst -= m;
src -= m;
#else
while (m--)
#endif
#endif
/*
* adjust offset index up
*/
while (i < n - 1) {
i++;
}
}
ino[0] -= 2;
return 1;
}
/*
* search for the key in the page.
* return offset index in the range 0 < i < n.
* return 0 if not found.
*/
static int
{
register int i;
for (i = 1; i < n; i += 2) {
return i;
}
return 0;
}
void
{
register int n;
n = ino[0];
/*
* select the page pointer (by looking at sbit) and insert
*/
n -= 2;
}
((short *) New)[0] / 2,
((short *) pag)[0] / 2));
}
/*
* check page sanity:
* number of entries should be something
* reasonable, and all offsets in the index should be in order.
* this could be made more rigorous.
*/
int
{
register int n;
register int off;
return 0;
if (n > 0) {
return 0;
n -= 2;
}
}
return 1;
}