C / C++ / MFC Discussion Boards

cod3Ninj47-Feb-24 23:40

7-Feb-24 23:40

Hi, I'm working on implementing a concurrent queue (implemented as single linked list) and I've encountered a problem. The structure of my linked list node looks like this:

struct queue {
    queue *head, *tail;
    pthread_mutex_t head_mut, tail_mut;
}
struct node {
    _Atomic(node*) next;
    int item;
};

I am currently implementing pop and push operations, both of them have their own separate mutex - tail_mut and head_mut respectively.
The list always includes a dummy node at the beginning.

I'm encountering an issue when there's only one element in the list (the dummy node plus this one element). I can't figure out how to handle the case where one thread is trying to push an element and another is trying to pop an element from the list.

The problem arises when we perform a pop operation first and change the head to head->next. In this scenario, another thread can still push elements to the list by adding them to the end of the list (tail). However, the list has only one element (the one that is being popped = tail), so i must find a solution to somehow block this operation or to signal 'pushing' thread that it should push to the head not to tail.

Acquiring the tail mutex would obviously solve the problem, but I'm looking for a potentially more efficient solution (so I would not block push operations by acquiring the tail mutex).

Is there a more efficient way to handle this situation? Any suggestions would be greatly appreciated.

Re: Concurrent linked list

jschell9-Feb-24 12:32

jschell

9-Feb-24 12:32

cod3Ninj4 wrote:
I can't figure out how to handle the case

Good thing because there is no way to handle that case.

You can only do it with one of the following.
1. One and only one lock.
2. Two dummy nodes, one at each end.

cod3Ninj4 wrote:
Is there a more efficient way to handle this situation?

Probably but that answer depends on how it is used and not on how it is implemented.

get_string memory leak?

mike74115-Feb-24 9:57

mike7411

5-Feb-24 9:57

I am taking Harvard's CS50 class. We are learning C.

They use their own library where you include cs50.h.

There is a function called get_string that returns a string.

I think it has a memory leak.

I think this is the source code:

https://github.com/cs50/libcs50/blob/main/src/cs50.c

They are saying stuff like:

string name = get_string("What is your name?");

Then, they never call free on the memory in main.

Anyone know how the memory gets freed or if it is a leak?

Thanks.

Re: get_string memory leak?

Dave Kreskowiak5-Feb-24 10:03

Dave Kreskowiak

5-Feb-24 10:03

No.

From the very code you linked to:

C++

/**
 * Called automatically after execution exits main.
 */
static void teardown(void)
{
    // Free library's strings
    if (strings != NULL)
    {
        for (size_t i = 0; i < allocations; i++)
        {
            free(strings[i]);
        }
        free(strings);
    }
}

The library keeps track of all the strings it allocates and frees them when your app exits.

Asking questions is a skill
CodeProject Forum Guidelines
Google: C# How to debug code
Seriously, go read these articles.
Dave Kreskowiak

Re: get_string memory leak?

Mircea Neacsu5-Feb-24 14:13

Mircea Neacsu

5-Feb-24 14:13

After Dave's on-point answer, this is just a general comment with the hope that your question becomes a teachable moment.

Way back when, as I was learning programming, I came up with a saying: "the silly is on the other side of the screen". It obviously can be interpreted both ways, but the idea is to look where the balance of probability indicates that the error should be. In my case, I learned my first assembly language trying to prove that the compiler was wrong - of course it wasn't. In your case, the chance that a course from a prestigious institution contains a trivial error are rather small compared with the chance that you are missing something.

Try to find what you are missing and those "Aha!" moments may benefit you more than the rest of the assignment. And, when in doubt, try to remember: the silly is on the other side of the screen. Laugh | :laugh:

Mircea

Re: get_string memory leak?

mike74115-Feb-24 20:05

mike7411

5-Feb-24 20:05

This is their pseudocode for bubble sort:

-------------------------------------------------------

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

-------------------------------------------------------

