Thread: need help with some weird bug.

Hi guys.
I need some help with understanding what's wrong with my code.
basically, my assignment is to write a system for managing a radio station.
let me give you some background first.
the code is composed of four classes:
Song: each song has a name, a composer and a singer, and has a few segments: INTRO,VERSE,CHORUS,TRANSITION, while each represents a different length string of chars.
Playlist: a multiset of songs, and a pointer to a RadioStatistics instance (see below).
RadioStation: a set of Songs (will represent the station database), and a list of Playlists, each playlist holds a few songs from the database.
RadioStatistics: can only be instantiate once, this object gather statistics; it has two maps: one that counts how many times a song was played, and second that counts how many times each singer was played. (the key is the song/singer name, and the value is the counter).

the RadioStation has a constant that defines a limit to how many times a song is allowed to be played.
whenever a song reaches this limit (meaning, it was played too much), the program needs to skip to the next song in the database.

so, I run this test from main, and the program crashes (or more accuratly get stuck, since the console stays open and the program keeps working until I stop it).
I made a few changes and run the debugger a few times, and was able to focus on the problem. let me show you the code first, and then I'll explain some more.

Song.h:

Code:

#ifndef SONG_H_
#define SONG_H_
#include<iostream>
#include<string>
#include<vector>
using namespace std;




class Song
{
public:
    enum eSection{INTRO,VERSE,CHORUS,TRANSITION};
    enum eSectionDurationInSeconds{INTRO_DUR=5,VERSE_DUR=10,CHORUS_DUR=20,TRANSITION_DUR=5};
    typedef pair<eSection,eSectionDurationInSeconds> SongSegment_t;

    Song(string name="", string composer="", string singer=""):
        m_name(name),m_composer(composer),m_singer(singer),m_songStr(""){}
    void addSection(eSection sec, eSectionDurationInSeconds iDuration);
    void playSong()const;
    void operator()(unsigned time)const;
    double getSongLengthInMinutes()const;
    string getName()const;
    string getSinger()const;
    bool operator==(const Song& song)const;
    bool operator!=(const Song& song)const;
    bool operator<(const Song& song)const;
    bool operator>(const Song& song)const;
private:
    string m_name;
    string m_composer;
    string m_singer;
    vector<SongSegment_t> m_song;
    string m_songStr;
};

#endif /* SONG_H_ */

Song.cpp

Code:

#include "Song.h"


void Song::addSection(eSection sec, eSectionDurationInSeconds iDuration)
{
    m_song.push_back(SongSegment_t(sec,iDuration));

    switch (sec)
    {
    case INTRO:
        m_songStr.append(INTRO_DUR,'I');
        break;
    case VERSE:
        m_songStr.append(VERSE_DUR,'V');
        break;
    case CHORUS:
        m_songStr.append(CHORUS_DUR,'C');
        break;
    case TRANSITION:
        m_songStr.append(TRANSITION_DUR,'T');
        break;
    }
}


void Song::playSong()const
{
    cout<<m_songStr<<endl;
}


void Song::operator()(unsigned time)const
{
    if ((time>0)&&(time<m_songStr.size()))
        cout<<m_songStr.substr(time);
    cout<<endl;
}


double Song::getSongLengthInMinutes()const
{
    return (double)m_songStr.size()/60;
}


string Song::getName()const
{
    return m_name;
}


string Song::getSinger()const
{
    return m_singer;
}


bool Song::operator==(const Song& song)const
{
    return (song.m_name==m_name)&&
            (song.m_composer==m_composer)&&
            (song.m_singer==m_singer)&&
            (song.m_song==m_song);
}


bool Song::operator!=(const Song& song)const
{
    return (song.m_name!=m_name)||
            (song.m_composer!=m_composer)||
            (song.m_singer!=m_singer)||
            (song.m_song!=m_song);
}


bool Song::operator<(const Song& song)const
{
    if (m_name==song.m_name)
        return m_singer<song.m_singer;
    else
        return m_name<song.m_name;
}


bool Song::operator>(const Song& song)const
{
    if (m_name==song.m_name)
        return m_singer>song.m_singer;
    else
        return m_name>song.m_name;
}

RadioManager.h: (has Playlist.h in it)

Code:

#ifndef RADIOMANAGER_H_
#define RADIOMANAGER_H_
#include<iostream>
#include<string>
#include<set>
#include<list>
#include<algorithm>
#include"Song.h"
#include"RadioStatistics.h"
using namespace std;



