function to place a key in one of its possible positions * tableID: table in which key has to be placed, also equal to function according to which key must be hashed * cnt: number of times function has already been called in order to place the first input key * n: maximum number of times function can be recursively called before stopping and declaring presence of cycle */
| 46 | * n: maximum number of times function can be recursively |
| 47 | called before stopping and declaring presence of cycle */ |
| 48 | void place(int key, int tableID, int cnt, int n) |
| 49 | { |
| 50 | /* if function has been recursively called max number |
| 51 | of times, stop and declare cycle. Rehash. */ |
| 52 | if (cnt==n) |
| 53 | { |
| 54 | printf("%d unpositioned\n", key); |
| 55 | printf("Cycle present. REHASH.\n"); |
| 56 | return; |
| 57 | } |
| 58 | |
| 59 | /* calculate and store possible positions for the key. |
| 60 | * check if key already present at any of the positions. |
| 61 | If YES, return. */ |
| 62 | for (int i=0; i<ver; i++) |
| 63 | { |
| 64 | pos[i] = hash(i+1, key); |
| 65 | if (hashtable[i][pos[i]] == key) |
| 66 | return; |
| 67 | } |
| 68 | |
| 69 | /* check if another key is already present at the |
| 70 | position for the new key in the table |
| 71 | * If YES: place the new key in its position |
| 72 | * and place the older key in an alternate position |
| 73 | for it in the next table */ |
| 74 | if (hashtable[tableID][pos[tableID]]!=INT_MIN) |
| 75 | { |
| 76 | int dis = hashtable[tableID][pos[tableID]]; |
| 77 | hashtable[tableID][pos[tableID]] = key; |
| 78 | place(dis, (tableID+1)%ver, cnt+1, n); |
| 79 | } |
| 80 | else //else: place the new key in its position |
| 81 | hashtable[tableID][pos[tableID]] = key; |
| 82 | } |
| 83 | |
| 84 | /* function to print hash table contents */ |
| 85 | void printTable() |