|
<![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) 