class Playlist
{
public:
    enum{MAX_PLAYLIST_LEN_IN_MINUTES=12};
    Playlist():m_stats(NULL){}
    double getPlaylistLengthInMinutes()const;
    bool addSongToPlaylist(const Song& song);
    bool removeSongFromPlaylist(const Song& song);
    bool isSongInPlaylist(const Song& song)const;
    void playPlaylist();
    const Song& getSong(unsigned index)const;
    size_t playlistSize()const;
private:
    //functor to compare between songs' length
    class CompareSongsLength
    {
    public:
        bool operator()(const Song& lhs, const Song& rhs)
        {
            //if lengths are equal
            if (lhs.getSongLengthInMinutes()==rhs.getSongLengthInMinutes())
                //compare names
                return lhs.getName()<rhs.getName();
            else
                //else; compare lengths
                return lhs.getSongLengthInMinutes()<rhs.getSongLengthInMinutes();
        }
    };

    //songs will be inserted orderly by their length (thus avoiding future sorting)
    multiset<Song,CompareSongsLength> m_playlist;
    RadioStatistics* m_stats;
};



class RadioStation
{
public:
    enum {MAX_PLAYED = 4};
    bool addSongToDB(const Song& song);
    void removeSongFromDB(const Song& song);
    bool isSongInDB(const Song& song)const;
    void addPlaylist(const Playlist& playlist);
    bool removePlaylist(unsigned iPlaylistNumber);
    void playAllPlaylists();
    void playAuthorizedSongs(const Playlist& playlist);
private:
    set<Song> m_dataBase;
    list<Playlist> m_playlists;
};



#endif /* RADIOMANAGER_H_ */

RadioManager.cpp:

Code:

#include"RadioManager.h"


/**************************RadioStation definitions*******************************/


bool RadioStation::addSongToDB(const Song& song)
{
    return m_dataBase.insert(song).second;
}


void RadioStation::removeSongFromDB(const Song& song)
{
    //erasing song from DB
    m_dataBase.erase(song);

    //setting iterators
    list<Playlist>::iterator head=m_playlists.begin();
    list<Playlist>::iterator tail=m_playlists.end();

    //deleting song from all playlists
    while (head!=tail)
    {
        head->removeSongFromPlaylist(song);
        head++;
    }
}


bool RadioStation::isSongInDB(const Song& song)const
{
    return m_dataBase.find(song)!=m_dataBase.end();
}


void RadioStation::addPlaylist(const Playlist& playlist)
{
    //adding playlist
    m_playlists.push_back(playlist);
    //adding playlist's songs to DB
    for (size_t i=0; i<playlist.playlistSize(); i++)
    {
        //if song is not in DB
        if (!isSongInDB(playlist.getSong(i)))
            addSongToDB(playlist.getSong(i));
    }
}


bool RadioStation::removePlaylist(unsigned iPlaylistNumber)
{
    //save collection size
    unsigned cSize=m_playlists.size();

    //if index is out of range
    if ((iPlaylistNumber<0)||(iPlaylistNumber>cSize-1))
        return false;

    //if index is in the first list's half
    if (iPlaylistNumber<cSize/2)
    {
        //get an iterator to begin and traverse forward
        list<Playlist>::iterator iter=m_playlists.begin();
        advance(iter, iPlaylistNumber);
        m_playlists.erase(iter);
    }
    //else; index is in the second list's half
    else
    {
        //get an iterator to end and traverse backward
        list<Playlist>::iterator iter=m_playlists.end();
        advance(iter, iPlaylistNumber-cSize);
        m_playlists.erase(iter);
    }
    return true;
}


void RadioStation::playAllPlaylists()
{
    //get iterators to begin and end of the list
    list<Playlist>::iterator head=m_playlists.begin();
    list<Playlist>::iterator tail=m_playlists.end();

    //traverse the list
    while (head!=tail)
    {
        //play only authorized songs from the playlist
        playAuthorizedSongs(*head);
        head++;
    }
}


void RadioStation::playAuthorizedSongs(const Playlist& playlist)
{
    RadioStatistics* stats=RadioStatistics::getInstance();

    //traverse over playlist
    for (size_t i=0; i<playlist.playlistSize(); i++)
    {
        //if song doesn't exceed limitation
        if (stats->getFreq(playlist.getSong(i).getName())<MAX_PLAYED)
        {
            playlist.getSong(i).playSong();
            stats->incrementStats(playlist.getSong(i));
        }
        //else; song was played too much
        else
        {
            //set iterator to song
            set<Song>::iterator iter=m_dataBase.find(playlist.getSong(i));
            //play the next song in the database
            iter++;
            iter->playSong();
        }
    }
}


/**************************Playlist definitions*******************************/


