x_tree.h

X-tree的C++源码

	mbr[i] = entries[0].bounces[i];

    n = get_num();
    for (j = 1; j < n; j++)
    {
	for (i = 0; i < 2*dimension; i += 2)
	{
	    mbr[i]   = min(mbr[i],   entries[j].bounces[i]);
	    mbr[i+1] = max(mbr[i+1], entries[j].bounces[i+1]);
        }
    }

    return mbr;
}


template <class DATA>
float* XTDirNode<DATA>::calc_mbr(DirEntry<DATA> *de, int num_entries)
// Calculates the Minimal Bounding Rectangle for a set of Directory Entries 
{
    int i, j;
    float *mbr;
    
    mbr = new float[2*dimension];
    for (i = 0; i < 2*dimension; i++)
        mbr[i] = de[0].bounces[i];
    
    for (j = 0; j < num_entries; j++)
    {
        for (i = 0; i < 2*dimension; i += 2)
	{
	    mbr[i]   = min(mbr[i],   de[j].bounces[i]);
	    mbr[i+1] = max(mbr[i+1], de[j].bounces[i+1]);
	}
    }
    
    return mbr;
}


template <class DATA> 
void XTDirNode<DATA>::enter(DirEntry<DATA> *de)
{
    // ist ein Einfuegen ueberhaupt moeglich?
    if (get_num() > (capacity-1))
        error("XTDirNode::enter: called, but node is full", TRUE);
  
    // Eintrag an erste freie Stelle kopieren
    entries[num_entries] = *de;

    // jetzt gibts einen mehr
    num_entries++;

    // Eintrag freigeben, aber keine Nachfolgeknoten loeschen !!!!
    de->son_ptr = NULL;
    delete de;
}


template <class DATA>
void XTDirNode<DATA>::adapt_node(int mult)
// adapt node to a multiple of EXT_SIZE
{
    int i, n;
    int size, upper_border;
    int* intern_help;
    DirEntry<DATA> *new_entries;
        
    n = get_num();

    // insure adapting to a multiple of EXT_SIZE
    if (nodesize == 1)
    {
	size = 0;
	upper_border = 4;
    }
    else
    {
	size = nodesize;
	upper_border = EXT_SIZE*mult;
    }
    
    // adapt intern_block
    // allocate one more intern blocks than necessary to avoid memory conflicts in
    // read_from_buffer and write_to_buffer
    intern_help = new int[size+EXT_SIZE*mult+1];
    for (i = 0; i < nodesize; i++)
	intern_help[i] = intern_block[i];
    delete [] intern_block;
    intern_block = intern_help;

    // append new blocks to file
    for (i = 0; i < upper_border; i++)
	intern_block[nodesize+i] = my_tree->file->append_block(my_tree->block_buffer);

    nodesize = size + EXT_SIZE * mult;
    capacity = nodesize * block_capacity;
    
    new_entries = new DirEntry<DATA>[capacity];

    memcpy(new_entries, entries, n*sizeof(DirEntry<DATA>));

    // delete old entries
    for (i = 0; i < n; i++)
    {
	entries[i].bounces = NULL;
	entries[i].son_ptr = NULL;
    }
    delete [] entries;

    entries = new_entries;
}


