Answer to Question 39B-4

  void insertList(const ListCell* L, HashTable& T);

  //==========================================
  //             destroyList
  //==========================================
  // Delete all the cells in linked list L.
  //==========================================

  void destroyList(ListCell* L)
  {
    if(L != NULL)
    {
      destroyList(L->tail);
      delete L;
    }
  }

  //==========================================
  //             enlarge
  //==========================================
  // Double the size of the array in hash table
  // T.
  //==========================================

  void enlarge(HashTable& T)
  {
    int       oldSize = T.size;
    int       newSize = 2*oldSize;
    ListCell* oldA    = T.A;

    T = HashTable(newSize);
    for(int i = 0; i < oldSize; i++)
    {
      insertList(oldA[i], T);
      destroyList(oldA[i]);
    }
    delete [] oldA;
  }

  //==========================================
  //             insert
  //==========================================
  // Insert key x with associated item v into
  // hash table T.  If x is already a key in
  // T, then just replace its item by v.
  //==========================================

  void insert(const char* x, const char* v, HashTable& T)
  {
    if(T.load >= 2*T.size)
    {
       enlarge(T);
    }

    int h = strhash(x) % T.size;

    //-----------------------------------------
    // Handle the case where x is already
    // in the table.
    //-----------------------------------------

    for(ListCell* p = T.A[h]; p != NULL; p = p->tail)
    {
      if(strcmp(p->key, x) == 0)
      {
         p->item = v;
         return;
      }
    }

    //-----------------------------------------
    // Insert a new cell for new key x.
    //-----------------------------------------

    T.A[h] = new ListCell(x, v, T.A[h]);
  }

  //==========================================
  //             insertList
  //==========================================
  // For each (key, item) pair in linked list
  // L, insert that pair int hash table T.
  //==========================================

  void insertList(const ListCell* L, HashTable& T)
  {
    for(const ListCell* p = L; p != NULL; p = p->tail)
    {
      insert(p->key, p->item, T);
    }
  }