double Playlist::getPlaylistLengthInMinutes()const
{
    //get iterators to begin and end
    multiset<Song>::iterator head=m_playlist.begin();
    multiset<Song>::iterator tail=m_playlist.end();

    //traverse over the list
    double total_length(0);
    for (; head!=tail; head++)
        total_length+=head->getSongLengthInMinutes();
    return total_length;
}


bool Playlist::addSongToPlaylist(const Song& song)
{
    //get list and song lengths
    double list_length=getPlaylistLengthInMinutes();
    double song_length=song.getSongLengthInMinutes();

    //if addition will exceed limitation
    if (list_length+song_length>MAX_PLAYLIST_LEN_IN_MINUTES)
        return false;

    m_playlist.insert(song);
    return true;
}


bool Playlist::removeSongFromPlaylist(const Song& song)
{
    //if song is not in playlist
    if (!isSongInPlaylist(song))
        return false;

    m_playlist.erase(song);
    return true;
}


bool Playlist::isSongInPlaylist(const Song& song)const
{
    //find() will return iterator to end if song wasn't  found
    return find(m_playlist.begin(),m_playlist.end(),song)!=m_playlist.end();
}


void Playlist::playPlaylist()
{
    //setting iterators
    multiset<Song>::iterator head=m_playlist.begin();
    multiset<Song>::iterator tail=m_playlist.end();

    m_stats=RadioStatistics::getInstance();

    for (; head!=tail; head++)
    {
        head->playSong();
        m_stats->incrementStats(*head);
    }
}


const Song& Playlist::getSong(unsigned index)const
{
    unsigned cSize=m_playlist.size();
    if ((index<0)||(index>=cSize))
        throw("index is out of range");

    if (index<cSize/2)
    {
        //get an iterator to begin and traverse forward
        multiset<Song>::iterator iter=m_playlist.begin();
        advance(iter, index);
        return *iter;
    }
    else
    {
        //get an iterator to end and traverse backward
        multiset<Song>::iterator iter=m_playlist.end();
        advance(iter, index-cSize);
        return *iter;
    }
}


size_t Playlist::playlistSize()const
{
    return m_playlist.size();
}

RadioStatistics.h:

Code:

#ifndef RADIOSTATISTICS_H_
#define RADIOSTATISTICS_H_
#include<iostream>
#include<string>
#include<map>
#include<iterator>
#include<algorithm>
using namespace std;



class RadioStation;
class Song;

class RadioStatistics
{
private:
    static RadioStatistics* m_instance;
    map<string, unsigned> m_songs;
    map<string, unsigned> m_singers;
    RadioStatistics(){}
public:
    static RadioStatistics* getInstance();
    string getSongMostPlayed();
    string getSingerMostPlayed();
    unsigned getFreq(const string& songName);
    void incrementStats(const Song& song);
};


#endif /* RADIOSTATISTICS_H_ */

RadioStatistics.cpp:

Code:

#include "RadioStatistics.h"
#include "Song.h"


//static variable initialization
RadioStatistics* RadioStatistics::m_instance=NULL;


bool CompareValues(pair<string, unsigned> lhs, pair<string, unsigned> rhs)
{
    return lhs.second<rhs.second;
}


RadioStatistics* RadioStatistics::getInstance()
{
    if (!m_instance)
        m_instance=new RadioStatistics;
    return m_instance;
}


string RadioStatistics::getSongMostPlayed()
{
    return max_element(m_songs.begin(),m_songs.end(),CompareValues)->first;
}


string RadioStatistics::getSingerMostPlayed()
{
    return max_element(m_singers.begin(),m_singers.end(),CompareValues)->first;
}


//returns how frequently each song was played
unsigned RadioStatistics::getFreq(const string& songName)
{
    return m_songs.find(songName)->second;
}


void RadioStatistics::incrementStats(const Song& song)
{
    m_songs[song.getName()]++;
    m_singers[song.getSinger()]++;
}

now, the problem starts when I run the following code:
main.cpp

Code:

#include "Song.h"
#include "RadioManager.h"
#include <vector>
#include <string>

Song createSongType1(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer);
Song createSongType2(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer);
Song createSongType3(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer);