template <class DATA> 
bool XTDirNode<DATA>::split(XTDirNode<DATA> **sn, int *dimen)
// splittet den aktuellen Knoten so auf, dass m mbrs nach sn verschoben
// werden und gibt TRUE zurueck, wenn der Split ausgefuehrt wird bzw. FALSE,
// wenn ein Supernode erstellt wird.
// In dimen wird die Split-Dimension an den aufrufenden Knoten zurueckgegeben, um dort
// die Split-History zu aktualisieren.
{
    int i, *distribution, dist, dist2, n, dim;
    float **mbr_array;
    float *r1, *r2;
    float a1, a2, o, overlap_relative;
    int *split_hist;
    DirEntry<DATA> *new_entries1, *new_entries2;
    int size_of_new_node;

#ifdef SHOWMBR
	split_000++;
#endif

    // no split, if node is supernode

    dim = 0;
	
    // wieviele sind denn nun belegt?
    n = get_num();

    // mbr_array allokieren und belegen
    mbr_array = new floatptr[n];
    split_hist = new int[n];
    for (i = 0; i < n; i++)
    {
	mbr_array[i] = entries[i].bounces;
	split_hist[i] = entries[i].history;
    }
    
    // Verteilung berechnen
    dist = XTNode<DATA>::topological_split(mbr_array, &distribution, &dim);

    // neues Datenarray erzeugen
    // --> siehe Konstruktor
    XTDirNode__dimension = dimension;
    XTDirNode__my_tree = my_tree;
    new_entries1 = new DirEntry<DATA>[capacity];
    new_entries2 = new DirEntry<DATA>[capacity];
    
    for (i = 0; i < dist; i++)
    {
	new_entries1[i] = entries[distribution[i]];
    }
    for (i = dist; i < n; i++)
    {
	new_entries2[i-dist] = entries[distribution[i]];
    }
    
    // Calculate the overlap size of the two mbrs
    r1 = calc_mbr(new_entries1, dist);
    r2 = calc_mbr(new_entries2, n-dist);
    o = overlap(dimension, r1, r2);
    a1 = area(dimension, r1);
    a2 = area(dimension, r2);
    overlap_relative = o / (a1+a2-o);
    
    if (overlap_relative > MAX_OVERLAP)
    {
	// topological split fails -> try overlap minimal split

        dist2 = XTNode<DATA>::overlap_free_split(mbr_array, split_hist, &distribution, &dim);
	
	if (dist2 != 0)
	{
	    // split_axis found
	    dist = dist2;
	    
	    // delete mbr_array and split history
	    delete [] mbr_array;
	    delete [] split_hist;
	    
	    // test for unbalanced nodes
	    if (((dist < (block_capacity*MIN_FANOUT)) || ((n-dist) < (block_capacity*MIN_FANOUT))))
	    {
		// dirnode has to be adapted to the size of the next greater multiple of EXT_SIZE
		adapt_node (((n/block_capacity+1) / EXT_SIZE) + 1);
		
		for (i = 0; i < n; i++)
		{
		    new_entries1[i].bounces = NULL;
		    new_entries1[i].son_ptr = NULL;                     
		    new_entries2[i].bounces = NULL;
		    new_entries2[i].son_ptr = NULL;                     
		}
		delete [] new_entries1;
		delete [] new_entries2;

                // Testausgabe
		printf("DIRECTORY SPLIT : Creating Supernode.\n");
		printf("Alter und neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);
		
		return FALSE;
	    }
	    else
	    {
		// nodes are balanced
		
		for (i = 0; i < dist; i++)
		{
		    new_entries1[i] = entries[distribution[i]];
		}
		for (i = dist; i < n; i++)
		{
		    new_entries2[i-dist] = entries[distribution[i]];
		}
		
		for (i = 0; i < n; i++)
		{
		    entries[i].son_ptr = NULL;
		}
		delete [] entries;
		
	        // decides, whether brother has to be a supernode or a regular directory node
		size_of_new_node = ((((n-dist)/block_capacity+1) / EXT_SIZE) + 1)*EXT_SIZE;
		if ((n-dist) < block_capacity)
		{
		    size_of_new_node = 1;
		}

		*sn = new XTDirNode<DATA>(size_of_new_node, my_tree);
	    
		(*sn)->son_is_data = son_is_data;
		(*sn)->level = level;

		// neue Datenarrays kopieren
		entries = new_entries1;
		(*sn)->entries = new_entries2;
		
		// Anzahl der Eintraege berichtigen
		num_entries = dist;
		(*sn)->num_entries = n - dist;  // muss wegen Rundung so bleiben !!

                // Testausgabe
                printf("DIRECTORY SPLIT : Balanced overlap free split.\n");
		printf("Alter Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);
		printf("Neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", (*sn)->num_entries, (*sn)->capacity, (*sn)->nodesize);
                 
		*dimen = dim;
	    }                
	}
    }
    else
    {
	// Datenarrays freigeben
	// da die Nachfolgeknoten aber nicht geloescht werden sollen
	// werden vor dem Aufruf von delete noch alle Pointer auf NULL gesetzt
	for (i = 0; i < n; i++)
	{
	    entries[i].son_ptr = NULL;
	}
	delete [] entries;

	// decides, whether brother has to be a supernode or a regular directory node
	if ((n-dist) >= block_capacity)
	{
	    *sn = new XTDirNode<DATA>( (((((n-dist)/block_capacity+1) / EXT_SIZE) + 1)*EXT_SIZE), my_tree);
	}
	else
	{
	    *sn = new XTDirNode<DATA>( 1, my_tree);
	}
   
	(*sn)->son_is_data = son_is_data;
	(*sn)->level = level;
		
	// neue Datenarrays kopieren
	entries = new_entries1;
	(*sn)->entries = new_entries2;
	
	// Anzahl der Eintraege berichtigen
	num_entries = dist;
	(*sn)->num_entries = n - dist;  // muss wegen Rundung so bleiben !!

        // Testausgabe
	printf("DIRECTORY SPLIT : Topological Split.\n");
	printf("Alter Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);
	printf("Neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", (*sn)->num_entries, (*sn)->capacity, (*sn)->nodesize);

	*dimen = dim;
    }

    return TRUE;
}


template <class DATA> 
int XTDirNode<DATA>::choose_subtree(float *mbr)
{
    int i, j, n, follow, minindex, *inside, inside_count, *over;
    float *bmbr, old_o, o, omin, a, amin, f, fmin;

    n = get_num();

    // faellt d in einen bestehenden Eintrag ?
    inside_count = 0;
    inside = new int[n];
    over = new int[n];
    for (i = 0; i < n; i++)
    {
	switch (entries[i].section(mbr))
	{
	case INSIDE:
	    inside[inside_count++] = i;
	    break;
	}
    }

    if (inside_count == 1)
    // Fall 1: Rechteck faellt genau in einen Eintrag
	follow = inside[0];
    else if (inside_count > 1)
    // Fall 2: Rechteck faellt in mehrere Eintrag --> nimm den
    // mit der geringsten Flaeche (volumen!!!)
    {
	fmin = MAXFLOAT;
	//printf("Punkt in %d von %d MBRs \n",inside_count,n);
	for (i = 0; i < inside_count; i++)
	{
	    f = area(dimension, entries[inside[i]].bounces);
	    if (f < fmin)
	    {
		minindex = i;
      		fmin = f;
       	    }
       	}
	follow = inside[minindex];
    }
    else
    // Fall 3: Rechteck faellt in keinen Eintrag -->
    // fuer Knoten, die auf interne Knoten zeigen:
    // nimm den Eintrag, der am geringsten vergroessert wird;
    // bei gleicher Vergroesserung:
    // nimm den Eintrag, der die geringste Flaeche hat
    //
    // fuer Knoten, die auf Datenknoten zeigen:
    // nimm den, der die geringste Ueberlappung verursacht
    // bei gleicher Ueberlappung:
    // nimm den Eintrag, der am geringsten vergroessert wird;
    // bei gleicher Vergroesserung:
    // nimm den Eintrag, der die geringste Flaeche hat
    {
       	if (son_is_data)
	{
            omin = MAXREAL;
	    fmin = MAXREAL;
	    amin = MAXREAL;
	    for (i = 0; i < n; i++)
	    {
		// berechne die mbr, wenn mbr in entries[i] eingefuegt wird
		enlarge(dimension, &bmbr, mbr, entries[i].bounces);

		// calculate area and area enlargement
		a = area(dimension, entries[i].bounces);
		f = area(dimension, bmbr) - a;

		// calculate overlap before enlarging entry_i
		old_o = o = 0.0;
		for (j = 0; j < n; j++)
		{
		    if (j != i)
		    {
			old_o += overlap(dimension,
					 entries[i].bounces,
					 entries[j].bounces);
			o += overlap(dimension,
				     bmbr,
				     entries[j].bounces);
		    }
	        }
	        o -= old_o;

	        // is this entry better than the former optimum ?
	        if ((o < omin) ||
		    (o == omin && f < fmin) ||
		    (o == omin && f == fmin && a < amin))
	        {
	       	    minindex = i;
		    omin = o;
		    fmin = f;
		    amin = a;
	        }
	        delete [] bmbr;
	    }
        }
        else
        {
	    fmin = MAXREAL;
	    amin = MAXREAL;
	    for (i = 0; i < n; i++)
	    {
	        // berechne die mbr, wenn mbr in entries[i] eingefuegt wird
	        enlarge(dimension, &bmbr, mbr, entries[i].bounces);

	        // calculate area and area enlargement
	        a = area(dimension, entries[i].bounces);
	        f = area(dimension, bmbr) - a;

	        // is this entry better than the former optimum ?
	        if ((f < fmin) ||
		    (f == fmin && a < amin))
	        {
	       	    minindex = i;
		    fmin = f;
	            amin = a;
	        }
	        delete [] bmbr;
	    }
        }

	// berechne die neue mbr und schreib sie in den Eintrag
	enlarge(dimension, &bmbr, mbr, entries[minindex].bounces);
	memcpy(entries[minindex].bounces, bmbr,
	       dimension * 2 * sizeof(float));
	follow = minindex;
	delete [] bmbr;

	// leider muss jetzt der Block auch geschrieben werden
	dirty = TRUE;
    }

    delete [] inside;
    delete [] over;

    return follow;
}


template <class DATA> 
R_OVERFLOW XTDirNode<DATA>::insert(DATA *d, XTNode<DATA> **sn, int *dim)
// dim references a variable in the father node, so the split history can be updated there
{
    int follow, dimen;
    XTNode<DATA> *succ, *new_succ;
    XTDirNode<DATA> *brother;
    DirEntry<DATA> *de;
    R_OVERFLOW ret;
    float *mbr,*nmbr;    

    dimen = 0;
    
    // Einfuegepfad waehlen
    mbr = d->get_mbr();
    follow = choose_subtree(mbr);
    delete [] mbr;

    // Sohn laden
    succ = entries[follow].get_son();

    // insert d into son
    ret = succ->insert(d, &new_succ, &dimen);
    *dim = dimen;
    if (ret != NONE)
    // if anything happend --> update bounces of entry "follow"
    {
        mbr = succ->get_mbr();
        memcpy(entries[follow].bounces, mbr, sizeof(float) * 2*dimension);
        delete [] mbr;
    }