gdk_delta.mx

这个是内存数据库中的一个管理工具

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f gdk_delta
@a M. L. Kersten, P. Boncz
@* Delta management
The basis for transaction management is to keep track of
elements inserted, deleted, and replaced.
This information is stored within the BAT structure using three
delta markers.
Inserted denotes
the first added BUN since the last commit. Deleted points to the BUNs removed.
The deletion list is terminated at @%first@, where space is reserved for swapping
BUNs upon deletion. Initialization of the BAT is extended as follows:

@{
@h
#ifndef _GDK_DELTA_H_
#define _GDK_DELTA_H_
#include "gdk.h"

@-
We make sure here that the BUNs section of a BAT at least starts 
4 bytes from the BUN start.  This ensures that the first data 
item of e.g. a BAT[void,bit] is (at least) integer aligned. 
This optimizes processing on such BATs (DDBENCH).
@h
#define DELTAprintf DELTADEBUG printf
#define DELTAinit(P1)	do {						      \
	BATsetcount((P1), 0);						      \
	(P1)->batBuns->free = 0;					      \
	(P1)->batDeleted = (P1)->batInserted = (P1)->batFirst = 	      \
		(BUN) Bunbase(P1);      	                              \
	(P1)->batElmshift = BATelmshift((P1));				      \
	DELTAprintf(							      \
	 	"#DELTAinit %s free " SZFMT " ins " PTRFMT " del " PTRFMT " first " PTRFMT " base " PTRFMT "\n", \
		BATgetId(P1),				      \
		(P1)->batBuns->free,			      \
		PTRFMTCAST (P1)->batInserted,		      \
		PTRFMTCAST (P1)->batDeleted,		      \
		PTRFMTCAST (P1)->batFirst,		      \
		PTRFMTCAST (P1)->batBuns->base );	      \
} while (0)
@

Upon saving a BAT, we should convert the delta marker BUN pointers into indexes
and convert them back into pointers upon reload.

@h
#define DELTAsave(P1)	do {						\
	(P1)->batInserted = (BUN) BUNindex((P1), (P1)->batInserted);	\
	(P1)->batDeleted = (BUN) BUNindex((P1), (P1)->batDeleted);	\
	(P1)->batFirst = (BUN) BUNindex((P1), (P1)->batFirst);		\
	DELTAprintf(							\
	 	"#DELTAsave %s free " SZFMT " ins " PTRFMT " del " PTRFMT " first " PTRFMT " base " PTRFMT "\n", \
		BATgetId(P1),						\
		(P1)->batBuns->free,					\
		PTRFMTCAST (P1)->batInserted,				\
		PTRFMTCAST (P1)->batDeleted,				\
		PTRFMTCAST (P1)->batFirst,				\
		PTRFMTCAST (P1)->batBuns->base );			\
} while (0)

#define DELTAload(P1)	do {						\
	DELTAprintf(							\
		"#DELTAload %s free " SZFMT " ins " PTRFMT " del " PTRFMT " first " PTRFMT " base " PTRFMT "\n", \
		BATgetId(P1),						\
		(P1)->batBuns->free,					\
		PTRFMTCAST (P1)->batInserted,				\
		PTRFMTCAST (P1)->batDeleted,				\
		PTRFMTCAST (P1)->batFirst,				\
		PTRFMTCAST (P1)->batBuns->base );			\
	(P1)->batInserted = BUNptr((P1), (size_t) (P1)->batInserted);	\
	(P1)->batDeleted = BUNptr((P1), (size_t) (P1)->batDeleted);	\
	(P1)->batFirst = BUNptr((P1), (size_t) (P1)->batFirst);		\
} while (0)
@	
@}
@-
The b->batDirty field tells you whether a BATs main memory representation
differs from its saved image on stable storage. But *not* whether it has
changed since last transaction commit (it can be storage-clean, but 
transaction-dirty). For this we have @%DELTAdirty(b)@.
@-
@{
@h
#define DELTAdirty(b)	(((b)->batDeleted != (b)->batFirst) ||\
	((b)->batInserted < (b)->batBuns->base+(b)->batBuns->free))

#endif /* _GDK_DELTA_H_ */
@

@- 
Impact on hashing and indexing.
The hash structure is maintained for all elements to be deleted ?.

@c
#include "monetdb_config.h"
#include "gdk.h"