int main()
{
    std::vector<Song> songsPool;
    songsPool.push_back(createSongType1("aaa","DJ1","john"));
    songsPool.push_back(createSongType1("abc","DJ32","dan"));
    songsPool.push_back(createSongType1("aaa","DJ11","ben"));
    songsPool.push_back(createSongType1("bbb","DJ18","berri"));

    songsPool.push_back(createSongType2("ccc","DJ12","dilen"));
    songsPool.push_back(createSongType2("bcc","DJ6","jake"));
    songsPool.push_back(createSongType2("aaa","DJ5","smith"));
    songsPool.push_back(createSongType2("ddd","DJ18","sam"));

    songsPool.push_back(createSongType3("aaa","DJ6","danni"));
    songsPool.push_back(createSongType3("aaa","DJ32","avraham"));
    songsPool.push_back(createSongType3("bac","DJ9","avigail"));
    songsPool.push_back(createSongType3("aaa","DJ6","sher"));

    //create a radio station
    RadioStation rs1;

    //add all songs to its database
    std::vector<Song>::iterator itr = songsPool.begin();
    while(itr != songsPool.end())
    {
        rs1.addSongToDB(*itr);
        ++itr;
    }

    //creating playlists from radio database
    Playlist pl1;
    pl1.addSongToPlaylist(songsPool[0]);
    pl1.addSongToPlaylist(songsPool[1]);
    pl1.addSongToPlaylist(songsPool[4]);
    pl1.addSongToPlaylist(songsPool[8]);
    pl1.addSongToPlaylist(songsPool[9]);

    Playlist pl2;
    pl2.addSongToPlaylist(songsPool[0]);
    pl2.addSongToPlaylist(songsPool[2]);
    pl2.addSongToPlaylist(songsPool[3]);
    pl2.addSongToPlaylist(songsPool[5]);
    pl2.addSongToPlaylist(songsPool[9]);
    pl2.addSongToPlaylist(songsPool[11]);

    Playlist pl3;
    pl3.addSongToPlaylist(songsPool[2]);
    pl3.addSongToPlaylist(songsPool[0]);
    pl3.addSongToPlaylist(songsPool[6]);
    pl3.addSongToPlaylist(songsPool[10]);
    pl3.addSongToPlaylist(songsPool[11]);

    Playlist pl4;
    pl4.addSongToPlaylist(songsPool[2]);
    pl4.addSongToPlaylist(songsPool[3]);
    pl4.addSongToPlaylist(songsPool[1]);
    pl4.addSongToPlaylist(songsPool[9]);
    pl4.addSongToPlaylist(songsPool[7]);
    pl4.addSongToPlaylist(songsPool[10]);


    //add playlists to radio station
    rs1.addPlaylist(pl1);
    rs1.addPlaylist(pl2);
    rs1.addPlaylist(pl3);
    rs1.addPlaylist(pl4);


    //play playlists
    rs1.playAllPlaylists();

    return 0;
}



Song createSongType1(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer)
{
    Song s1(songName, composer, singer);
    s1.addSection(Song::INTRO,Song::INTRO_DUR); //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::TRANSITION,Song::TRANSITION_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    return s1;    //total: 90 seconds, 1.5 minutes
}

Song createSongType2(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer)
{
    Song s1(songName, composer, singer);
    s1.addSection(Song::INTRO,Song::INTRO_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::TRANSITION,Song::TRANSITION_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    return s1;    //total: 120 seconds. 2 minutes.
}

Song createSongType3(const std::string& songName,
                     const std::string& composer,
                     const std::string& singer)
{
    Song s1(songName, composer, singer);
    s1.addSection(Song::INTRO,Song::INTRO_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::TRANSITION,Song::TRANSITION_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::TRANSITION,Song::TRANSITION_DUR);    //5
    s1.addSection(Song::VERSE,Song::VERSE_DUR);    //10
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    s1.addSection(Song::CHORUS,Song::CHORUS_DUR);    //20
    return s1;    //total: 2.75
}

I ran a step by step debugger, and found out the problem lays with line 90 in RadioManager.cpp, when the while loop runs its fourth iteration.
it crashes when it tries to dereference the iterator, while it points to the fourth playlist in the list.

and here's some more weird stuff: when I comment out line 73 in main.cpp - it works perfectly fine! (line 73 in particular! commenting out any other line in main.cpp didn't worked around the bug!)

please, if anyone has a few minutes to look over and make some observation on what can cause this, or even try to compile it themself, I'll be grateful.

Any chance you could attach a zip file of those 7 files - it's quite a lot to copy/paste.

Your code is often using std::map::find(), and then dereferencing immediately. That will be a problem if find() returns an end() iterator (i.e. if the entry being searched for is not in the map). You need to check such cases, and most of the time you are not. Similarly, calling find(), then incrementing will produce an invalid iterator if find() returns end().


Unrelated to your problem, but it is an extremely bad idea to have "using namespace std;" in header files. In header files use "std::<whatever>" rather then relying on a using directive.

