Очень странная проблема - C & Pthreads - PullRequest
0 голосов
/ 13 мая 2011

У меня очень странная проблема с этим фрагментом кода, извините, он довольно грязный.В основном это алгоритм PageRank.Каждая структура веб-страницы содержится в динамическом массиве «страниц».Вектор страниц пропускается по алгоритму до тех пор, пока его абсолютное значение (| P |) не станет меньше, чем «эпсилон».Теперь вопрос с линиями 195-201.Если я удаляю итерацию по массиву в этих строках (то есть пустой цикл while), это работает для случаев, которые требуют только одну итерацию.Однако, когда у меня есть цикл for (даже для случаев с одной итерацией), он выдает error6 (строка 179, отладка показывает e == NULL), даже не выполняя вставленный цикл.Я установил точки останова и т. Д., И все еще выдает ошибку6, даже не прочитав лишний код.Что тут происходит?Я довольно новичок в C и параллельном программировании, так что, возможно, это нечто фундаментальное.Был бы признателен за любую помощь!

формат ввода:

number_of_cores
number_of_pages
...
page_names
...
page_links

формат вывода:

...
page_rank
...

код

#include <assert.h>
#include <math.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static const double D = 0.85;
static const double EPSILON = 0.005;
int ncores;
int npages;
struct webpage** pages;
int maxdepth;

struct webpage* has(char s[20], int e);
void* threadf(void* ptr);
int quit(void);
double rec(int s, int f, int depth);




struct webpage {
    char name[20];
    double oldrank;
    double rank;
    struct node* in;
    int incount;
    int outcount;

};

struct node {
    struct webpage* data;
    struct node* next;
};

struct arg {
    int s;
    int f;
    int depth;
    double ret;
};

struct webpage*
has(char s[20], int e) {
    int p;
    for (p=0; p<e; ++p) {
        if (strcmp(s, pages[p]->name) == 0) {
            return pages[p];
        }
    }
    return NULL;
}

void *
threadf(void* ptr) {
    struct arg* curr = (struct arg*)ptr;
    curr->ret = rec(curr->s, curr->f, curr->depth);
}
int
quit(void) {
    int i;
    for(i=0; i<npages; ++i) {
        struct node* curr = pages[i]->in;
        struct node* next;
        while(curr != NULL) {
            next = curr->next;
            free(curr);
            curr = next;
        }
        free(pages[i]);
    }
    free(pages);
    return 0;
}

double 
seq(int s, int f) {
    double sum;
    sum = 0;
    int w;
    for (w=s; w<=f; w++) {
        struct webpage* curr = pages[w];
        double ser;
        ser = 0;
        struct node* currn = curr->in;
        while (currn != NULL) {
            struct webpage* n = currn->data;
            ser = ser + ((n->oldrank)/(n->outcount));
            currn = currn->next;
        }

        double temp = (((1-D)/npages) + (D*ser)); 
        sum = sum + pow((temp - curr->oldrank), 2);
        curr->oldrank = curr->rank;
        curr->rank = temp;
    }
    return sum;
}


double 
rec(int s, int f, int depth) {
    if (depth == maxdepth ) {
        return seq(s, f);
    } else {
        if (s < f){
            int m;
            m = (s+f)/2;
            struct arg l;
            struct arg r;
            l.s = s;
            l.f = m;
            l.depth = depth+1;
            r.s = m+1;
            r.f = f;
            r.depth = depth+1;
            pthread_t left, right;
            pthread_create(&left, NULL, threadf, (void*) &l);
            pthread_create(&right, NULL, threadf, (void*) &r);
            pthread_join(left, NULL);
            pthread_join(right, NULL);
            double res;
            res = l.ret + r.ret;
            return res;
        } 
        return seq(s, f);

    }
}

int
main(void) {
    if (scanf("%d", &ncores) != 1) {
        printf("error1\n");
        return quit();
    }
    if (scanf(" %d", &npages) != 1) {
        printf("error2\n");
        return quit();
    }
    int i;
    char n[20];
    pages = (struct webpage**)malloc(npages*sizeof(struct webpage*));
    for (i=0; i<npages; ++i) {

        if (scanf(" %c", n) != 1 || has(n, i) != NULL) {
            printf("error3\n");
            return quit();
        }
        pages[i] = (struct webpage*)malloc(sizeof(struct webpage));
        struct webpage* curr = pages[i];
        strcpy(curr->name, n);
        curr->oldrank = 1/npages;
        curr->in = NULL;
        curr->incount = 0;
        curr->outcount = 0;

    }

    int nedges;
    if (scanf(" %d", &nedges) != 1) {
        printf("error4\n");
        return quit();
    }
    for (i=0; i<nedges; ++i) {
        char f[20], t[20];
        if (scanf(" %s %s", f, t) != 2) {
            printf("error5\n"); 
            return quit();
        }
        char from[20], to[20];
        strcpy(from, f);
        strcpy(to, t);
        struct webpage* s = has(from, npages);
        struct webpage* e = has(to, npages);
        if (s == NULL || e == NULL) {
            printf("error6\n");
            return quit();
        }
        s->outcount++;
        e->incount++;
        struct node* new;
        new = (struct node*)malloc(sizeof(struct node));
        new->data = s;
        if (e->in == NULL) {
            e->in = new;
        } else {
            new->next = e->in;
            e->in = new;
        }
    }
    maxdepth = (log(ncores))/(log(2)) + 0.5;
    while (sqrt(rec(0, npages-1, 0)) > EPSILON){
        int c;
        for (c=0; c<npages; ++c) {
            struct webpage* curr = pages[c];
            curr->oldrank = curr->rank;
        }
    }
    int z;
    for (z=0; z<npages; ++z) {
        struct webpage* curr = pages[z];
        printf("%s %.4lf\n", curr->name, curr->rank);
    }

    return quit();

}

пример ввода:

8
4
a
b
c
d
4
a a

вывод:

error6

1 Ответ

1 голос
/ 14 мая 2011
char n[20];
[ ... ]
    if (scanf(" %c", n) != 1 || has(n, i) != NULL) {

Спецификатор формата %c для scanf читает только один символ.Таким образом, n состоит из введенного вами символа и любого мусора, который был в стеке до того, как вы вызвали scanf().Если вы используете %s, он будет состоять из введенного вами символа, плюс байта NUL для завершения строки и ненужного мусора.

Также обратите внимание, что вы можете ограничить количество символов scanf() читает с использованием спецификатора ширины, например:

scanf("%19s", n)

(имеется в виду: прочитать 19 символов и добавить байт NUL).В противном случае ваш буфер может переполниться, что может привести к выполнению произвольного кода (или, по крайней мере, к сбою при использовании не злонамеренными пользователями).

...