Then, David Malan supposedly analyzed the running time
by multiplying n-1 by n-2.

Re: get_string memory leak?

Mircea Neacsu5-Feb-24 20:22

Mircea Neacsu

5-Feb-24 20:22

That is, indeed, the worst case performance of bubble sort. Bubble sort - Wikipedia[^]. Not sure what you want to say.

Mircea

Re: get_string memory leak?

Dave Kreskowiak6-Feb-24 4:39

Dave Kreskowiak

6-Feb-24 4:39

What does that have to do with "get_string memory leak"?

Asking questions is a skill
CodeProject Forum Guidelines
Google: C# How to debug code
Seriously, go read these articles.
Dave Kreskowiak

Re: get_string memory leak?

Mircea Neacsu6-Feb-24 6:59

Mircea Neacsu

6-Feb-24 6:59

Just the fact that’s not wise to assume the error is someone else’s code. Better to try to understand what’s going on and discover what atexit function does.

Next step would be to eventually figure out that the “constructor” code is contrived and the call to atexit could be done on first allocation.

Edit: not sure to what message was your reply. Stuck to a cell phone today and CP is not the greatest on mobile. Apologies if I’m confusing you.

Mircea

Re: get_string memory leak?

Dave Kreskowiak6-Feb-24 12:22

Dave Kreskowiak

6-Feb-24 12:22

First the question is about a method that may leak memory, then a sudden jump-cut a post about bubble sort pseudocode, then another jump-cut to your philosophy.

To say I'm confused as to what's going on with this thread is an understatement.

Asking questions is a skill
CodeProject Forum Guidelines
Google: C# How to debug code
Seriously, go read these articles.
Dave Kreskowiak

Re: get_string memory leak?

Mircea Neacsu6-Feb-24 12:28

Mircea Neacsu

6-Feb-24 12:28

Apologies again! I thought your message was directed at my answer. Anyway I'll try to cut the philosophy c**p in the future; it's waste of time.

Mircea

Re: get_string memory leak?

jschell6-Feb-24 5:02

jschell

6-Feb-24 5:02

mike7411 wrote:
I think it has a memory leak.

Despite the other posts - yes this would be a classic example of a memory leak.

The teardown() method, as used, is pointless. When the application exits (on every modern OS including small ones) the memory that the application uses is returned to the OS. So the fact that teardown is called on the application exit via the atexit() method is absolutely pointless.

If you were to use the code in a regular application, especially but not limited to one that does not exit, then this would fail. Because of memory leaks. You could not call teardown() arbitrarily either because it would clear everything.

Now it is possible that the point of the code is not to teach you efficient memory usage. But one could certainly argue that the get_string() method should make it clear that this is not a good way to do things.

However the following is in comment for that method.

Stores string
on heap, but library's destructor frees memory on program's exit.

And that indicates that the creator of this code did not understand/know what I pointed out above.
The code also has a copyright date of 2023 so there is no claim that the code could have been written, for example 50 years ago, where one might (perhaps) have used an OS where the application would have needed to do that. Note however that even then I am not sure any OSes actually worked that way. Back then PC-DOS, CPM and early unix versions (there was no linux) returned memory to the OS.

You can take from this that you should not write code like this.

In general in C and C++ you should always control the scope of your memory allocations. So for example if your method allocates some memory then that same method should deallocate (all exit conditions for the method included.) There should almost never be a need to have a method return an allocation and if it does happen then the method should document (comment) that the caller is responsible for the allocation.

C++ makes this easier since you can wrap the allocation in a class. And control allocation/deallocation from that. That is something that I would suggest always doing. So in C++ you would never return an allocated pointer.

Re: get_string memory leak?

k50546-Feb-24 5:15

k5054

6-Feb-24 5:15

You've covered everything I was going to say, and then some. I was not sure what early versions of DOS might have done with allocated memory at program exit, but it's nice to know that even then, an most OS's would do the Right Thing™.