Can you advance by a negative number?

Code:

Program received signal SIGINT, Interrupt.
0x00007ffff7b43810 in std::_Rb_tree_increment(std::_Rb_tree_node_base*) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
(gdb) bt
#0  0x00007ffff7b43810 in std::_Rb_tree_increment(std::_Rb_tree_node_base*) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1  0x0000000000407ecd in std::_Rb_tree_const_iterator<Song>::operator++ (this=0x7fffffffd9d0) at /usr/include/c++/4.6/bits/stl_tree.h:269
#2  0x000000000040738b in std::__advance<std::_Rb_tree_const_iterator<Song>, long> (__i=..., __n=849357497) at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:140
#3  0x0000000000406ab7 in std::advance<std::_Rb_tree_const_iterator<Song>, unsigned int> (__i=..., __n=4294967293) at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:175
#4  0x0000000000406404 in Playlist::getSong (this=0x7fffffffdd60, index=2) at RadioManager.cpp:205
#5  0x0000000000405e1d in RadioStation::addPlaylist (this=0x7fffffffda20, playlist=...) at RadioManager.cpp:45
#6  0x0000000000402466 in main () at main.cpp:78
(gdb) frame 3
#3  0x0000000000406ab7 in std::advance<std::_Rb_tree_const_iterator<Song>, unsigned int> (__i=..., __n=4294967293) at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:175
175	      std::__advance(__i, __d, std::__iterator_category(__i));
(gdb) up
#4  0x0000000000406404 in Playlist::getSong (this=0x7fffffffdd60, index=2) at RadioManager.cpp:205
205			advance(iter, index-cSize);
(gdb) print index 
$6 = 2
(gdb) print cSize 
$7 = 5
(gdb) list
200		}
201		else
202		{
203			//get an iterator to end and traverse backward
204			multiset<Song>::iterator iter=m_playlist.end();
205			advance(iter, index-cSize);
206			return *iter;
207		}
208	}
209

index-cSize is -3 on my machine, and it never returns from this function.

Originally Posted by Absurd

for example, in the case you mentioned, we were told that we won't be tested for a case where an over-played song is happened to be the last song in the playlist, so I figured I don't need to be worried about it.

Your figuring is flawed. An "overplayed song last in the playlist" is not the same as "song is not in the playlist". It is the second condition that will cause problems I described, not the first.

Use asserts to validate your assumptions, you'll be surprised how often they were wrong!

OK, some updates.
I switched to Visual, it now became a problem of derefrencing:
"Expression: map/set iterator not dereferencable."
it crashed at the same place as before: line 90 on RadioManager.cpp, only this time, it crashes immediately on the first iteration.
anyone has an idea why won't it let me dereferencing 'head'?

edit

maybe this will be useful:

Code:

void RadioStation::playAllPlaylists()
{
    //get iterators to begin and end of the list
    list<Playlist>::iterator head=m_playlists.begin();
    list<Playlist>::iterator tail=m_playlists.end();

    //traverse the list
    while (head!=tail)
    {
        //play only authorized songs from the playlist
        playAuthorizedSongs(*head); //error; cannot dereference
        head++;
    }
}

Code:

void RadioStation::playAllPlaylists()
{
    //get iterators to begin and end of the list
    list<Playlist>::iterator head=m_playlists.begin();
    list<Playlist>::iterator tail=m_playlists.end();

    //traverse the list
    while (head!=tail)
    {
        //play only authorized songs from the playlist
        (*head).playPlaylist() //dereferencing without a problem...
        head++;
    }
}

OK, the problem was solved, with a help of a friend.

if anyone is still interested to know what the problem was:
it is not a dereferencing problem, even though it says so in the error massage...
the problem was at getFreq() (in RadioStatistics.cpp):
playAllPlaylists() called playAuthorizedSongs() which then called getFreq(), but in getFreq() I forgot to test for a case where the name of the song wasn't found:

Code:

//returns how frequent each song was played
unsigned RadioStatistics::getFreq(const string& songName)
{
        return m_songs.find(songName)->second;
}

this is how I fixed it:

Code:

//returns how frequent each song was played
unsigned RadioStatistics::getFreq(const string& songName)
{
    if (m_songs.find(songName)==m_songs.end())
        return 0;
    else
        return m_songs.find(songName)->second;
}

I thought the program crashes at playAllPlaylists(), and sent myself to a wild goose chase.
Thanks for anyone who commented.
any additional tips to improve this code will be happily accepted.

You do not need to search twice.

assign result of find to iterator and then check if it is end() - return null, else second of the element pointer by iterator