/* HASHIND(3.0) PRODUCE HASH ARRAY INDEX 25.07.87+02.08.88 ------------------------------------------------------------------ 0TYPE: 0 FUNCTION 0DECLARATION: 0 DCL HASHIND ENTRY(CHAR(*) VAR, (*) CHAR(*) VAR) RETURNS(BIN FIXED); 0REFERENCE: 0 HASHIND(,) 0PARAMETERS: 0 HASH_KEY - HASH KEY FOR INDEX PRODUCING OBJECT_KEY - ARRAY OF OBJECT KEYS (INDEXATION SHOULD START FROM 1) 0VALUE: 0 HASH INDEX PRODUCED FROM HASH KEY AND INDICATING EITHER AN EMPTY CELL IN OBJECT KEY ARRAY OR A CELL CONTAINING OBJECT KEY IDENTICAL TO HASH KEY (ZERO RETURNED VALUE INDICATES HASHIND FAILURE WHEN THE ATTEMPT IS MADE TO ALLOCATE NEW KEY IN COMPLETELY FILLED OBJECT KEY ARRAY). 0EXAMPLES: 0 AVAILABLE FROM DEBUGGING LOGOUT. 0NOTES: 0 - EMPTY OBJECT KEY INDICATES AN EMPTY CELL IN ARRAY. - ARRAY OF OBJECT KEYS SHOULD CONTAIN AT LEAST ONE EMPTY CELL; THIS CONDITION SHOULD MANDATORY BE CHECKED BY CALLING PROGRAM, AS FAR AS ITS CHECKING BY HASHIND IS TIME CONSUMING (NUMBER OF CHECKS AMOUNTING TO DOUBLED DIMENSION OF OBJECT KEYS ARRAY). - TO IMPROVE (MINIMIZE) THE OPERATION TIME IT IS RECOMMENDED THAT THE DIMENSION VALUE OF OBJECT KEY ARRAY SHOULD BE A SIMPLE NUMBER (TO DECREASE THE NUMBER OF COLLISIONS). - TO IMPROVE (MINIMIZE) THE OPERATION TIME IT IS RECOMMENDED THAT THE OBJECT KEY ARRAY SHOULD NEVER BE FILLED OVER 75% OF ITS FULL CAPACITY, LEST THE NUMBER OF COLLISIONS AND HENCE THE SEARCH TIME MAY INCREASE DRAMMATICALLY. 1START FUNCTION *//* 0 DEBUG: PROC OPTIONS(MAIN); */ HASHIND: PROC(HASH_KEY,OBJECT_KEY) RETURNS(BIN FIXED); /* 0PARAMETERS */ 0 DCL HASH_KEY CHAR(*), OBJECT_KEY(*) CHAR(*) VAR; /* 0WORKING VARIABLES */ 0 DCL KEY_LENGTH BIN FIXED BASED(P), 1 WORKING_KEY BASED(P), 2 LENGTH BIN FIXED, 2 TEXT (KEY_LENGTH REFER(LENGTH)), BIT_SYMB BIT(8) BASED(Q), I BIN FIXED(31) BASED(R), R PTR INIT(ADDR(Q)), (OBJECTS_MAX, HASH_INDEX) BIN FIXED, HASH_SUM BIN FIXED(31) INIT(0); /* 0SET OVERLAY POINTERS */ 0 P=ADDR(HASH_KEY); Q=ADDR(WORKING_KEY.TEXT); /* 0COMPUTE HASH SUM OF SUPPLIED HASH KEY */ 0 DO I=I TO I+KEY_LENGTH-1; HASH_SUM=HASH_SUM+BIT_SYMB; END; /* 0PRODUCE PRIMARY HASH INDEX */ 0 OBJECTS_MAX=DIM(OBJECT_KEY,1); HASH_INDEX=MOD(HASH_SUM,OBJECTS_MAX); /* 1PRODUCE SECONDARY HASH INDEX (HASH SEARCH) *//* 0 PUT EDIT('HASH_SUM=',HASH_SUM)(X(12),A,P'(5)9') ('PRIM_HASH_IND=',HASH_INDEX+1)(X(3),A,P'99'); K=HASH_INDEX; */ 0 I=MOD(HASH_SUM,OBJECTS_MAX-2); DO J=1 TO OBJECTS_MAX WHILE((OBJECT_KEY(HASH_INDEX+1)^='')& (OBJECT_KEY(HASH_INDEX+1)^=HASH_KEY)); HASH_INDEX=MOD(HASH_INDEX+J*I,OBJECTS_MAX); /* SEARCH_STEPS=SEARCH_STEPS+1; */ END; /* 0PRODUCE SECONDARY HASH INDEX (LEANEAR SEARCH) */ 0 IF (J=OBJECTS_MAX+1) THEN DO; DO J=1 TO OBJECTS_MAX WHILE((OBJECT_KEY(J)^='')& (OBJECT_KEY(J)^=HASH_KEY)); /* SEARCH_STEPS=SEARCH_STEPS+1; */ END; /* 0FORM LEANEAR SEARCHED HASH INDEX (-1 INDICATES SEARCH FAILURE) *//* 0 SEARCH_TYPE=1; */ 0 HASH_INDEX=J*(J<=OBJECTS_MAX)-1; END; /* 0RETURN FUNCTION VALUE TO THE POINT OF INVOCATION (0 INDIC FAILURE) *//* 0 SEARCH_TYPE=SEARCH_TYPE+(HASH_INDEX^=K); IF (HASH_INDEX^=K) THEN PUT EDIT('SEC_HASH_IND=',HASH_INDEX+1)(X(3),A,P'99'); PUT EDIT('OBJECT_KEY(',HASH_INDEX+1,')=',OBJECT_KEY(HASH_INDEX+1)) (COL(88),A,P'99',A,A); */ 0 RETURN(HASH_INDEX+1); /* 0FINISH FUNCTION */ 0 END HASHIND; /* 1DEBUG FUNCTION *//* 0 DCL HASH_KEY(23) CHAR(10) VAR INIT('VLADIMIR', 'VLADIMIR', 'MARIA', '*ABC*', 'DANIEL', 'NATALIA', '*BCA*', 'MIKHAIL', 'KOMA', '*CAB*', 'VICTOR', 'VICTOR', 'INNA', '*BAC*', 'SASHA', 'OLGA', '*CBA*', 'ALEXANDER', 'ILIA', '*ACB*', 'ANASTASIYA', 'ANASTASIYA', 'DOROTHY'), SEARCH_COMMENT(0:2) CHAR(28) INIT('PRIMARY', 'SECONDARY (HASH SEARCHED)', 'SECONDARY (LEANEAR SEARCHED)'), OBJECT_KEY(19) CHAR(10) VAR INIT((19)''), (SEARCH_TYPE, SEARCH_STEPS, FILLING_COUNTER INIT(0)) BIN FIXED; 0 DCL EJECT ENTRY(FILE, BIN FIXED, BIN FIXED) RETURNS(BIN FIXED), PRNTTTL ENTRY(CHAR(*) VAR, CHAR(1) VAR, FILE, BIN FIXED, BIN FIXED); 0 F1: FORMAT(SKIP,A(19)); 1 CALL PRNTTTL('HASHIND(3.0) PRODUCE HASH ARRAY INDEX', '',SYSPRINT,1,0); 0 DO L=1 TO 23; PUT EDIT('ITERATION NUMBER:',L) (SKIP(EJECT(SYSPRINT,29,2+3*(MOD(L,2)=0)*(L>2))), A(19),P'99'); SEARCH_TYPE=0; SEARCH_STEPS=1; M=HASHIND(HASH_KEY(L),OBJECT_KEY); PUT EDIT('ITERATION TIME:', TRANSLATE('SE.TND',TIME(),'****SETND'))(R(F1),A) ('HASH KEY:',HASH_KEY(L))(R(F1),A) ('ARRAY FILLING:',100*FILLING_COUNTER/19,'%') (R(F1),P'999V.9',A) ('SEARCH STEPS:',SEARCH_STEPS)(R(F1),P'99') ('HASH INDEX:',M)(R(F1),P'99'); IF (M=0) THEN PUT EDIT('FAILURE INDICATOR')(X(12),A); ELSE PUT EDIT(SEARCH_COMMENT(SEARCH_TYPE))(X(12),A); FILLING_COUNTER=FILLING_COUNTER+(OBJECT_KEY(M)=''); OBJECT_KEY(M)=HASH_KEY(L); PUT EDIT('HASH ARRAY:')(SKIP,R(F1)) (('OBJECT_KEY(',N,')=',OBJECT_KEY(N) DO N=1 TO 19)) (SKIP,(19)(SKIP,X(3),A,P'99',A,A)); 0 END DEBUG; */