// File: DoppioHashing.pseudocpp

/* 
   Contiene lo pseudocodice delle fiunzione Inserisci, Cerca, Elimina
   nel caso di doppio hashing, dove utilizziamo due diverse funzioni
   di hashing: hash() per trovare la posizione iniziale nella tavola,
   e hash2() per associare alla chiave uno specifico offset che
   stabilisce quanto sono lunghi i passi di scansione per quella data
   chiave.

   Si noti che ogni posizione della tavola puo' essere
   in tre stati: 'vuota', 'liberata', 'occupata' 
   dove 'occupata' significa che non e' vuota e non e' liberata.
*/


// Inserisce l'oggetto nella prima posizione vuota o liberata.

void Inserisci(Chiave K, InsAttr I)
{
  if (tavola_piena) return; // oppure rehash

  int probe = hash(K);
  int offset = hash2(K); 
  while (tavola[probe].stato != 'occupata')
    probe = (probe + offset) % dimTavola;
  tavola[probe] = (K,I);
}


// Considera la ricerca fallita se arriva ad una posizione 'vuota'.
// Nota per non bloccare la sequenza di scansione le posizioni liberate
// non vengono poste a 'vuota' ma nello stato speciale 'liberata'.

(bool,Chiave,InsAttr) Cerca(Chiave K, InsAttr I)
{
  int probe = hash(K);
  int offset = hash2(K); 
  while (tavola[probe].stato != 'vuota' && tavola[probe].key != K)
    probe = (probe + offset) % dimTavola;
 if (tavola[probe].stato != 'vuota') return (false,nil,nil);
 else return (true, tavola[probe].key, tavola[probe].insattr);
}


// Per non bloccare la sequenza di scansione le posizioni liberate
// non vengono poste a 'vuota' ma nello stato speciale 'liberata'.

void Elimina(Chiave K)
{
  int probe = hash(K);
  int offset = hash2(K); 
  while (tavola[probe].stato != 'vuota' && tavola[probe].key != K)
    probe = (probe + offset) % dimTavola;
  if (tavola[probe].key == K) tavola[probe] = 'liberata';
}