@- 
batcommit really forgets the atoms guarded for an undo; we just need to free their heap space (only if necessary).
@c
BAT *
BATcommit(BAT *b)
{
	BATcheck(b, "BATcommit");
	DELTAprintf("#BATcommit1 %s free " SZFMT " ins " PTRFMT " del " PTRFMT " first " PTRFMT " base " PTRFMT "\n", BATgetId(b), b->batBuns->free, PTRFMTCAST b->batInserted, PTRFMTCAST b->batDeleted, PTRFMTCAST b->batFirst, PTRFMTCAST b->batBuns->base);
	ALIGNcommit(b);
	if (b->batDeleted < b->batFirst && BBP_cache(b->batCacheid)) {
		int (*hunfix) (ptr) = BATatoms[b->htype].atomUnfix;
		int (*tunfix) (ptr) = BATatoms[b->ttype].atomUnfix;
		void (*hatmdel) (Heap *, var_t *) = BATatoms[b->htype].atomDel;
		void (*tatmdel) (Heap *, var_t *) = BATatoms[b->ttype].atomDel;
		BUN p, q;
		int xx;

		if (hatmdel || hunfix || tatmdel || tunfix) {
			DELloop(b, p, q, xx) {
				ptr h = BUNhead(b, p);
				ptr t = BUNtail(b, p);

				if (hunfix) {
					(*hunfix) (h);
				}
				if (hatmdel) {
					(*hatmdel) (b->hheap, (var_t *) (p + b->hloc));
				}
				if (tunfix) {
					(*tunfix) (t);
				}
				if (tatmdel) {
					(*tatmdel) (b->theap, (var_t *) (p + b->tloc));
				}
			}
		}
	}
	if (!BATdirty(b)) {
		b->batDirtyflushed = 0;
	}
	if (DELTAdirty(b)) {
		b->batDirtydesc = 1;
	}
	b->batDeleted = b->batFirst;
	if (b->batBuns->base) {
		b->batInserted = BUNlast(b);
	} else {
		b->batInserted = (BUN) (b->batBuns->free / BUNsize(b));
	}
	DELTAprintf("#BATcommit2 %s free " SZFMT " ins " PTRFMT " del " PTRFMT " first " PTRFMT " base " PTRFMT "\n", BATgetId(b), b->batBuns->free, PTRFMTCAST b->batInserted, PTRFMTCAST b->batDeleted, PTRFMTCAST b->batFirst, PTRFMTCAST b->batBuns->base);
	return b;
}

@-
BATfakeCommit() flushed the delta info, but leaves the BAT marked clean.
@c 
BAT *
BATfakeCommit(BAT *b)
{
	if (b) {
		BATcommit(b);
		b->batDirty = 0;
		b->batDirtydesc = b->batDirtybuns = 0;
		b->hheapdirty = b->theapdirty = 0;
	}
	return b;
}

