Thread: I'm suppose to use this library but I'm confused on what exactly the data structure

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    47

    Red face I'm suppose to use this library but I'm confused on what exactly the data structure

    Hi guys I'm suppose to use this library to create a bigger application but I'm struggling trying to figure out how exactly this big data structure works together.


    I noticed the rules struct is a double linked list correct?>
    Which holds a char array.


    THere is also another doubly linekd list named names.
    Which holds a name array and also another struct named name_data.


    Okay so these 2 lists don't seem to be communicating with eachother but where I get lost is here:

    Code:
    // Global lists
    
    struct {
      struct names all;             // from all dependency lines
      struct names targets;         // from most recent dependency line
      struct name *primary;         // from first dependency line
    } names = { { NULL, NULL }, { NULL, NULL }, NULL };
    What exactly is this doing?
    Its a struct but whats the line:
    struct names all;
    struct names targets
    struct name *primary;
    and the names = {{NULL,NULL},{....}

    all mean?

    Thats where I'm getting lost.

    ANy help would be great!


    Code:
    /*--------------------------------------------------------------------------------*/
    
    /* Each target has a name, a list of sources, and a list of rules.
     *   The list of sources could be empty.
     *   The list of rules could be empty.
     * Each source could be a target, and each target could be a source.
     * A rule describes a command that could be issued to build a target.
     *   A rule is attached to each of the targets of the most recent dependency iine.
     * A list of sources is derived from one or more dependency lines.
     *   When a second dependency line is noticed for a target, should it replace the
     *   previous line, or add to it?  Should the following rules replace the previous
     *   rules, or add to them?
     * The rules are taken in order as seen, so a singly-linked list is ok.
     *   We only need the text of the command.  For simplicity, it retains the trailing
     *   newline from fgets().
     * We need the last modification time from stat().
     *   The access() function might be useful to see if a file exists.
     * The primary target is the first one seen.
     * The current targets are those listed on the most recent dependency line.
     * The error and warning messages can imitate Sun's make or GNU make.
     *   GNU make on Solaris is gmake.  Linux and Mac OS X use GNU make.
     */
    
    // List of Rules
    
    struct rule {
      struct rule *next;
      char *command;                // with trailing newline
    };
    
    struct rules {
      struct rule *head, *tail;
    };
    
    
    // List of Names, can be used for targets or sources
    
    /* C requires a forward declaration here. */
    struct name_data;
    
    struct name {                   // target or source
      struct name *next;
      char *name;
      struct name_data *name_data;
    };
    
    struct names {
      struct name *head, *tail;
    };
    
    
    // Data for each name
    
    struct name_data {
      char *name;
      struct names sources;         // list of sources
      struct rules rules;           // list of rules
      int stat_valid;               // 1/0 = true/false, as usual
      struct stat stat;             // info from stat()
      int printed;                  // 1/0 if rules already printed or not
    };
    
    
    // Global lists
    
    struct {
      struct names all;             // from all dependency lines
      struct names targets;         // from most recent dependency line
      struct name *primary;         // from first dependency line
    } names = { { NULL, NULL }, { NULL, NULL }, NULL };
    
    /*--------------------------------------------------------------------------------*/
    
    void *Malloc(size_t size);              // simple wrappers, example follows
    char *Strdup(char *str);
    
    struct name *find_name(char *name);     // example follows
    struct name_data *allocate_name_data(char *name);
    struct name *allocate_name(char *name); // example follows
    void append_name(struct names *names, struct name *name);
        // scan the list and avoid duplication
    
    struct rule *allocate_rule(char *command);
    void _append_rule(struct rules *rules, struct rule *rule);
    void append_rule(char *command);        // use current target, example follows
    int print_rule(struct rule *rule);      // return number of rules printed
    int print_rules(struct rules *rules);
    
    void append_source(char *name);         // use current target
    int print_source(struct name *source);  // return number of sources printed
    int print_sources(struct names *sources);
    
    void append_target(char *name, int start);
        // there might be more than one target on a dependency line
        // start == 1 indicates initialize the list, otherwise append
    int print_target(struct name *target);  // return number of rules printed
    int print_targets(char *msg);
    
    void parse(char *buf, char *word[]);    // modified from Project 6
    void read_file(char *filename);         // see above
    
    /*--------------------------------------------------------------------------------*/
    
    void *Malloc(size_t size)
    {
      void *p = malloc(size);
    
      if (p == NULL) { printf("failed: Malloc(): %s\n", strerror(errno)); exit(1); }
    
      return p;
    }
    
    /*--------------------------------------------------------------------------------*/
    
    struct name *find_name(char *name)
    {
      struct name *nm;
    
      for (nm = names.all.head; nm != NULL; nm = nm->next)
        {
          if (strcmp(name, nm->name) == 0)
            { break; }
        }
    
      return nm;
    }
    
    struct name *allocate_name(char *name)
    {
      struct name *p = Malloc(sizeof(struct name));
    
      p->next = NULL;
      p->name = Strdup(name);
      p->name_data = allocate_name_data(name);
    
      return p;
    }
    
    /*--------------------------------------------------------------------------------*/
    
    void _append_rule(struct rules *rules, struct rule *rule)
    {
      if (rules->head == NULL)      // empty list
        {
          rules->head = rules->tail = rule;
        }
      else
        {
          rules->tail->next = rule;
          rules->tail = rule;
        }
    }
    
    void append_rule(char *command)
    {
      struct rule *p = allocate_rule(command);
    
      _append_rule(&names.targets.head->name_data->rules, p);
    }
    
    /*--------------------------------------------------------------------------------*/

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Rules is a single linked list (it only has a next pointer, no previous pointer) - it does however have a head and tail so that inserts can be made at either end of the list - head points to the first element, tail at the last element.

    Code:
    struct {
      struct names all;             // from all dependency lines
      struct names targets;         // from most recent dependency line
      struct name *primary;         // from first dependency line
    } names = { { NULL, NULL }, { NULL, NULL }, NULL };
    Declare a unnamed struct, then declared a variable called names of that structure. The structure contains a linked list (struct names) "all" that holds, according to the comment, "all dependency lines". Then a "targets" linked list, which is the "most recent dependency line", and "primary", which is the name of the first target found in the makefile.

    The { NULL ... } bit initializes all the member variables to NULL - it is somewhat redundant, as global variables are initialized to zero, so it is only really needed in systems where NULL is not zero.

    struct names is defined above, as a single linked list:
    Code:
    struct name {                   // target or source
      struct name *next;
      char *name;
      struct name_data *name_data;
    };
    
    struct names {
      struct name *head, *tail;
    };
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data structure for french-english dictionary
    By officedog in forum C Programming
    Replies: 9
    Last Post: 03-20-2009, 01:43 AM
  2. Data Structure Eror
    By prominababy in forum C Programming
    Replies: 3
    Last Post: 01-06-2009, 09:35 AM
  3. Bitmasking Problem
    By mike_g in forum C++ Programming
    Replies: 13
    Last Post: 11-08-2007, 12:24 AM
  4. Data Structure Library for C
    By hzmonte in forum C Programming
    Replies: 5
    Last Post: 11-15-2005, 07:30 AM
  5. Data structure implementation
    By fkheng in forum C Programming
    Replies: 3
    Last Post: 07-31-2003, 07:44 AM