/*
* header file for SOFT3410 assignment four – “pagerank”
*
* DO NOT MODIFY THIS HEADER FILE
*/
#ifndef __PAGERANK_H
#define __PAGERANK_H
#include #define EPSILON 5E-3 /* forward type definitions */ /* data structure to store page information */ /* singly linked list node to store each page */ /* singly linked list to store all pages */ /* ========== FUNCTION PROTOTYPES ========== */ static void die(list* plist); /* ========================================== */ /** /** page *p = (page *) malloc(sizeof(page)); strcpy(p->name, name); return p; /** list* inlinks = p->inlinks; curr = inlinks->head; /** if (plist == NULL) /* failed to allocate memory */ plist->length = 0; return plist; /* frees a page linked list and all of the pages it contains. if (plist == NULL) /* null page list */ current = plist->head; free(plist); /* adds a page p to the start of page linked list pl. if (new_node == NULL) /* failed to allocate memory */ /* assign the page */ if (plist->head == NULL) /* empty list */ plist->head->next = NULL; else /* insert into the front */ plist->length++; /* front of the list */ /* adds a page p to the end of a page linked list pl node* new_node = (node *) malloc(sizeof(node)); if (new_node == NULL) /* failed to allocate memory */ if (plist->head == NULL) /* empty list */ plist->head->next = NULL; else /* insert into the end */ plist->length++; /* end of the list */ /* given a page linked list and a name, performs a forward iteration through node* curr = plist->head; /* helper function to read the list of pages into a page_list if (plist == NULL) /* null list */ *plist = page_list_create(); for (int i = 0; i < npages; i++)
{
if (fgets(buffer, BUFFER_SIZE, stdin) == NULL
|| sscanf(buffer, "%20s\n", name) != 1)
die(*plist);
if ((p = page_create(name, i)) == NULL)
die(*plist);
if (page_list_add_end(*plist, p) == NULL)
die(*plist);
}
}
/* helper function to read the list of edges into pages in a page_list
*
* buffer is used by fgets to read input (assumed to be of sufficient size)
*
* die() is called if there are any input errors
*/
static void _read_edges(char* buffer, list* plist, int* nedges)
{
node* node1;
node* node2;
char name1[NAME_SIZE];
char name2[NAME_SIZE];
char excess[NAME_SIZE];
if (fgets(buffer, BUFFER_SIZE, stdin) == NULL
|| sscanf(buffer, "%d %s\n", nedges, excess) != 1)
die(plist);
for (int i = 0; i < *nedges; i++)
{
if (fgets(buffer, BUFFER_SIZE, stdin) == NULL
|| sscanf(buffer, "%20s %20s %s\n", name1, name2, excess) != 2)
die(plist);
node1 = page_list_find(plist, name1);
node2 = page_list_find(plist, name2);
if (node1 == NULL || node2 == NULL) /* undefined pages */
die(plist);
/* Make sure we can add links into a page */
if (node2->page->inlinks == NULL && /* Add the link to the page */ node1->page->noutlinks++; /* function to read input in the correct format and handle input errors */ /* check for invalid input */ if (fgets(buffer, BUFFER_SIZE, stdin) == NULL if (fgets(buffer, BUFFER_SIZE, stdin) == NULL if (fgets(buffer, BUFFER_SIZE, stdin) == NULL /* read in the list of pages and edges once we have the main parameters */ _read_page_list(buffer, plist, *npages); #endif
#include
#include
#include
#include
#define NAME_SIZE 21
#define BUFFER_SIZE 101
typedef struct page page;
typedef struct node node;
typedef struct list list;
struct page
{
char name[21]; /* page name */
int index; /* index of the page */
int noutlinks; /* number of outlinks from this page */
list* inlinks; /* pointer to linked list of pages with inlinks to this page */
};
struct node
{
page* page; /* pointer to page data structure */
node* next; /* pointer to next page in list */
};
struct list
{
node* head; /* pointer to the head of the list */
node* tail; /* pointer to the tail of the list */
int length; /* length of the entire list */
};
static void page_destroy(page* p);
static page* page_create(char* name, int index);
static list* page_list_create(void);
static void page_list_destroy(list* plist);
static node* page_list_find(list* plist, char* name);
static void _read_edges(char* buffer, list* plist, int* nedges);
static void _read_page_list(char* buffer, list** plist, int npages);
static void read_input(list** plist, int* ncores, int* npages, int* nedges, double* damping_factor);
* Outputs ‘error’ to stdout
* cleans up the given page list and exits with non-zero status
*/
static void die(list* plist)
{
printf(“error\n”);
page_list_destroy(plist);
exit(1);
}
* Creates a page struct given a name and index
* > Returns NULL when name is too long or malloc fails
*/
static page* page_create(char* name, int index)
{
if (strlen(name) >= NAME_SIZE) /* page name too long */
return NULL;
if (p == NULL) /* failed to allocate memory */
return NULL;
p->index = index;
p->noutlinks = 0;
p->inlinks = NULL;
}
* Free the memory of used by a dynamically allocated specified page
*/
static void page_destroy(page* p)
{
if (p == NULL) /* empty page */
return;
if (inlinks != NULL) /* empty inlinks */
{
node *next;
node *curr;
while (curr != NULL)
{
next = curr->next;
free(curr);
curr = next;
}
free(inlinks);
}
free(p);
}
* Create an empty page linked list
* > Returns the created list, otherwise NULL if malloc fails
*/
static list* page_list_create(void)
{
list *plist = (list *) malloc(sizeof(list));
return NULL;
plist->head = NULL;
plist->tail = NULL;
}
* assumes pl was allocated by malloc
*/
static void page_list_destroy(list* plist)
{
node* next;
node* current;
return;
while (current != NULL)
{
next = current->next;
page_destroy(current->page);
free(current);
current = next;
}
}
* returns a pointer to the new front of the linked list
* returns NULL if malloc fails
*/
static node* page_list_add_front(list* plist, page* p)
{
node* new_node = (node *) malloc(sizeof(node));
return NULL;
new_node->page = p;
{
plist->head = new_node;
plist->tail = new_node;
plist->tail->next = NULL;
}
{
new_node->next = plist->head;
plist->head = new_node;
}
return plist->head;
}
* returns the new end of the linked list (where next = NULL)
* returns NULL if malloc fails
*/
static node* page_list_add_end(list* plist, page* p)
{
if (plist == NULL) /* null list */
return NULL;
return NULL;
else /* assign the page */
new_node->page = p;
{
plist->head = new_node;
plist->tail = new_node;
plist->tail->next = NULL;
}
{
plist->tail->next = new_node;
plist->tail = new_node;
new_node->next = NULL;
}
return plist->tail;
}
* the linked list and finds the item containing a page with the same name.
*
* returns NULL if no matching page can be found
*/
static node* page_list_find(list* plist, char* name)
{
if (plist == NULL) /* null list */
return NULL;
while (curr != NULL)
{
if (strcmp(curr->page->name, name) == 0)
return curr;
curr = curr->next;
}
return NULL;
}
*
* buffer is used by fgets to read input (assumed to be of sufficient size)
*
* ppl is a pointer to a pointer to a page_list, so that this function can
* modify the pointer value to point to the filled page list
*
* die() is called if there are any input errors
*/
static void _read_page_list(char* buffer, list** plist, int npages)
{
page* p;
char name[NAME_SIZE];
die(NULL);
(node2->page->inlinks = page_list_create()) == NULL)
die(plist);
if (page_list_add_front(node2->page->inlinks, node1->page) == NULL)
die(plist);
}
}
static void read_input(list** plist, int* ncores, int* npages,
int* nedges, double* dampener)
{
char buffer[BUFFER_SIZE];
|| sscanf(buffer, “%d\n”, ncores) != 1
|| *ncores == 0)
die(*plist);
|| sscanf(buffer, “%lf\n”, dampener) != 1
|| *dampener < 0 || fabs(*dampener) > 1)
die(*plist);
|| sscanf(buffer, “%d\n”, npages) != 1
|| *npages == 0)
die(*plist);
_read_edges(buffer, *plist, nedges);
}