The code looks like it comes from the early 80's. That it should come from a prestigious university (it is that Harvard, right?), that should know better, is disheartening. Although, it might be a shining example of what not to do.

"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown

Re: get_string memory leak?

RedDk6-Feb-24 10:06

RedDk

6-Feb-24 10:06

Actually, you, like I do, should question the exisitential "being" of said OP, if this is any indication of a sentience which can't be gleened from his reputation due to the fact that there is no access to said: mike7411 - Professional Profile[^]

I know, I know. A kite joke. Frown | :(

Re: get_string memory leak?

jschell7-Feb-24 5:22

jschell

7-Feb-24 5:22

k5054 wrote:
That it should come from a prestigious university (it is that Harvard, right?), that should know better

That of course doesn't mean anything.

Large organizations, all large organizations, tend towards the average. That is inevitable due to size.

Besides that there is no determination about an individuals competence in general or for specific things.

You can also google for variations of the code library and find variations. I found a variation that looked like it was C++. No memory leak in that (very brief look) because it was returning 'string'. So possible that someone familiar with C++ but not so much C converted it. And also possible it wasn't even the person teaching the class, just that the teacher found it and is using it.

Re: get_string memory leak?

charlieg12-Feb-24 23:04

charlieg

12-Feb-24 23:04

Harvard esp. so Smile | :)

Charlie Gilley

“They who can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.” BF, 1759

Has never been more appropriate.

"connect" with "lambda" C++ code analysis , please.

Salvatore Terress3-Feb-24 15:01

Salvatore Terress

3-Feb-24 15:01

First - my apology for taking so much space, I promise to delete ALL after I get this solved - unless it is of benefit to forum...

Here is the current status of "main menu with sub menus "
using "connect" with lambda - it works only on FIRST menu.

I believe the sender and subsequent trigger are WRONG.
I am enclosing the code which creates
the " main menus with their associated sub menus ".
The code works as expected / desired.

The issue is using "connect" as a trigger..sub menu selection...

C++

{// menus processing
                                    // main memu primary loop is not array
                                    // main list is NOT an array
                                    for (index = 0; index < list.size(); ++index)
                                    {
                                        { // // main menu process block
                                            { // function
                                                // int subSize = 2;
                                                subMenu[index]  = m_ui->menuWindow_cpntrol;
                                                // adds main menu with arrows
                                                // triggers on hower
                                                subMenu[index] = subMenu[index]
                                                        ->addMenu(list[index] + " # " + QString::number(index));
                                                mainAction[index] = subMenu[index]->menuAction();  // TOK

                                                subSize = list_array[index].size();
                                                for (index_sub = 0; index_sub < subSize; ++index_sub)
                                                { // inner loop function block
                                                    { // process block
                                                        { // add sub menu
                                                            subAction[index_sub]= subMenu[index]->addAction(list_array[index][                      index_sub] + " #" + QString::number( index_sub));
                                                            subAction[index_sub]->setCheckable(true);
                                                        }// add sub menu
                                                    }// process block
                                                } // inner loop
                                            } // main menu process block

                                            // common stuff
                                            QAction* tempAction = new QAction(); //  text , this);
                                            tempAction->setCheckable(true);


                                            { // real connect block
                                                // connect to subMenu
                                                //connect(subMenu[index], &QMenu::triggered, this ,[=]() { this->processMenu_NoParameters() ;});
                                                //    connect(subMenu[1], &QMenu::triggered, this ,[=]() { this->processMenu(index,index_sub) ;});
                                            }

                                            { // connect block
                                                {// signal mapper code block

                                                } //   signal mapper code block
                                            }// connect block

                                            { // bypass block }
                                                //connect(subAction[index_sub],&QAction::triggered, [=]() {                                                               emit  this->processAction(index,index_sub);});

{}
                                            } // bypass block }
                                        }// main loop
                                    } // function block

                                    {
                                        //break;

                                    }
                                    //       connect(subAction[index_sub],&QAction::triggered, [=]() {
                                    //           emit  this->processAction(index,index_sub);});
                                }

