Changeset: 1d9d829eb848 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=1d9d829eb848
Modified Files:
geom/monetdb5/geomPoints.c
Branch: geo
Log Message:
PBSM added back
diffs (truncated from 472 to 300 lines):
diff --git a/geom/monetdb5/geomPoints.c b/geom/monetdb5/geomPoints.c
--- a/geom/monetdb5/geomPoints.c
+++ b/geom/monetdb5/geomPoints.c
@@ -24,7 +24,7 @@
#include "time.h"
#include "unistd.h"
-/*
+
typedef struct pbsm_ptr {
BUN offset;
unsigned long count;
@@ -32,11 +32,13 @@ typedef struct pbsm_ptr {
static pbsm_ptr *pbsm_idx = NULL;
static oid *oids = NULL;
-static mbr *limits = NULL;
+//static mbr *limits = NULL;
//hard coded filename
static char* filename = "../pbsmIndex_20m";
-*/
+static char* idxFilename;
+static char* dataFilename;
+static char* limitsFilename;
//it gets two BATs with x,y coordinates and returns a new BAT with the points
static BAT* BATMakePoint2D(BAT* xBAT, BAT* yBAT) {
@@ -884,6 +886,432 @@ static str wkbPointsFilterWithImprints_g
}
+/* PBSM */
+static str createFilenames(str module) {
+ char* idxEnding = ".idx";
+ char* dataEnding = ".data";
+ char* limitsEnding =".mbb";
+
+ //allocate space for the files
+ if((idxFilename = (char*)
GDKmalloc(strlen(filename)+strlen(idxEnding)+1)) == NULL) {
+ return createException(MAL, module, "Problem allocating space
for idxFilename");
+ }
+ if((dataFilename = (char*)
GDKmalloc(strlen(filename)+strlen(dataEnding)+1)) == NULL) {
+ GDKfree(idxFilename);
+ return createException(MAL, module, "Problem allocating space
for dataFilename");
+ }
+ if((limitsFilename = (char*)
GDKmalloc(strlen(filename)+strlen(limitsEnding)+1)) == NULL) {
+ GDKfree(idxFilename);
+ GDKfree(dataFilename);
+ return createException(MAL, module, "Problem allocating space
for limitsFilename");
+ }
+
+ strcpy(idxFilename, filename);
+ strcpy(idxFilename+strlen(filename), idxEnding);
+ strcpy(dataFilename, filename);
+ strcpy(dataFilename+strlen(filename), dataEnding);
+ strcpy(limitsFilename, filename);
+ strcpy(limitsFilename+strlen(filename), limitsEnding);
+
+ return MAL_SUCCEED;
+}
+
+static char *
+PBSMcomputeindex1(const dbl *x, const dbl *y, BUN n, double minx, double maxx,
double miny, double maxy, oid seqbase) {
+ sht *cells;
+ BAT *pbsm;
+ unsigned long i;
+ int shift = sizeof(sht) * 8 / 2;
+ sht prevCell, cell;
+ unsigned long m = 0, prevO;
+
+
+ if((pbsm = BATnew(TYPE_void, TYPE_sht, n, TRANSIENT)) == NULL)
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+ cells = (sht*) Tloc(pbsm, BUNfirst(pbsm));
+
+ // calculate the pbsm values
+ for (i = 0; i < n; i++) {
+ unsigned char cellx = ((x[i] - minx)/(maxx - minx))*UCHAR_MAX;
+ unsigned char celly = ((y[i] - miny)/(maxy - miny))*UCHAR_MAX;
+ cells[i] = ((((unsigned short) cellx) << shift)) | ((unsigned
short) celly);
+ }
+
+ // order the BAT according to the cell values
+ /* set some properties */
+ BATsetcount(pbsm,n);
+ BATseqbase(pbsm, 0);
+ pbsm->hsorted = 1;
+ pbsm->hrevsorted = (BATcount(pbsm) <= 1);
+ pbsm->tsorted = 0;
+ pbsm->trevsorted = 0;
+ pbsm->hdense = true;
+ pbsm->tdense = false;
+ BATseqbase(pbsm, seqbase);
+ BATmaterialize(pbsm);
+ //BATderiveProps(pbsm, false);
+ //BATassertProps(pbsm);
+ pbsm = BATorder(BATmirror(pbsm));
+ //BATprint(pbsm);
+
+ // compress the head
+ cells = (sht*) Hloc(pbsm, BUNfirst(pbsm));
+ oids = (oid*) Tloc(pbsm, BUNfirst(pbsm));
+
+ prevCell = cells[0];
+ cell = cells[0];
+ m = 0;
+ prevO = 0;
+ for (i = 0; i < n; i++) {
+ cell = cells[i];
+
+ if (cell == prevCell) {
+ m++;
+ } else {
+ pbsm_idx[cell - SHRT_MIN].offset = prevO;
+ pbsm_idx[cell - SHRT_MIN].count = m;
+ prevCell = cell;
+ prevO = i;
+ m = 1;
+ }
+ }
+ pbsm_idx[cell - SHRT_MIN].offset = prevO;
+ pbsm_idx[cell - SHRT_MIN].count = m;
+
+ // clean up
+ pbsm->T->heap.base = NULL; // need to keep the oids array
+ BBPreleaseref(pbsm->batCacheid);
+
+ return MAL_SUCCEED;
+}
+
+
+static char *
+PBSMcomputeindex2(const dbl *x, const dbl *y, BUN n, double minx, double maxx,
double miny, double maxy, oid seqbase) {
+ unsigned long *tmpCount;
+ unsigned long i;
+ int shift = sizeof(sht) * 8 / 2;
+
+ if ((pbsm_idx = GDKmalloc(USHRT_MAX * sizeof(pbsm_ptr))) == NULL)
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+
+ if ((oids = GDKmalloc(n * sizeof(oid))) == NULL) {
+ GDKfree(pbsm_idx);
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+ }
+
+ if ((tmpCount = GDKmalloc(USHRT_MAX * sizeof(unsigned long))) == NULL) {
+ GDKfree(pbsm_idx);
+ GDKfree(oids);
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+ }
+
+ for (i = 0; i < USHRT_MAX; i++) {
+ pbsm_idx[i].count = 0;
+ pbsm_idx[i].offset = 0;
+ }
+
+ for (i = 0; i < USHRT_MAX; i++) {
+ tmpCount[i] = 0;
+ }
+
+ // count pbsm values per cell
+ for (i = 0; i < n; i++) {
+ unsigned char cellx = ((x[i] - minx)/(maxx - minx))*UCHAR_MAX;
+ unsigned char celly = ((y[i] - miny)/(maxy - miny))*UCHAR_MAX;
+ sht cell = ((((unsigned short) cellx) << shift)) | ((unsigned
short) celly);
+ pbsm_idx[cell - SHRT_MIN].count++;
+ }
+
+ // compute the offset values before filling in the oid array
+ pbsm_idx[0].offset = 0;
+ for (i = 1; i < USHRT_MAX; i++) {
+ pbsm_idx[i].offset = pbsm_idx[i-1].offset + pbsm_idx[i-1].count;
+ }
+
+ // fill in the oid array
+ for (i = 0; i < n; i++) {
+ unsigned char cellx = ((x[i] - minx)/(maxx - minx))*UCHAR_MAX;
+ unsigned char celly = ((y[i] - miny)/(maxy - miny))*UCHAR_MAX;
+ sht cell = ((((unsigned short) cellx) << shift)) | ((unsigned
short) celly);
+ unsigned long position = pbsm_idx[cell - SHRT_MIN].offset +
tmpCount[cell - SHRT_MIN];
+ oids[position] = i + seqbase;
+ tmpCount[cell - SHRT_MIN]++;
+ }
+
+ GDKfree(tmpCount);
+
+ return MAL_SUCCEED;
+}
+
+
+static char *
+PBSMcreateindex (const dbl *x, const dbl *y, BUN n, double minx, double maxx,
double miny, double maxy, oid seqbase) {
+ FILE *f;
+ unsigned long i;
+ clock_t t = clock();
+
+ assert (pbsm_idx == NULL && oids == NULL);
+
+ createFilenames("batgeom.Filter");
+
+ if ((pbsm_idx = GDKmalloc(USHRT_MAX * sizeof(pbsm_ptr))) == NULL)
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+
+ for (i = 0; i < USHRT_MAX; i++) {
+ pbsm_idx[i].count = 0;
+ pbsm_idx[i].offset = 0;
+ }
+
+ /* have we precomputed the grid? */
+ if ((f = fopen(idxFilename, "rb"))) {
+ if (fread(pbsm_idx, sizeof(pbsm_idx[0]), USHRT_MAX, f) !=
USHRT_MAX) {
+ fclose(f);
+ GDKfree(pbsm_idx);
+ throw(MAL, "batpbsm.contains16", "Could not read the
PBSM index from disk (source: %s)", idxFilename);
+ }
+ fclose(f);
+
+ if ((oids = GDKmalloc(n * sizeof(oid))) == NULL) {
+ GDKfree(pbsm_idx);
+ throw(MAL, "pbsm.createindex", MAL_MALLOC_FAIL);
+ }
+
+ if ((f = fopen(dataFilename, "rb"))) {
+ if (fread(oids, sizeof(oids[0]), n, f) != n) {
+ fclose(f);
+ GDKfree(pbsm_idx);
+ GDKfree(oids);
+ throw(MAL, "batpbsm.contains16", "Could not
read the PBSM index from disk (source: %s)", dataFilename);
+ }
+
+ fclose(f);
+
+ t = clock() - t;
+ fprintf(stderr, "[PBSM] Index loading: %d clicks - %f
seconds\n", (unsigned int)t, ((float)t)/CLOCKS_PER_SEC);
+
+ return MAL_SUCCEED;
+ } else {
+ GDKfree(pbsm_idx);
+ GDKfree(oids);
+ throw(MAL, "batpbsm.contains16", "Could not read the
PBSM index (.dat).");
+ }
+ }
+
+ /* No. Let's compute the grid! */
+ // version 1
+ if ( false && PBSMcomputeindex1(x, y, n, minx, maxx, miny, maxy,
seqbase) != MAL_SUCCEED)
+ throw(MAL, "pbsm.createindex", "Failed to compute index (1).");
+ //
+ // version 2
+ if ( true && PBSMcomputeindex2(x, y, n, minx, maxx, miny, maxy,
seqbase) != MAL_SUCCEED)
+ throw(MAL, "pbsm.createindex", "Failed to compute index (2).");
+
+ t = clock() - t;
+ fprintf(stderr, "[PBSM] Index population: %d clicks - %f seconds\n",
(unsigned int)t, ((float)t)/CLOCKS_PER_SEC);
+
+ /* Save the index for future use (sloppiness acknowledged) */
+ if ((f = fopen(idxFilename, "wb"))) {
+ if (fwrite(pbsm_idx, sizeof(pbsm_idx[0]), USHRT_MAX,f) !=
USHRT_MAX) {
+ fclose(f);
+ GDKfree(pbsm_idx);
+ GDKfree(oids);
+ throw(MAL, "batpbsm.contains16", "Could not save the
PBSM index to disk (target: %s)", idxFilename);
+ }
+ fflush(f);
+ fclose(f);
+ }
+
+ if ((f = fopen(dataFilename, "wb"))) {
+ if (fwrite(oids, sizeof(oids[0]), n, f) != n) {
+ fclose(f);
+ GDKfree(pbsm_idx);
+ GDKfree(oids);
+ throw(MAL, "batpbsm.contains16", "Could not save the
PBSM index to disk (target: %s)", dataFilename);
+ }
+ fflush(f);
+ fclose(f);
+ }
+
+ return MAL_SUCCEED;
+}
+
+static char *
+PBSMarraycontains16(BAT **bres, const dbl *x, BAT *batx, const dbl *y, BAT
*baty, mbr *mbb, BUN n, double minx, double maxx, double miny, double maxy) {
+ unsigned long csize = 0, u;
+ oid *candidates;
+ unsigned char mbrcellxmin, mbrcellxmax, mbrcellymin, mbrcellymax, k,l;
+ int shift = sizeof(sht) * 8 / 2;
+ unsigned long i;
+ str msg;
+
+ /* assert calling sanity */
+ assert(*bres != NULL && x != NULL && y != NULL && batx != NULL && baty
!= NULL);
+ assert(batx->hseqbase == baty->hseqbase);
+
+ /* read the pbsm index to memory */
+ if (pbsm_idx == NULL || oids == NULL) {
+ /* the index has not been materialized/loaded yet */
+ if ((msg = PBSMcreateindex(x, y, n, minx, maxx, miny, maxy,
batx->hseqbase)) != MAL_SUCCEED)
+ return msg;
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
