Erreur de segmentation Skiplist

**kandro** · 07/10/2013, 20h58

Bonsoir,
Pour mon cours d'algorithmique il m'a été demandé d'implémenter une skiplist, j'ai un soucis dans la méthode de ma classe SkipList qui réalise l'insertion des données.

Voici mon code pour la classe SkipList :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdlib>
#include <time.h>
 
#include "skiplist.hpp"
 
using namespace std;
 
SkipList::SkipList()
    :level(0),size(0),proba(.5)
{
    head = new Node(0, 32);
 
    srand (time(NULL));
}
 
SkipList::~SkipList()
{
    Node *prec = NULL;
 
    for(Node *n = head; n != NULL; n = n->getNextAtLevel(0))
    {
        delete prec;
        prec = n;
    }
 
    delete prec;
}
 
bool SkipList::contains(const int &key) const
{
    Node *current = head;
 
    for(int i = level; i >= 0; --i)
        if(current->getNextAtLevel(i))
        {
            while(current->getNextAtLevel(i)->getKey() < key)
            {
                current = current->getNextAtLevel(i);
 
                if(!current->getNextAtLevel(i))
                    break;
            }
 
            if(current->getNextAtLevel(i))
                if(current->getNextAtLevel(i)->getKey() == key)
                    return true;
        }
 
    return false;
}
 
void SkipList::add(const int &key)
{	
    unsigned nodeSize = 1;
 
    unsigned val = 1;
 
    while(val)
    {
        val = rand()%2;
        if(val)
            ++nodeSize;
    }
 
    if(nodeSize > level)
        level = nodeSize - 1;
 
    Node *newNode = new Node(key, nodeSize);
    Node *current = head;
 
    for(int i = level; i >= 0; --i)
    {
        if(!current->getNextAtLevel(i))
        {
            if(i < nodeSize)
                current->setNextAtLevel(i, newNode);
 
            continue;
        }
 
        while(1)
        {
            if(current->getNextAtLevel(i))
            {
                if(current->getNextAtLevel(i)->getKey() < key)
                    current = current->getNextAtLevel(i);
                else
                    break;
            }
            else
                break;
        }
 
        if(current->getNextAtLevel(i))
            if(current->getNextAtLevel(i)->getKey() == key)
            {
                delete newNode;
                return;
            }
 
        if(current->getNextAtLevel(i))
            if(current->getNextAtLevel(i)->getKey() > key)
            {
                newNode->setNextAtLevel(i, current->getNextAtLevel(i));
                current->setNextAtLevel(i, newNode);
            }
 
        ++size;
    }
}

Et celui de ma classe Node :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "node.hpp"
 
Node::Node(const int &key, const unsigned &size)
	:key(key), size(size)
{
	next = new Node *[size];
 
	for(unsigned i = 0; i < size; ++i)
		next[i] = NULL;
}
 
Node::~Node()
{
	delete []next;
}
 
unsigned Node::getSize() const
{
	return size;
}
 
int Node::getKey() const
{
	return key;
}
 
Node* Node::getNextAtLevel(const unsigned &level) const
{
	return next[level];
}
 
void Node::setNextAtLevel(const unsigned &level, Node *node)
{
	next[level] = node;
}

Le problème semble se situer à la ligne 85 de SkipList.cpp, en effet l'appel de la fonction getNextAtLevel() renvoi 0x21 sous linux et 0xabababab sous windows. J'ai eu beau retourné le problème dans tous les sens je ne vois pas où se situe mon erreur.

**koala01** · 08/10/2013, 01h44

Salut,

Avant d'aller plus loin, as-tu conscience de ce que fait le bout de code (qui apparait dans SkipList entre la ligne 81 et la ligne 92), un peu épuré ci-dessous

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
while(1)
{
    /* ...*/
}

Si, déjà, tu trouves la bonne réponse, il y a de grandes chances que tu trouves la solution à ton problème

Au fait, tu devrais peut être réfléchir un tout petit peux aux deux premières lignes de ma signature, car j'ai vraiment l'impression que ton algorithme est... bancal à la base

Il faut dire que je suis plus ou moins allergique aux mots cle continue de manière générale et au mot clé break quand il ne se trouve pas dans un switch->case

Ah, tant qu'à faire, quelle méthode de représentation d'algorithme utilises tu

**gnto** · 08/10/2013, 09h23

Bonjour,

Complétement d'accord avec koala01, pourquoi casser les séquences ? Les break dans les boucles me donne l'impression qu'il n'y a pas de pilote a bord, on code a vu. Idem sur les return en pleine méthode, c'est "pour moi", moins lisible.

Dans le destructeur, je pense que tu delete un pointeur nul. Et je pense qu'une boucle conditionnel type while serait plus appropriée. Une boucle for est une boucle dont on maitrise le nombre d'iterations avant running.

**Astraya** · 08/10/2013, 09h44

Bonjour,
En plus de plusoyer tout mes collègues ici présent. Ton crash vient du fait que tu réalises un "out of bound" sur ton tableau next dans la classe Node.
En effet, tu ne vérifies jamais que level est bien inférieur à size. Donc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Node* Node::getNextAtLevel(const unsigned &level) const
{
	return next[level];
}