Here is my current, working with FIRST menu code.
I do apology for "debug" junk code , it is a little hard to follow the real code.

C++

{
#ifdef LAMBDA
    text = "START TASK DEBUG lambda ... ";
    text += Q_FUNC_INFO;
    text += QString::number(__LINE__);
    qDebug() << text;
#endif

    // results
    int submenu_index = -1;
    int mainmenu_index= -1;

    QString mainMenu;


    QObject obj;

    qDebug() << " index_sub " << index_sub ; // bogus
    obj.connect(subMenu[index_sub],&QMenu::triggered,subMenu[index_sub  ],[](QAction* action)
// obj.connect(subAction[index_sub],QAction::triggered(bool),subAction[index_sub ],[](QAction* action)

    {// lambda

        QString path=action->text();


#ifdef LAMBDA
       qDebug() << "TEST need index ?? " << path;
       qDebug()<<"path (sub menu trigger ) "<< path ;
#endif
        QWidget* parent=action->parentWidget();
        // !!!!  submenu  trigger index   !!!
        path = QString("(%1)").arg(parent->actions().indexOf(action));
        //path += QString("(%1)").arg(parent->actions().indexOf(action));
        //qDebug() << " index ??" << parent->actions().indexOf(actions);
        //  TODO submenu_index = path;

#ifdef LAMBDA
        qDebug()<<"path (sub menu ) with index TOK  "<< path ;
#endif
        while(parent)
            {
            // main menu
            QMenu* menu=qobject_cast<QMenu*>(parent);
            QString title=menu->title();
 #ifdef LAMBDA
            qDebug()<<"title (main menu )  "<< title ;
#endif
            path+="->"+title;
            qDebug()<<"path (title) "<< path ;
            // who is parent widget
            parent=parent->parentWidget();
#ifdef LAMBDA
           qDebug()<<"TRACE  while first entry crasher ... "<< __LINE__ ;
#endif
            if(parent)
                {
#ifdef LAMBDA
           qDebug()<<"TRACE  parent widget (??) valid continue  ... "<< __LINE__ ;
#endif


                QMenu* menu=qobject_cast<QMenu*>(parent);
#ifdef LAMBDA
           qDebug()<<"TRACE  parent widget main menu (??)continue "<< __LINE__ ;
#endif
                int index=0;
                const QList<QAction*> actions=menu->actions();
#ifdef LAMBDA
           qDebug()<<"TRACE  parent widget main menu list (actions) continue "<< __LINE__ ;
#endif


                // all "window" menu ( action )
                // find current triggred menu
                for(const QAction *act : actions)
                    {
#ifdef LAMBDA
           qDebug()<<"TRACE  for(const QAction *act : actions) "<< __LINE__ ;
#endif
#ifdef LAMBDA
           qDebug()<<"TRACE  title (??) " << title << __LINE__ ;
#endif
#ifdef LAMBDA
           qDebug()<<"TRACE  act->text()==title  "<< act->text() << __LINE__ ;
#endif
                    if(act->text()==title)
                        {

#ifdef LAMBDA
           qDebug()<<"TRACE  main menu found act->text()==title  "<< act->text() << __LINE__ ;
#endif
                       //path +=QString("(%1)").arg(index);
                        path = QString("(%1)").arg(index);
                        // mainMenu = QString("%1").arg(index);
#ifdef LAMBDA
                        //qDebug()<< "mainMenu index " << mainMenu;
                        //mainmenu_index = QString::number(mainMenu);

#endif


#ifdef LAMBDA
                        qDebug()<<"HERE   path (main menu -> sub menu) "<< path ;
#endif
                        goto TEMP_LABEL;
                        // ??break;
                        }
#ifdef LAMBDA
           qDebug()<<"TRACE  "<< __LINE__ ;
#endif

                    index++;
                    }
                }
            } // while loop
TEMP_LABEL:        qDebug()<<" FINAL  (??) "<< path;

    }// lambda
    );

    QString::number(__LINE__);
    //mainmenu_index = QString::number(mainMenu);


#ifdef LAMBDA
    text = "END TASK DEBUG lambda... ";
    text += Q_FUNC_INFO;
    text += QString::number(__LINE__);
    qDebug() << text;
#endif
    return 0;
}

