Genomgång kodprov oktober 2017

Skillnaden mellan proven på förmiddagen och eftermiddagen var att i det ena provet tillhandahöll listan en extern iterator för att söka efter hyllor, och i det andra provet en intern iterator. I ena provet gick det att iterera över en lista t.ex. så här:

iter_t *iter = list_iterator(list);
while (iter_has_next(iter))
  {
    ... = iter_next(iter);
    ...
  }
iter_delete(iter);

Och i det andra t.ex. så här:

int shelf_cmp(void *shelf, void *shelf_name)
{
  shelf_t *s = shelf;
  return strcmp(s->name, (char *)shelf_name) == 0;
}

shelf_t found = list_find(list, shelf_cmp, some_name);

Det kan tyckas lite meckigare att skapa en funktion och använda funktionspekare, men denna lösning kräver ingen minneshantering och har färre rader kod, så jag bedömde dem därför som likvärdiga.

Ovanstående kompliceras som sagt något av manuell minneshantering. I alla fall där vi behåller VN eller HN i någon datatstruktur måste VN och HN hållas vid liv och frigöras först när programmet tar slut. I de fall där VN och HN inte sparas måste strängarna frigöras för att undvika minnesläckageHar du löst uppgiften korrekt modulo minneshanteringen har du fått rest.

Det utdelade programmet gör följande uppstädning vid avslut:

/// Tear down
tree_apply(db, delete_lists, NULL);
tree_delete(db);
tree_delete(shelves);

Den första raden tar bort allt minne i alla listor i trädet db. Den andra raden tar bort trädet db. Den sista raden tar bort trädet shelves men dess innehåll tas aldrig bort. Beroende på vad som stoppas in i shelves i en lösning kan olika förändringar av denna logik komma på fråga. En enkel lösningen som jag använder i lösningsförslaget nedan är att skapa kopior av strängarna och utöka logiken för att ta städa bort shelves.

shelf_t *find_shelf_for_good(tree_t *db, char *good_name, char *shelf_name)
{
  list_t *shelves = tree_get(db, good_name);
  iter_t *iter = list_iterator(shelves);

  while (iter_has_next(iter))
    {
      shelf_t *shelf = iter_next(iter);
      if (strcmp(shelf->name, shelf_name) == 0)
        {
          iter_delete(iter); /// Många har glömt denna iter_delete()!
          return shelf;
        }
    }
  iter_delete(iter);

  // Not found!
  return NULL;
}

Först visar jag en lösning som läcker minne.

do
  {
    if (answer) free(answer);

    char *goods_name = ask_question_string("Mata in namnet på en vara:");
    char *shelf_name = ask_question_string("Mata in namnet på en hylla:");
    int amount = ask_question_int("Mata in ett antal:");

    list_t *list = tree_get(db, goods_name);

    /// Steg 1: Kolla om shelf_name redan har använts för någon tidigare vara
    char *owner = tree_get(shelves, shelf_name);
    /// Om det fanns en tidigare vara, kolla om det är samma som goods_name
    bool same_owner = owner && strcmp(owner, goods_name) == 0;

    // If we are seeing this goods for the first time
    if (list == NULL)
      {
        list = list_new();
        tree_insert(db, goods_name, list);
        /// Nedanstående rad skall inte köras här -- bara om shelf_name inte har använts förut!
        /// tree_insert(shelves, shelf_name, goods_name);
      }

    /// Om hyllan redan är i bruk
    if (owner)
      {
        /// Om vi använder hyllan till samma sorts vara
        if (same_owner)
          {
            /// Steg 4: Hitta rätt hylla
            shelf_t *shelf = find_shelf_for_good(db, owner, shelf_name);
            /// Steg 6: Uppdatera antalet
            shelf->amount += amount;
          }
        /// Steg 3: ingenting
      }
    else
      {
        /// Steg 5
        list_append(list, shelf_new(shelf_name, amount));
        /// Hyllan var inte i bruk, så lägg till den i shelves
        tree_insert(shelves, shelf_name, goods_name);
      }

    answer = ask_question_string("Fler? (ja/nej)");
  }