retourne n'importe quoi car ici level est plus grand que size. Si ton level > size retourne null_ptr.

**jblecanard** · 08/10/2013, 10h00

Salut !

Je suis en grande partie d'accord avec les précédentes interventions. Je ne suis pas contre continue et break comme Koala, ils sont utiles et ont du sens quand ils sont bien utilisés, mais là tu en abuses car il y a plusieurs endroits où tu pourrais t'en passer et écrire des boucles plus claires.

Tu utilises aussi beaucoup et pas très bien les one-liners (boucles conditionnelles sans accolades). Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if(current->getNextAtLevel(i))
  if(current->getNextAtLevel(i)->getKey() == key)
  {
    delete newNode;
    return;
  }

Qui s'écrit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if(current->getNextAtLevel(i) && current->getNextAtLevel(i)->getKey() == key)
{
  delete newNode;
  return;
}

Dans le destructeur, je pense que tu delete un pointeur nul.

Alors juste pour la culture, delete sur un pointeur nul est parfaitement valide. Attention cependant à ne pas confondre un pointeur nul et un pointeur qui a été delete. Je suppose que tu débutes alors ne prend pas mal nos petits "reproches", ce sont des bonnes habitudes à prendre pour ne pas t'arracher les cheveux par la suite

. Tu pourras corriger tes soucis en réorganisant ton code et en étant attentif au point soulevé par Astraya.

**kandro** · 08/10/2013, 13h17

Bonjour,
Merci à vous tous pour vos réponses.

Je suis conscient que le code que je vous ait envoyé n'est pas très "propre", javais commencé par faire des tests du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if(current->getNextAtLevel(i) && && current->getNextAtLevel(i)->getKey() == key)

Idem dans mon while, seulement lorsque je voyais qu'appeler la méthode getKey() renvoyais une erreur, j'ai pensé que d'appeler cet méthode à partir d'un pointeur nul pouvais causer mon bug. C'est pourquoi j'ai commencé par faire le test de nullité et ensuite le test sur la valeur.

Je voulais surtout remercier Astraya qui ayant mit le doigt sur mon erreur m'a fait comprendre que mon algorithme était faux. En effet, il est normalement pas normal d'envoyer une valeur supérieure à la taille du nœud dans getNextAtLevel. L'erreur se situe lors de l'insertion du nouveau nœud, en effet je ne teste pas si l'indice du niveau courant est inférieur à la taille du nœud à insérer avant de l'insérer. J'ai donc corrigé cela en faisant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if(current->getNextAtLevel(i) && current->getNextAtLevel(i)->getKey() > key && i < nodeSize)
{
	newNode->setNextAtLevel(i, current->getNextAtLevel(i));
	current->setNextAtLevel(i, newNode);
}

**gnto** · 08/10/2013, 13h19

Envoyé par jblecanard

Alors juste pour la culture, delete sur un pointeur nul est parfaitement valide. Attention cependant à ne pas confondre un pointeur nul et un pointeur qui a été delete. Je suppose que tu débutes alors ne prend pas mal nos petits "reproches", ce sont des bonnes habitudes à prendre pour ne pas t'arracher les cheveux par la suite

. Tu pourras corriger tes soucis en réorganisant ton code et en étant attentif au point soulevé par Astraya.

Je crois pas avoir dit que ce soit invalide. Faire un while(true) ou while(1) n'est pas invalide, c'est juste maladroit.

On peut avoir un débat sur optimisation de ligne de code, d'instruction Vs lisibilité, maitrise du code et algorithmie.

**jblecanard** · 08/10/2013, 13h59

Envoyé par gnto

Je crois pas avoir dit que ce soit invalide. Faire un while(true) ou while(1) n'est pas invalide, c'est juste maladroit.

En effet, mais faire un delete d'un pointeur nul n'a rien de maladroit, au contraire, c'est très pratique dans les destructeurs car on n'a pas besoin de tester le pointeur, ça le rend le code plus lisible.

**koala01** · 08/10/2013, 15h25

Envoyé par gnto

Bonjour,

Complétement d'accord avec koala01, pourquoi casser les séquences ? Les break dans les boucles me donne l'impression qu'il n'y a pas de pilote a bord, on code a vu. Idem sur les return en pleine méthode, c'est "pour moi", moins lisible.

En fait, je ne suis très certainement pas un fanatique du SESE (Single Entry Single Exist), bien au contraire : s'il faut faire un return à l'intérieur d'une boucle parce que cela ne sert strictement à rien de continuer, je n'ai strictement aucune objection à le faire.

C'est vraiment au break et au continue dans les boucles que je suis allergique

Simplement parce que les boucles sont plus ou moins interchangeables et qu'il est tout à fait possible de choisir un autre type de boucle qui pourrait prendre une condition de sortie plus précise que la boucle pour, qui est itérative

Erreur de segmentation Skiplist

C++

Discussions similaires

Partager

Partager