'

Here is more junk - actual debug output when first "main menu" and its "first sub menu " is selected - by triggering on first sub menu.

19:53:10: Starting /mnt/A_BT_DEC10/BT__PROGRAMS/A_JAN11/A_BT_LIBRARY/mdi/mdi...
Warning: Ignoring XDG_SESSION_TYPE=wayland on Gnome. Use QT_QPA_PLATFORM=wayland to run on Wayland anyway.
"START TASK DEBUG lambda ... int MainWindow_Bluetooth::setupLambda()89"
 index_sub  0
"END TASK DEBUG lambda... int MainWindow_Bluetooth::setupLambda()213"
TEST need index ??  "SubWindow LOCAL terminal all options          #0"
path (sub menu trigger )  "SubWindow LOCAL terminal all options          #0"
path (sub menu ) with index TOK   "(0)"
title (main menu )   "terminal      # 0"
path (title)  "(0)->terminal      # 0"
TRACE  while first entry crasher ...  138
TRACE  parent widget (??) valid continue  ...  143
TRACE  parent widget main menu (??)continue  149
TRACE  parent widget main menu list (actions) continue  154
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "Tile subwindows " 169
TRACE   194
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "Cascade subwindows " 169
TRACE   194
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "Maximize current subwindow " 169
TRACE   194
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "" 169
TRACE   194
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "" 169
TRACE   194
TRACE  for(const QAction *act : actions)  163
TRACE  title (??)  "terminal      # 0" 166
TRACE  act->text()==title   "terminal      # 0" 169
TRACE  main menu found act->text()==title   "terminal      # 0" 175
HERE   path (main menu -> sub menu)  "(5)"
 FINAL  (??)  "(5)"
19:53:27: /mnt/A_BT_DEC10/BT__PROGRAMS/A_JAN11/A_BT_LIBRARY/mdi/mdi exited with code 0

Here is the failure when ANY main menu , with exception of first one , is used.

That points to probable cause - wrong sender....

19:31:40: Starting /mnt/A_BT_DEC10/BT__PROGRAMS/A_JAN11/A_BT_LIBRARY/mdi/mdi...
Warning: Ignoring XDG_SESSION_TYPE=wayland on Gnome. Use QT_QPA_PLATFORM=wayland to run on Wayland anyway.
"START TASK DEBUG lambda ... int MainWindow_Bluetooth::setupLambda()89"
 index_sub  0
"END TASK DEBUG lambda... int MainWindow_Bluetooth::setupLambda()213"
19:31:54: /mnt/A_BT_DEC10/BT__PROGRAMS/A_JAN11/A_BT_LIBRARY/mdi/mdi exited with code 0

Re: "connect" with "lambda" C++ code analysis , please.

k50543-Feb-24 15:55

k5054

3-Feb-24 15:55

Best guess? Wrong forum. AFAICT this is a QT issue. QT ≠ C++. While QT does use C++ as a base, it's a framework on top of C++. You are more likely to get an answer either from a QT specific forum, or from the site you got your examples from.

"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown

Re: "connect" with "lambda" C++ code analysis , please.

Salvatore Terress3-Feb-24 16:44

Salvatore Terress

3-Feb-24 16:44

So you do not think this is my fault - wrong usage of C++?

"connect " is Qt specific , but lambda is C++ or am I wrong?
I did post same on QT forum and I fully expect somebody to say _ this is C++ code problem "...

But if I continue this discussion here ... I will end up banned......
.,..in that case..