@
@}
@- 
The routine @%BATundo@ restores the BAT to the previous commit point.
The inserted elements are removed from the accelerators, deleted from the
heap. The guarded elements from uncommitted deletes are
inserted into the accelerators.
@-
@{
@c
BAT *
BATundo(BAT *b)
{
	int bunsize = BUNsize(b);
	BUN p, bunlast, bunfirst;

	BATcheck(b, "BATundo");
	DELTAprintf("#BATundo %s \n", BATgetId(b));
	ALIGNundo(b);
	if (b->batDirtyflushed) {
		b->batDirtydesc = b->batDirtybuns = 1;
	} else {
		b->batDirty = 0;
		b->batDirtydesc = b->batDirtybuns = 0;
		b->hheapdirty = b->theapdirty = 0;
	}
	bunfirst = b->batInserted;
	bunlast = BUNlast(b) - BUNsize(b);
	if (bunlast >= b->batInserted) {
		size_t i = BUNindex(b, bunfirst);
		int (*hunfix) (ptr) = BATatoms[b->htype].atomUnfix;
		int (*tunfix) (ptr) = BATatoms[b->ttype].atomUnfix;
		void (*hatmdel) (Heap *, var_t *) = BATatoms[b->htype].atomDel;
		void (*tatmdel) (Heap *, var_t *) = BATatoms[b->ttype].atomDel;

		if (hunfix || tunfix || hatmdel || tatmdel || b->hhash || b->thash) {
			for (p = bunfirst; p <= bunlast; p += bunsize, i++) {
				ptr h = BUNhead(b, p);
				ptr t = BUNtail(b, p);

				if (b->hhash) {
					HASHdel(b->hhash, i, h, p < bunlast);
				}
				if (hunfix) {
					(*hunfix) (h);
				}
				if (hatmdel) {
					(*hatmdel) (b->hheap, (var_t *) (p + b->hloc));
				}
				if (b->thash) {
					HASHdel(b->thash, i, t, p < bunlast);
				}
				if (tunfix) {
					(*tunfix) (t);
				}
				if (tatmdel) {
					(*tatmdel) (b->theap, (var_t *) (p + b->tloc));
				}
			}
		}
	}
	b->batBuns->free = (char *) b->batInserted - (char *) Bunbase(b);

	bunfirst = b->batDeleted;
	bunlast = b->batFirst;
	if (bunlast > b->batDeleted) {
		size_t i = BUNindex(b, bunfirst);
                BAT *bm = BBP_cache(-b->batCacheid);

		/* elements are 'inserted' => zap properties */
		if (b->hsorted & 1 || b->hsorted == (bit)GDK_SORTED_REV)
			b->hsorted = FALSE;
		if (b->tsorted & 1 || b->tsorted == (bit)GDK_SORTED_REV)
			b->tsorted = FALSE;
		if (b->hkey)
			BATkey(b, FALSE);
		if (b->tkey)
			BATkey(BATmirror(b), FALSE);

		for (p = bunfirst; p < bunlast; p += bunsize, i++) {
			ptr h = BUNhead(b, p);
			ptr t = BUNtail(b, p);

			if (b->hhash) {
				HASHins(b, i, h);
			}
			if (b->thash) {
				HASHins(bm, i, t);
			}
		}
	}
	b->batFirst = b->batDeleted;
	BATsetcount(b, (BUNlast(b)-BUNfirst(b))/BUNsize(b) );
	return b;
}

@}
@- 
The proposed modifications can be obtained through the @%BATalpha@
and @%BATdelta@ routines , which return the inserted and deleted BUNs, 
respectively.
@{
@c
BAT *
BATprev(BAT *b)
{
	BUN p;
	BAT *bn;

	BATcheck(b, "BATprev");
	if (b->batRestricted == BAT_READ) {
		bn = VIEWcreate(b);
		if (bn) {
			bn->batBuns->free = bn->batInserted - bn->batBuns->base;
			bn->batInserted = bn->batFirst = bn->batDeleted;
			BATsetcount(bn, (BUNlast(bn)-BUNfirst(bn))/BUNsize(bn) );
		}
		return bn;
	}
	bn = BATnew(BAThtype(b), BATttype(b), BATcapacity(b));
	if (bn == NULL) {
		return bn;
	}
	for (p = b->batDeleted; p < b->batInserted; p = BUNnext(b, p)) {
		if (BUNins(bn, BUNhead(b, p), BUNtail(b, p), FALSE) == NULL) {
			BBPreclaim(bn);
			return NULL;
		}
	}
	return bn;
}

BAT *
BATalpha(BAT *b)
{
	BUN p;
	BAT *bn;

	BATcheck(b, "BATalpha");
	if (b->batRestricted == BAT_READ) {
		bn = VIEWcreate(b);
		if (bn) {
			bn->batDeleted = bn->batFirst = bn->batInserted;
			BATsetcount(bn, (BUNlast(bn)-BUNfirst(bn))/BUNsize(bn) );
		}
		return bn;
	}
	bn = BATnew(BAThtype(b), BATttype(b), BATcapacity(b));
	if (bn == NULL) {
		return bn;
	}
	for (p = b->batInserted; p < BUNlast(b); p = BUNnext(b, p)) {
		if (BUNins(bn, BUNhead(b, p), BUNtail(b, p), FALSE) == NULL) {
			BBPreclaim(bn);
			return NULL;
		}
	}
	return bn;
}

BAT *
BATdelta(BAT *b)
{
	BUN p;
	BAT *bn;

	BATcheck(b, "BATdelta");
	if (b->batRestricted == BAT_READ) {
		bn = VIEWcreate(b);
		if (bn) {
			bn->batBuns->free = bn->batFirst - bn->batBuns->base;
			bn->batFirst = bn->batInserted = bn->batDeleted;
			BATsetcount(bn, (BUNlast(bn)-BUNfirst(bn))/BUNsize(bn) );
		}
		return bn;
	}
	bn = BATnew(BAThtype(b), BATttype(b), BATcapacity(b));
	if (bn == NULL) {
		return bn;
	}
	for (p = b->batDeleted; p < b->batFirst; p = BUNnext(b, p)) {
		if (BUNins(bn, BUNhead(b, p), BUNtail(b, p), FALSE) == NULL) {
			BBPreclaim(bn);
			return NULL;
		}
	}
	return bn;
}