1			/*
     2			 * sdbm - ndbm work-alike hashed database library
     3			 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
     4			 * author: oz@nexus.yorku.ca
     5			 * status: public domain.
     6			 *
     7			 * page-level routines
     8			 */
     9			
    10			#include "config.h"
    11			#ifdef __CYGWIN__
    12			# define EXTCONST extern const
    13			#else
    14			# include "EXTERN.h"
    15			#endif
    16			#include "sdbm.h"
    17			#include "tune.h"
    18			#include "pair.h"
    19			
    20			#define exhash(item)	sdbm_hash((item).dptr, (item).dsize)
    21			
    22			/* 
    23			 * forward 
    24			 */
    25			static int seepair proto((char *, int, char *, int));
    26			
    27			/*
    28			 * page format:
    29			 *	+------------------------------+
    30			 * ino	| n | keyoff | datoff | keyoff |
    31			 * 	+------------+--------+--------+
    32			 *	| datoff | - - - ---->	       |
    33			 *	+--------+---------------------+
    34			 *	|	 F R E E A R E A       |
    35			 *	+--------------+---------------+
    36			 *	|  <---- - - - | data          |
    37			 *	+--------+-----+----+----------+
    38			 *	|  key   | data     | key      |
    39			 *	+--------+----------+----------+
    40			 *
    41			 * calculating the offsets for free area:  if the number
    42			 * of entries (ino[0]) is zero, the offset to the END of
    43			 * the free area is the block size. Otherwise, it is the
    44			 * nth (ino[ino[0]]) entry's offset.
    45			 */
    46			
    47			int
    48			fitpair(char *pag, int need)
    49	         997    {
    50	         997    	register int n;
    51	         997    	register int off;
    52	         997    	register int free;
    53	         997    	register short *ino = (short *) pag;
    54			
    55	         997    	off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
    56	         997    	free = off - (n + 1) * sizeof(short);
    57	         997    	need += 2 * sizeof(short);
    58			
    59				debug(("free %d need %d\n", free, need));
    60			
    61	         997    	return need <= free;
    62			}
    63			
    64			void
    65			putpair(char *pag, datum key, datum val)
    66	        1715    {
    67	        1715    	register int n;
    68	        1715    	register int off;
    69	        1715    	register short *ino = (short *) pag;
    70			
    71	        1715    	off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
    72			/*
    73			 * enter the key first
    74			 */
    75	        1715    	off -= key.dsize;
    76	        1715    	(void) memcpy(pag + off, key.dptr, key.dsize);
    77	        1715    	ino[n + 1] = off;
    78			/*
    79			 * now the data
    80			 */
    81	        1715    	off -= val.dsize;
    82	        1715    	(void) memcpy(pag + off, val.dptr, val.dsize);
    83	        1715    	ino[n + 2] = off;
    84			/*
    85			 * adjust item count
    86			 */
    87	        1715    	ino[0] += 2;
    88			}
    89			
    90			datum
    91			getpair(char *pag, datum key)
    92	        1154    {
    93	        1154    	register int i;
    94	        1154    	register int n;
    95	        1154    	datum val;
    96	        1154    	register short *ino = (short *) pag;
    97			
    98	        1154    	if ((n = ino[0]) == 0)
    99	      ######    		return nullitem;
   100			
   101	        1154    	if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
   102	           8    		return nullitem;
   103			
   104	        1146    	val.dptr = pag + ino[i + 1];
   105	        1146    	val.dsize = ino[i] - ino[i + 1];
   106	        1146    	return val;
   107			}
   108			
   109			int
   110			exipair(char *pag, datum key)
   111	           2    {
   112	           2    	register short *ino = (short *) pag;
   113			
   114	           2    	if (ino[0] == 0)
   115	      ######    		return 0;
   116			
   117	           2    	return (seepair(pag, ino[0], key.dptr, key.dsize) != 0);
   118			}
   119			
   120			#ifdef SEEDUPS
   121			int
   122			duppair(char *pag, datum key)
   123	      ######    {
   124	      ######    	register short *ino = (short *) pag;
   125	      ######    	return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
   126			}
   127			#endif
   128			
   129			datum
   130			getnkey(char *pag, int num)
   131	         425    {
   132	         425    	datum key;
   133	         425    	register int off;
   134	         425    	register short *ino = (short *) pag;
   135			
   136	         425    	num = num * 2 - 1;
   137	         425    	if (ino[0] == 0 || num > ino[0])
   138	          41    		return nullitem;
   139			
   140	         384    	off = (num > 1) ? ino[num - 1] : PBLKSIZ;
   141			
   142	         384    	key.dptr = pag + ino[num];
   143	         384    	key.dsize = off - ino[num];
   144			
   145	         384    	return key;
   146			}
   147			
   148			int
   149			delpair(char *pag, datum key)
   150	         997    {
   151	         997    	register int n;
   152	         997    	register int i;
   153	         997    	register short *ino = (short *) pag;
   154			
   155	         997    	if ((n = ino[0]) == 0)
   156	          29    		return 0;
   157			
   158	         968    	if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
   159	         559    		return 0;
   160			/*
   161			 * found the key. if it is the last entry
   162			 * [i.e. i == n - 1] we just adjust the entry count.
   163			 * hard case: move all data down onto the deleted pair,
   164			 * shift offsets onto deleted offsets, and adjust them.
   165			 * [note: 0 < i < n]
   166			 */
   167	         409    	if (i < n - 1) {
   168	         401    		register int m;
   169	         401    		register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
   170	         401    		register char *src = pag + ino[i + 1];
   171	         401    		register int   zoo = dst - src;
   172			
   173					debug(("free-up %d ", zoo));
   174			/*
   175			 * shift data/keys down
   176			 */
   177	         401    		m = ino[i + 1] - ino[n];
   178			#ifdef DUFF
   179			#define MOVB 	*--dst = *--src
   180			
   181	         401    		if (m > 0) {
   182	         401    			register int loop = (m + 8 - 1) >> 3;
   183			
   184	         401    			switch (m & (8 - 1)) {
   185	       14596    			case 0:	do {
   186	       14596    				MOVB;	case 7:	MOVB;
   187	       14744    			case 6:	MOVB;	case 5:	MOVB;
   188	       14846    			case 4:	MOVB;	case 3:	MOVB;
   189	       14892    			case 2:	MOVB;	case 1:	MOVB;
   190	       14914    				} while (--loop);
   191						}
   192					}
   193			#else
   194			#ifdef HAS_MEMMOVE
   195					dst -= m;
   196					src -= m;
   197					memmove(dst, src, m);
   198			#else
   199					while (m--)
   200						*--dst = *--src;
   201			#endif
   202			#endif
   203			/*
   204			 * adjust offset index up
   205			 */
   206	       45137    		while (i < n - 1) {
   207	       44736    			ino[i] = ino[i + 2] + zoo;
   208	       44736    			i++;
   209					}
   210				}
   211	         409    	ino[0] -= 2;
   212	         409    	return 1;
   213			}
   214			
   215			/*
   216			 * search for the key in the page.
   217			 * return offset index in the range 0 < i < n.
   218			 * return 0 if not found.
   219			 */
   220			static int
   221			seepair(char *pag, register int n, register char *key, register int siz)
   222	        2124    {
   223	        2124    	register int i;
   224	        2124    	register int off = PBLKSIZ;
   225	        2124    	register short *ino = (short *) pag;
   226			
   227	       83364    	for (i = 1; i < n; i += 2) {
   228	       82796    		if (siz == off - ino[i] &&
   229					    memEQ(key, pag + ino[i], siz))
   230	        1556    			return i;
   231	       81240    		off = ino[i + 1];
   232				}
   233	         568    	return 0;
   234			}
   235			
   236			void
   237			splpage(char *pag, char *New, long int sbit)
   238	           6    {
   239	           6    	datum key;
   240	           6    	datum val;
   241			
   242	           6    	register int n;
   243	           6    	register int off = PBLKSIZ;
   244	           6    	char cur[PBLKSIZ];
   245	           6    	register short *ino = (short *) cur;
   246			
   247	           6    	(void) memcpy(cur, pag, PBLKSIZ);
   248	           6    	(void) memset(pag, 0, PBLKSIZ);
   249	           6    	(void) memset(New, 0, PBLKSIZ);
   250			
   251	           6    	n = ino[0];
   252	         730    	for (ino++; n > 0; ino += 2) {
   253	         724    		key.dptr = cur + ino[0]; 
   254	         724    		key.dsize = off - ino[0];
   255	         724    		val.dptr = cur + ino[1];
   256	         724    		val.dsize = ino[0] - ino[1];
   257			/*
   258			 * select the page pointer (by looking at sbit) and insert
   259			 */
   260	         724    		(void) putpair((exhash(key) & sbit) ? New : pag, key, val);
   261			
   262	         724    		off = ino[1];
   263	         724    		n -= 2;
   264				}
   265			
   266				debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
   267				       ((short *) New)[0] / 2,
   268				       ((short *) pag)[0] / 2));
   269			}
   270			
   271			/*
   272			 * check page sanity: 
   273			 * number of entries should be something
   274			 * reasonable, and all offsets in the index should be in order.
   275			 * this could be made more rigorous.
   276			 */
   277			int
   278			chkpage(char *pag)
   279	        1380    {
   280	        1380    	register int n;
   281	        1380    	register int off;
   282	        1380    	register short *ino = (short *) pag;
   283			
   284	        1380    	if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
   285	      ######    		return 0;
   286			
   287	        1380    	if (n > 0) {
   288	        1351    		off = PBLKSIZ;
   289	      109022    		for (ino++; n > 0; ino += 2) {
   290	      107671    			if (ino[0] > off || ino[1] > off ||
   291						    ino[1] > ino[0])
   292	      ######    				return 0;
   293	      107671    			off = ino[1];
   294	      107671    			n -= 2;
   295					}
   296				}
   297	        1380    	return 1;
   298			}