|
<![CDATA[
int insert( input, n, r, A )
dataarray input, r; int n, *A;
{ extern int m, m2;
int d, i, ia, ib, iup, j;
datarecord tempr;
if( m < n ) return(0);
for( i=0; i<m2; i++ ) A[i] = 0;
for( i=0; i<n; i++ ) A[ input[i].k % m2 ]++;
/* Shellsort input array based on collision counts */
for ( d=n; d>1; ) {
if (d<5) d = 1;
else d = (5*d-1)/11;
for ( i=n-1-d; i>=0; i-- ) {
tempr = input[i];
ia = tempr.k % m2;
for ( j=i+d; j<n && (A[ia] < A[ib=input[j].k % m2] ||
A[ia] == A[ib] && ia > ib); j+=d )
input[j-d] = input[j];
input[j-d] = tempr;
}
}
for( i=0; i<n; i=iup ) {
ia = input[i].k % m2;
iup = i + A[ia];
for( A[ia]=ib=1; ib < 9*m; A[ia] += ib++ ) {
for( j=i; j<iup && empty(r[hashfunction(A[ia],input[j].k)]);
j++ ) r[hashfunction(A[ia],input[j].k)] = input[j];
if( j >= iup ) break;
for( j--; j >= i; j-- )
r[hashfunction(A[ia],input[j].k)].k = NOKEY;
}
if( ib >= 9*m )
/* Cannot build optimal hashing table with m and m2 */
return(0);
}
return(1);
}
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (3316.ins.c) 