/******************************** search.c ********************************* Purpose: Implement the searching stage of the MPHF algorithm. Provenance: Written and tested by Q. Chen and E. Fox, March 1991. Edited and tested by S. Wartik, April 1991. Notes: The other two stages must have been performed already. **/ #include #include "types.h" #include "pmrandom.h" #include "support.h" #ifdef __STDC__ extern int fit_pattern( arcsType* arcs, verticesType* vertices, int i, char* disk, intSetType *primes, intSetType* slotSet ); extern void initialize_search( arcsType* arcs, verticesType* vertices, char* disk ); extern void initialize_primes( int n, intSetType* primes ); #else extern int fit_pattern(); extern void initialize_search(); extern void initialize_primes(); #endif /************************************************************************* searching( arcsType*, verticesType* ) Return: int -- NORM on success, ABNORM on failure. Purpose: Search a MPHF for the key set. Notes: The "prec" field is used as the "vertex visited" marker. The slotSet variable actually is only used in fit_pattern(). However, since storage for it must be dynamically allocated, and since this routine calls fit_pattern() repeatedly, it's declared here, where storage can be allocated just once. **/ int searching( arcs, vertices ) arcsType *arcs; verticesType *vertices; { int i, /* Each vertex in the VS list. */ searching_tries = 0, /* Running count of searching tries. */ status = ABNORM; /* Condition variable. */ char *disk; /* Simulated hash table. */ intSetType primes, /* Table of primes for pattern shifts. */ slotSet; /* Set of hash addresses. */ disk = (char*) owncalloc( arcs->no_arcs, sizeof(char) ); slotSet.intSetRep = (int*) owncalloc( vertices->maxDegree, sizeof(int) ); initialize_primes( arcs->no_arcs, &primes ); while ( (searching_tries++ < SEARCHINGS) && (status == ABNORM) ) { status = NORM; i = vertices->vsHead; /* Get the highest-level vertex. */ initialize_search( arcs, vertices, disk ); while ( i != NP ) { /* Fit keys of level of vertex i onto the disk. */ vertices->vertexArray[i].prec = VISIT; if ( fit_pattern(arcs, vertices, i, disk, &primes, &slotSet) == ABNORM ) { status = ABNORM; /* Search failed at vertex i. Try */ break; /* a new pattern. */ } else /* Search succeeded. Proceed to next node. */ i = vertices->vertexArray[i].succ; } } free( disk ); free( (char *)slotSet.intSetRep ); free( (char *)primes.intSetRep ); return(status); } /************************************************************************* fit_pattern( arcsType*, verticesType*, int, char*, intSetType*, intSetType* ) Return: int -- NORM if a fit is found, ABNORM if not. Purpose: Compute a pattern for a level and fit it onto the hash table. If a pattern is found, then the g values for vertices on that level are set appropriately, and the slots on the disk for the vertices are filled. **/ int fit_pattern( arcs, vertices, i, disk, primes, slotSet ) arcsType *arcs; /* in: The arcs in the graph. */ verticesType *vertices;/* in out: The vertices in the graph. */ int i; /* in: Vertex's location in vertex-selected list. */ char *disk; /* in out: The hash table (disk). */ intSetType *primes, /* in: Prime number table */ *slotSet; /* Set of slots taken by keys in this pattern. */ { arcType *arc; /* Current arc. */ int shift, /* Shift value for the pattern. */ side, /* Side indicator (0 or 1). */ hashAddress, /* Hash address being tried. */ fitOK = ABNORM, /* Fit condition variable. */ no_fits = 0; /* Running count of attempts to fit. */ side = (i >= vertices->no_vertices/2); shift = primes->intSetRep[pmrandom() % primes->count]; while ( (no_fits++ < arcs->no_arcs) && (fitOK == ABNORM) ) { fitOK = NORM; slotSet->count = 0; /* Initialize slot set to empty. */ arc = vertices->vertexArray[i].first_edge; while ( arc != 0 ) { /* Iterate over all arcs in this level. */ /* If the key for arc is at this level, */ /* get its hash address. */ if ( vertices->vertexArray[arc->h12[(side+1)%2]].prec == VISIT ) { hashAddress = abs(arc->h0 + vertices->vertexArray[arc->h12[0]].g + vertices->vertexArray[arc->h12[1]].g ) % arcs->no_arcs; /* See if this key can be put at hashAddress. */ if ( disk[hashAddress] != EMPTY ) { /* Collision. Clear */ int k; /* marked slots in disk.*/ for ( k = 0; k < slotSet->count; k++ ) disk[slotSet->intSetRep[k]] = EMPTY; /* Try a new shift. */ vertices->vertexArray[i].g = ( vertices->vertexArray[i].g + shift ) % arcs->no_arcs; fitOK = ABNORM; break; } else { /* Success. Remember the address, */ /* and mark the table. */ slotSet->intSetRep[slotSet->count++] = hashAddress; disk[hashAddress] = FULL; } } /* end of if */ arc = arc->next_edge[side]; /* Hash next arc. */ } /* end of inner while */ } /* end of outer while */ return(fitOK); } /************************************************************************* initialize_search( arcsType*, verticesType*, char* ) Return: void Purpose: Prepare for the search stage: Put random values in all the g fields, mark all vertices un-visited, and empty the disk. **/ void initialize_search( arcs, vertices, disk ) arcsType *arcs; /* in: arcs. */ verticesType *vertices; /* out: vertices. */ char *disk; /* out: the hash table. */ { int i; setseed( pmrandom() ); /* Set the seed. */ for ( i = 0; i < vertices->no_vertices; i++ ) { vertices->vertexArray[i].g = pmrandom() % arcs->no_arcs; vertices->vertexArray[i].prec = NOTVISIT; } /* Reset the hash table.*/ for ( i = 0; i < arcs->no_arcs; disk[i++] = EMPTY ); } /************************************************************************* initialize_primes( int, intSetType* ) Return: void Purpose: Set up the prime number table. **/ void initialize_primes( n, primes ) int n; /* in: the size of the hash table. */ intSetType *primes; /* out: the prime number table. */ { int i, testingNumber = 2; /* Testing number for possible prime numbers. */ primes->intSetRep = (int*) owncalloc( PRIMES, sizeof(int) ); primes->intSetRep[0] = 1; /* 1 is added to the table, although it */ primes->count = 1; /* is not a prime. */ while ( (testingNumber++ < n) && (primes->count < PRIMES) ) { if ( n % testingNumber != 0 ) { /* Get first PRIMES-1 */ for ( i = testingNumber - 1; i > 0; i-- ) /* prime numbers. */ if ( testingNumber % i == 0 ) break; if ( i == 1 ) primes->intSetRep[primes->count++] = testingNumber; } /* end of if */ } /* end of while */ }