[WikiDyd] [TitleIndex] [WordIndex

Projekt dirdu: moduł kontenera

[wiki:Jimp1/ProgramowanieProceduralne strona projektu]

Pierwsza wersja kodu kontenera i testy

Zrealizujemy ten moduł w postaci multilisty, w której główna lista będzie zawierała klucze (nazwy plików lub katalogów), a listy podrzędne będą zawierały wyliczenia ścieżki, które zawierają obiekty o takich nazwach.

Plik nagłówkowy:

   1 /* container.h
   2    version 0.1, 11-10-2005
   3    jstar@iem.pw.edu.pl
   4 */
   5                                                                                                                                                
   6 typedef enum
   7 { CONTAINER_OK, CONTAINER_NO_MEMORY } container_err_type;
   8                                                                                                                                                
   9 typedef enum
  10 { AS_FILE, AS_DIRECTORY } entry_type;
  11                                                                                                                                                
  12 typedef struct path_elem
  13 {                               /* informacja o sciezce - lista podrzedna */
  14   char *path;
  15   entry_type type;
  16   struct path_elem *nextp;
  17 } path_elem_t;
  18                                                                                                                                                
  19 typedef struct name_elem
  20 {                               /* informacja o nazwie - lista nadrzędna */
  21   char *name;
  22   path_elem_t *paths;
  23   struct name_elem *nextn;
  24 } name_elem_t;
  25                                                                                                                                                
  26 typedef struct
  27 {                               /* typ danych dla interfejsu */
  28   char *name;
  29   int no_paths;
  30   char **paths;
  31 } group_t;
  32                                                                                                                                                
  33 void add (char *name, char *path, entry_type type);     /* dodaje element do kontenera, inicjuje iterator po grupach */
  34                                                                                                                                                
  35 void init_group_iterator (void);        /* inicjuje iterator po grupach */
  36                                                                                                                                                
  37 group_t *next_group (void);     /* zwraca następną grupę, lub NULL, jeśli nie ma więcej */

Plik z funkcjami

   1 /* container.c
   2    version 0.1, 11-10-2005
   3    jstar@iem.pw.edu.pl
   4 */
   5                                                                                                                                                
   6 #include "container.h"
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <stdio.h>
  10                                                                                                                                                
  11 container_err_type container_err = CONTAINER_OK;
  12                                                                                                                                                
  13 static name_elem_t *head = NULL;        /* kontener */
  14                                                                                                                                                
  15 static name_elem_t *iterator = NULL;
  16                                                                                                                                                
  17 static group_t g;               /* zmienna robocza, uzywana w next_group */
  18                                                                                                                                                
  19 path_elem_t *
  20 new_path_element (char *path, entry_type type, path_elem_t * next)
  21 {
  22   path_elem_t *n = malloc (sizeof *n);
  23   if (n == NULL || (n->path = malloc (strlen (path) + 1)) == NULL) {
  24     container_err = CONTAINER_NO_MEMORY;
  25     if (n != NULL)
  26       free (n);
  27     return next;
  28   }
  29   else {
  30     strcpy (n->path, path);
  31     n->type = type;
  32     n->nextp = next;
  33     return n;
  34   }
  35 }
  36                                                                                                                                                
  37 path_elem_t *
  38 addpath (path_elem_t * list, char *path, entry_type type)
  39 /* dodaje nowy element do listy sciezek */
  40 {
  41   return new_path_element (path, type, list);
  42 }
  43 
  44 name_elem_t *
  45 new_name_element (char *name, char *path, entry_type type, name_elem_t * next)
  46 /* dodaje nowy element główny */
  47 {
  48   name_elem_t *e;
  49                                                                                                                                                
  50   if ((e = malloc (sizeof *e)) == NULL) {
  51     container_err = CONTAINER_NO_MEMORY;
  52     return next;
  53   }
  54   if ((e->name = malloc (strlen (name) + 1)) == NULL) {
  55     container_err = CONTAINER_NO_MEMORY;
  56     return next;
  57   }
  58   strcpy (e->name, name);
  59   e->paths = addpath (NULL, path, type);        /* uwaga! po tym powinno się sprawdzic container_err ! */
  60   e->nextn = next;
  61   return e;
  62 }
  63                                                                                                                                                
  64 void
  65 add (char *name, char *path, entry_type type)
  66 /* dodaje element do kontenera, inicjuje iterator po grupach */
  67 {
  68   name_elem_t *e;
  69                                                                                                                                                
  70   if (head == NULL || strcmp (head->name, name) > 0) {
  71     e = new_name_element (name, path, type, head);
  72     if (container_err == CONTAINER_OK) {
  73       head = e;
  74     }
  75   }
  76   else {
  77     e = head;
  78     while (e->nextn != NULL && strcmp (name, e->nextn->name) > 0)
  79       e = e->nextn;
  80     if (e->nextn == NULL || strcmp (name, e->nextn->name) < 0)
  81       /* trzeba wstawic nowy element za e */
  82       e->nextn = new_name_element (name, path, type, e->nextn);
  83     else
  84       /* e->nextn->name == name   => tylko dodajemy path */
  85       e->nextn->paths = addpath (e->nextn->paths, path, type);
  86   }
  87   iterator = head;
  88 }
  89                                                                                                                                                
  90 void
  91 init_group_iterator (void)
  92 /* inicjuje iterator po grupach */
  93 {
  94   iterator = head;
  95 }
  96 
  97 group_t *
  98 next_group (void)
  99 /* zwraca następną grupę, lub NULL, jeśli nie ma więcej */
 100 {
 101   path_elem_t *pit;
 102   int all_paths_length = 0;     /* total length of the table containing all paths */
 103   int i;
 104   if (iterator == NULL)
 105     return NULL;
 106                                                                                                                                                
 107   free (g.name);
 108   free (g.paths[0]);
 109                                                                                                                                                
 110   /* calculate how much memory needs to be allocated for all paths (+descriptions) */
 111   pit = iterator->paths;
 112   while (pit != NULL) {
 113     all_paths_length += strlen (pit->path + 4 + 1);     /* 4 for " (d)" or " (f)", 1 for '\0' */
 114     pit = pit->nextp;
 115   }
 116   if ((g.paths[0] = malloc (all_paths_length)) == NULL) {
 117     container_err = CONTAINER_NO_MEMORY;
 118     return NULL;
 119   }
 120   /* now copy paths to allocated memory */
 121   pit = iterator->paths;
 122   i = 0;
 123   while (pit != NULL) {
 124     int this_length =
 125       sprintf (g.paths[i], "%s %s", pit->path,
 126                (pit->type == AS_FILE ? "(f)" : "(d)"));
 127     i++;
 128     pit = pit->nextp;
 129     if (pit != NULL)
 130       g.paths[i] = g.paths[i - 1] + this_length;
 131   }
 132   iterator = iterator->nextn;
 133   return &g;
 134 }
 135                                                                                                                                                
 136 void
 137 print_all (FILE * out)
 138 /* do testowania - wypisuje cala liste */
 139 {
 140   name_elem_t *e = head;
 141   while (e != NULL) {
 142     path_elem_t *p = e->paths;
 143     fprintf (out, "NAME: %s\n", e->name);
 144     while (p != NULL) {
 145       fprintf (out, "\tAS %s IN PATH: %s\n",
 146                (p->type == AS_FILE ? "file     " : "directory"), p->path);
 147       p = p->nextp;
 148     }
 149     e = e->nextn;
 150   }
 151 }

Program testujący

   1 #include "container.h"
   2                                                                                                                                                
   3 #include <stdio.h>
   4                                                                                                                                                
   5 main( int argc, char **argv ) {
   6   char n[1024],
   7        p[1024];
   8   int t;
   9                                                                                                                                                
  10   while( ! feof( stdin ) ) {
  11     scanf( "%s %i %s", n, &t, p );
  12     fprintf( stderr, "got %s (%c) -> %s\n", n, (t==0?'f':'d'), p );
  13                                                                                                                                                
  14     fprintf( stderr, "adding..." );
  15                                                                                                                                                
  16     add( n, p, t );
  17                                                                                                                                                
  18     fprintf( stderr, "done\nList after:\n" );
  19                                                                                                                                                
  20     print_all( stderr );
  21                                                                                                                                                
  22   }
  23                                                                                                                                                
  24   return 0;
  25 }

I dane do niego

ala 0 src
zosia 1 src
ala 0 docs
ala 1 test/stare/src
zosia 1 test
jasio 0 src

Wyniki testu pokazują, że źle działa funkcja add:

got ala (f) -> src
adding...done
List after:
NAME: ala
  AS file      IN PATH: src
got zosia (d) -> src
adding...done
List after:
NAME: ala
  AS file      IN PATH: src
NAME: zosia
  AS directory IN PATH: src
got ala (f) -> docs
adding...done
List after:
NAME: ala
  AS file      IN PATH: src
NAME: ala
  AS file      IN PATH: docs
NAME: zosia
  AS directory IN PATH: src
got ala (d) -> test/stare/src
adding...done
List after:
NAME: ala
  AS file      IN PATH: src
NAME: ala
  AS directory IN PATH: test/stare/src
  AS file      IN PATH: docs
NAME: zosia
  AS directory IN PATH: src
got zosia (d) -> test
adding...done
List after:
NAME: ala
  AS file      IN PATH: src
NAME: ala
  AS directory IN PATH: test/stare/src
  AS file      IN PATH: docs
NAME: zosia
  AS directory IN PATH: test
  AS directory IN PATH: src
got jasio (f) -> src
... [ obcięte] ...

Test pokazuje, że gdy nazwa już występuje na poczatku listy, to nowa ściezka dodawana jest nie do tej nazwy, ale do nowego elementu listy. Analiza kodu funkcji add:

   1 void
   2 add (char *name, char *path, entry_type type)
   3 /* dodaje element do kontenera, inicjuje iterator po grupach */
   4 {
   5   name_elem_t *e;
   6                                                                                                                                                
   7   if (head == NULL || strcmp (head->name, name) > 0) {
   8     e = new_name_element (name, path, type, head);
   9     if (container_err == CONTAINER_OK) {
  10       head = e;
  11     }
  12   }
  13   else {
  14     e = head;
  15     while (e->nextn != NULL && strcmp (name, e->nextn->name) > 0)
  16       e = e->nextn;
  17     if (e->nextn == NULL || strcmp (name, e->nextn->name) < 0)
  18       /* trzeba wstawic nowy element za e */
  19       e->nextn = new_name_element (name, path, type, e->nextn);
  20     else
  21       /* e->nextn->name == name   => tylko dodajemy path */
  22       e->nextn->paths = addpath (e->nextn->paths, path, type);
  23   }
  24   iterator = head;
  25 }

pokazuje, że istotnie jest ona nieprawidłowa: w pierwszym if-ie add sprawdza, czy elementu nie trzeba wstawić na początek listy, ale w drugim zaczyna porównywanie nazw od drugiego elementu, nie badając już pierwszego. Można to poprawić tak:

   1 void
   2 add (char *name, char *path, entry_type type)
   3 /* dodaje element do kontenera, inicjuje iterator po grupach */
   4 {
   5   name_elem_t *e;
   6                                                                                                                                                
   7   if (head == NULL || strcmp (head->name, name) > 0) {
   8     e = new_name_element (name, path, type, head);
   9     if (container_err == CONTAINER_OK) {
  10       head = e;
  11     }
  12   }
  13   else if( strcmp( head->name, name ) == 0 ) {
  14     head->paths= addpath( head->paths, path, type );
  15   }
  16   else {
  17     e = head;
  18     while (e->nextn != NULL && strcmp (name, e->nextn->name) > 0)
  19       e = e->nextn;
  20     if (e->nextn == NULL || strcmp (name, e->nextn->name) < 0)
  21       /* trzeba wstawic nowy element za e */
  22       e->nextn = new_name_element (name, path, type, e->nextn);
  23     else
  24       /* e->nextn->name == name   => tylko dodajemy path */
  25       e->nextn->paths = addpath (e->nextn->paths, path, type);
  26   }
  27   iterator = head;
  28 }

I to załatwia sprawę:

oer:~/dydaktyka/wyklady/jimp2/dirdu> ./t1 < test1
got ala (f) -> src
adding...done
List after:
NAME: ala
        AS file      IN PATH: src
got zosia (d) -> src
adding...done
List after:
NAME: ala
        AS file      IN PATH: src
NAME: zosia
        AS directory IN PATH: src
got ala (f) -> docs
adding...done
List after:
NAME: ala
        AS file      IN PATH: docs
        AS file      IN PATH: src
NAME: zosia
        AS directory IN PATH: src
got ala (d) -> test/stare/src
adding...done
List after:
NAME: ala
        AS directory IN PATH: test/stare/src
        AS file      IN PATH: docs
        AS file      IN PATH: src
NAME: zosia
        AS directory IN PATH: src
got zosia (d) -> test
adding...done
List after:
NAME: ala
        AS directory IN PATH: test/stare/src
        AS file      IN PATH: docs
        AS file      IN PATH: src
NAME: zosia
        AS directory IN PATH: test
        AS directory IN PATH: src
... [ obcięte ] ...

W dalszej kolejności testujemy poprawność funkcji next_group. Wykorzystujemy do tego program drugi:

   1 #include "container.h"
   2                                                                                                     
   3 #include <stdio.h>
   4                                                                                                     
   5 void format_group( group_t *g, FILE *out )
   6 {
   7   if( g != NULL ) {
   8     register int i;
   9     fprintf (out, "NAME: %s\n", g->name);
  10     for( i= 0; i < g->no_paths; i++ )
  11       fprintf (out, "\t%s\n", *( g->paths+i ) );
  12   }
  13 }
  14                                                                                                     
  15 main( int argc, char **argv ) {
  16   char n[1024],
  17        p[1024];
  18   int t;
  19                                                                                                     
  20   group_t *g;
  21                                                                                                     
  22   fprintf( stderr, "Reading input..." );
  23                                                                                                     
  24   while( scanf( "%s %i %s", n, &t, p ) == 3 ) {
  25     add( n, p, t );
  26   }
  27   fprintf( stderr, "done\nList:\n" );
  28   print_all( stderr );
  29                                                                                                     
  30   fprintf( stderr, "Starting iteration over groups\n" );
  31   init_group_iterator();
  32                                                                                                     
  33   while( (g= next_group()) != NULL ) {
  34     fprintf( stderr, "\nNext group:\n" );
  35     format_group( g, stderr );
  36   }
  37                                                                                                     
  38   return 0;
  39 }

Aby zautomatyzować testy wykonujemy pierwszy szkic makefile

COPT += -DCONTAINER_DEBUG
                                                                                                    
all: test1 test2
                                                                                                    
test1: t1 test1
  ./t1 < test1
                                                                                                    
test2: t2 test1
  ./t2 < test1
                                                                                                    
t1: container.c t1_container.c utils.c
  ${CC} ${COPT} -o $@ $+
                                                                                                    
t2: container.c t2_container.c utils.c
  ${CC} ${COPT} -o $@ $+

Testy pozwalają nam ulepszyć nieco kod.

[wiki:Jimp1/DirduContainer W miare ostateczna wersja kontenera]


2015-09-23 06:43