Thanks and have a swell day...

Re: "connect" with "lambda" C++ code analysis , please.

k50544-Feb-24 4:34

k5054

4-Feb-24 4:34

I'm basing this on the runtime error, which you believe is something to do with "wrong sender". That seems to me to be a QT issue, not a C++ issue. AFAIK, there's no such thing as a "sender" in the C++ standard. Which points to QT, not C++

"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown

Re: "connect" with "lambda" C++ code analysis , please.

Salvatore Terress4-Feb-24 4:49

Salvatore Terress

4-Feb-24 4:49

OK, it is Qt issue..
I'll give few days for somebody else to respond , then I
will take it down.
Is that OK?

Re: "connect" with "lambda" C++ code analysis , please.

k50544-Feb-24 5:30

k5054

4-Feb-24 5:30

I'd just leave it, unless more senior members disagree. Otherwise, there's a discussion that someone else might stumble on and wonder what was going on. Who knows, maybe someone will stumble on this at some time in the future and be able to explain what the issue is.

"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown

Re: "connect" with "lambda" C++ code analysis , please.

Salvatore Terress4-Feb-24 13:36

Salvatore Terress

4-Feb-24 13:36

Here is my analysis in a nutshell.
The "issue" is with Qt "connect" function / process...
I have the "connect" working as expected , but ...
I am passing parameters / indexes - main menu and submenu...
...that is what I thought I was doing , but ...
the "parameters " values are NOT dynamic AKA
used when "connect" is activated - click on sub menu.
In my test - the main menu should be 0
and the submenu anything from 0 to 7

The code I have found uses lambda
and it analyze the "connect" AND
RETRIEVES the dynamic values of both indexes.
I need the indexes to do what the menu / submenu
is about - process something...

I have modified the code because i
CANNOT debug / step thru the lambda code !

So - the lambda code does work BUT ...
it only works/ retrieves main menu index of 0

That is the real error and I am seeking assistance
to find out why
it only works on FIRST menu.

My uneducated guess is -
the obvious place
to look is where
the code step thru "main menu list"...

C++

    if(parent)
        {
        QMenu* menu=qobject_cast<QMenu*>(parent);
        int index=0;
        const QList<QAction*> actions=menu->actions();
        for(const QAction *act : actions)
            {
            if(act
->text()==title)
                {
                path+=QString("(%1)").arg(index);
                break;
                }
            index++;
            }
        }

Re: "connect" with "lambda" C++ code analysis , please.

k50545-Feb-24 4:25

k5054

5-Feb-24 4:25

Salvatore Terress wrote:
I have modified the code because i
CANNOT debug / step thru the lambda code !

That does seem to be an issue with lambdas - at least gdb doesn't seem to be able to step into lambdas. I haven't tried it myself, so I can only go by what I've seen elsewhere on the subject.

But.

Why don't you just extract the function definition from the lambda and define it as a normal function. I think that should work

C++

foo( a, b, c, [](int x, int y) { /*  do something; */ return val; } );

becomes

C++

int lambda_f( int x, int y)
{
   // body from lambda called in foo(), above
   return val;
}

// ...
foo(a, b, c lambda_f);

"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown

Re: "connect" with "lambda" C++ code analysis , please.

Salvatore Terress5-Feb-24 6:30

Salvatore Terress

5-Feb-24 6:30

Yes, I am now using plain function to analyze results of "connect".
My code is still pretty messy , hard to read , since I added debug...
But I can step thru it , so the debug is "leftover from lambda"...

I got my code doing what I need...
In retrospect - the problem was what I suspected from the start

understanding "connect" and PLACING it into correct place.
PS
As far as getting help from forums - it was ABOUT 80% of "RTFM" and other
"fill the blanks" to make "small talk"...

Last Visit: 31-Dec-99 18:00 Last Update: 9-May-24 2:55

Refresh

ᐊ Prev 1...7 8 9 101112 13 14 15 16 Next ᐅ

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.