while (starts_with(answer, "#-----") == 0 || strcmp(uppercase(answer), "JA") == 0);

Samma kod som ovan med några få rader ändrade/tillagda för korrekt minneshantering. För att slippa komplicerade flaggor som fångar under vilka omständigheter vi behåller goods_name använder vi strdup() vid insättning i db, och avslutar varje loop med free(goods_name). Detta medför dock att de varunamn som lagras i shelves och de som lagras i db inte är samma, vilket i sin tur innebär att vi måste lägga till ett ytterligare steg vid borttagning av shelves. Detta är enkelt att kopiera från existerande kod (delete_shelves).

do
  {
    if (answer) free(answer);

    char *goods_name = ask_question_string("Mata in namnet på en vara:");
    char *shelf_name = ask_question_string("Mata in namnet på en hylla:");
    int amount = ask_question_int("Mata in ett antal:");

    list_t *list = tree_get(db, goods_name);

    char *owner = tree_get(shelves, shelf_name);
    bool same_owner = owner && strcmp(owner, goods_name) == 0;

    if (list == NULL)
      {
        list = list_new();
        tree_insert(db, strdup(goods_name), list); /// strdup!
      }

    if (owner)
      {
        if (same_owner)
          {
            shelf_t *shelf = find_shelf_for_good(db, owner, shelf_name);
            shelf->amount += amount;
          }
        free(shelf_name); /// We did not store the shelf_name!
    }
    else
      {
        list_append(list, shelf_new(shelf_name, amount));
        tree_insert(shelves, shelf_name, strdup(goods_name)); /// strdup!
      }

    /// Always remove goods name because it is strdup'd into the trees
    free(goods_name);

    answer = ask_question_string("Fler? (ja/nej)");
  }
while (starts_with(answer, "#-----") == 0 || strcmp(uppercase(answer), "JA") == 0);

if (answer) free(answer);

tree_apply(db, print_goods, NULL);

/// Tear down
tree_apply(db, delete_lists, NULL);
tree_delete(db);
tree_apply(shelves, delete_strings, NULL); /// Remove all values in shelves tree
tree_delete(shelves);

Där delete_strings() är definierad på detta vis:

void delete_strings(char *key, void *string, void *p)
{
  free(string);
}

Observera att det går alldeles utmärkt att lösa uppgiften utan strdup() och delete_string()! Det kräver istället att anropen till free(shelf_name) och free(goods_name) distributeras över koden. Vi tar bort ett inläst hyllnamn om det redan fanns sparat och ett varunamn i det fall vi ser att varan redan finns. Båda lösningarna förekommer i inlämningarna.

Det förklaras på mail som kommer till dig som fått rest.

Förvånansvärt många har missuppfattat shelves och har trott att det är en avbildning av namn på hyllor på shelf_t-pekare. Dessa har förmodligen brottats med kraschande program eftersom den sträng med varunamn som returnerats från tree_get() har tolkats som en pekare och en int.

/// Exempel från ett faktiskt kodprov (modulo namn)
shelf_t *shelf = tree_get(shelves, shelf_name);

Många verkar helt ha missat existensen av shelves, eller så har man missuppfattat hur shelves fungera och till slut givit upp och försökt lösa uppgiften utan hjälp av shelves. Detta har i regel lett till väldigt krångliga lösningar med jobba anrop till tree_apply(). Dessa har tyvärr ofta varit felaktiga.

Några har missat att anropa iter_delete() för att ta bort iteratorn. Vissa har kommit ihåg att ta bort iteratorn efter iterator-loopen, men gjort en return innifrån iterator-loopen, precis som i min kod ovan, och där glömt att städa upp iteratorn.

Några har missat att ta bort goods_name och/eller shelf_name i de fall när de inte sparas.

Några använt == istället för strcmp() för strängjämförelse. Observera att i C betyder detta jämför adresserna och inte jämför strängarna. En sådan jämförelse kommer aldrig vara true i detta program med mindre än att vi frigör strängar för tidigt.

/// Exempel från ett faktiskt kodprov (modulo namn)
if (shelf->name == shelf_name) ...

Några som har använt strcmp() verkar ha glömt att funktionen returnerar 0 när två strängar är lika.