Help with double linked lists

[Sigmathaar]

Hi, I'm having some problems when using double linked lists, specially
when it's up to the Blink an Flink pointers. Does anybody knows a good
site or a book where they explain how to use them?

Thanks

[mlimber]

Sigmathaar wrote:

Hi, I'm having some problems when using double linked lists, specially
when it's up to the Blink an Flink pointers. Does anybody knows a good
site or a book where they explain how to use them?

Well since this forum is for standard C++ language and library
discussions, I presume you're talking about some particular
implementation of std::list. Unfortunately, Blink and Flink are not
part of the standard on this point, so I can't comment on them (at
least not without some code to look at), though they probably refer to
the backward and forward links respectively. You should check Josuttis'
_The C++ Standard Library - A Tutorial and Reference_ for more on how
to use std::list. Alternately, pick up any data structures book, and it
should deal with them.

Cheers! --M

[Sigmathaar]

Yes, Blink and Flink refer to the backward and foward links, my problem
is that it's the first time I'm dealing with them and it's also been a
littel while since I last coded anything in C or C++. Since it's
difficult to help me without any code to look I'll give the part who's
giving me problems.

This is the struct of the list :

typedef struct _LIST_ENTRY {
struct _LIST_ENTRY *Flink;
struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;

These are the variables I'm using :

static LIST_ENTRY m_CacheListHead;
LIST_ENTRY* pEntry;
LIST_ENTRY* pEntryNext;
USER_INFO* pUser;

And here's an extract of the code I'm having problems with :

for ( pEntry = m_CacheListHead.Flink; pEntry != &m_CacheListHead;
pEntry = pEntryNext )
{
pUser = CONTAINING_RECORD( pEntry, USER_INFO, ListEntry );
pEntryNext = pEntry->Flink;

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

The code is suposed to go through pUser and free the memory used by
each entry on CacheListHead but I don't understand the last two lines
which for me seem to be useless. Can somebody explain me what are those
lines for?

[Alf P. Steinbach]

* Sigmathaar:

Yes, Blink and Flink refer to the backward and foward links, my problem
is that it's the first time I'm dealing with them and it's also been a
littel while since I last coded anything in C or C++. Since it's
difficult to help me without any code to look I'll give the part who's
giving me problems.

This is the struct of the list :

typedef struct _LIST_ENTRY {
Identifier starting with underscore followed by uppercase is reserved to
the implementation.

Also, all uppercase should only be used for macros.

That means you're looking at _bad_ example code.

struct _LIST_ENTRY *Flink;
struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;

These are the variables I'm using :

static LIST_ENTRY m_CacheListHead;
LIST_ENTRY* pEntry;
LIST_ENTRY* pEntryNext;
USER_INFO* pUser;
Don't use global variables.

And here's an extract of the code I'm having problems with :

for ( pEntry = m_CacheListHead.Flink; pEntry != &m_CacheListHead;
pEntry = pEntryNext )
{
pUser = CONTAINING_RECORD( pEntry, USER_INFO, ListEntry );
pEntryNext = pEntry->Flink;

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

The code is suposed to go through pUser and free the memory used by
each entry on CacheListHead
but I don't understand the last two lines
which for me seem to be useless. Can somebody explain me what are those
lines for?

They're a good way to gobble up memory. They unlink the node and leaves
no pointer to it anywhere. So it's lost.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Howard]

"Sigmathaar" <si********@gmail.com> wrote in message
news:11*********************@z14g2000cwz.googlegro ups.com...

Yes, Blink and Flink refer to the backward and foward links, my problem
is that it's the first time I'm dealing with them and it's also been a
littel while since I last coded anything in C or C++. Since it's
difficult to help me without any code to look I'll give the part who's
giving me problems.

This is the struct of the list :

typedef struct _LIST_ENTRY {
struct _LIST_ENTRY *Flink;
struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;

Don't use leading underscores followed by capital letter, ever. That's
reserved for the "implementation" (i.e., the compiler/library vendor).

And prefer to only use all capital letters for macros.

That's also an old C construct. Use C++ instead:

struct ListEntry
{
ListEntry* FLink;
ListEntry* BLink; // although Next and Previous would be more readable!
};

// this is your pointer typedef, but useless in my ompinion,
// since you can always use ListEntry*, which takes the same amount of
typing
typedef ListEntry* PListEntry;
These are the variables I'm using :

static LIST_ENTRY m_CacheListHead;
LIST_ENTRY* pEntry;
LIST_ENTRY* pEntryNext;
USER_INFO* pUser;

ListEntry* pEntry;
ListEntry* pEntryNext;
And here's an extract of the code I'm having problems with :

for ( pEntry = m_CacheListHead.Flink; pEntry != &m_CacheListHead;
pEntry = pEntryNext )
{
pUser = CONTAINING_RECORD( pEntry, USER_INFO, ListEntry );
pEntryNext = pEntry->Flink;

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

The code is suposed to go through pUser and free the memory used by
each entry on CacheListHead but I don't understand the last two lines
which for me seem to be useless. Can somebody explain me what are those
lines for?
If you are removing every ListEntry item (you don't show the rest of the
code, but it appears so), then those two lines are indeed useless. But
similar code is often used when removing a _single_ item from a list, in
order to tell the items on either side of the removed item who they should
now be pointing at. (Perhaps the coder simply did here what he/she does
whenever they remove a _single_ item from the list?)

However, unless this is a _circular_ linked list, where FLink and BLink are
never NULL, then they're likely to cause a crash or other Undefined
Behavior, since the BLink (previous) pointer for the first item would be
NULL, making the following line illegal:
pEntry->Blink->Flink = pEntry->Flink; // Can't access
pEntry->BLink->FLink if pEntry->BLink is NULL!

(A similar thing would happen at the end of the list, when pEntry->FLink is
NULL.)

-Howard

[Sigmathaar]

I wasn't the one who wrote the code, I'm having problems understanding
it because there's no comment on the sources. _LIST-ENTRY is in fact
part of one Visual C++ 6.0 library but their explaination of how to use
it it's neather clear or complete. The variables are not global, they
are part of the method of one classe of the program I'm working on, I
didn't put the whole source code since the part I'm having problems
with is understandable like that and there's in fact only two lines
which I don't understand :

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

Cans somebody tell what do they do?

[Howard]

"Alf P. Steinbach" <al***@start.no> wrote in message
news:43*****************@news.individual.net...

for ( pEntry = m_CacheListHead.Flink; pEntry != &m_CacheListHead;
pEntry = pEntryNext )
{
pUser = CONTAINING_RECORD( pEntry, USER_INFO, ListEntry );
pEntryNext = pEntry->Flink;

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

They're a good way to gobble up memory. They unlink the node and leaves
no pointer to it anywhere. So it's lost.

No way to know that, actually, since the rest of the loop isn't shown.
Could be there's a "delete pEntry" call there. Or not. :-)

-Howard

[Sigmathaar]

Well, here is the complete source code, the list I'm using is like
Howard said a circular linked list.

VOID CAuthFilter::TerminateCache()
{
LIST_ENTRY* pEntry;
LIST_ENTRY* pEntryNext;
USER_INFO* pUser;

if ( !m_fCacheInitialized )
return;

EnterCriticalSection( &m_csCacheLock );

for ( pEntry = m_CacheListHead.Flink; pEntry != &m_CacheListHead;
pEntry = pEntryNext )
{
pUser = CONTAINING_RECORD( pEntry, USER_INFO, ListEntry );
pEntryNext = pEntry->Flink;
pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

LocalFree( pUser );
}

m_cCacheItems = 0;
LeaveCriticalSection( &m_csCacheLock );
DeleteCriticalSection( &m_csCacheLock );
m_fCacheInitialized = FALSE;
}

[Howard]

"Sigmathaar" <si********@gmail.com> wrote in message
news:11**********************@g49g2000cwa.googlegr oups.com...

I wasn't the one who wrote the code, I'm having problems understanding
it because there's no comment on the sources. _LIST-ENTRY is in fact
part of one Visual C++ 6.0 library but their explaination of how to use
it it's neather clear or complete. The variables are not global, they
are part of the method of one classe of the program I'm working on, I
didn't put the whole source code since the part I'm having problems
with is understandable like that and there's in fact only two lines
which I don't understand :

pEntry->Blink->Flink = pEntry->Flink;
pEntry->Flink->Blink = pEntry->Blink;

Cans somebody tell what do they do?

Think of it as you and ome other people standing in line. Assume pEntry is
you. BLink means the guy behind you in line. FLink means the guy in front
of you.

Similarly, BLink->FLink means "the guy in front of the guy behind you".
Which is you! And FLink->BLink means "the guy behind the guy in front of
you", which is also you.

But since you want to remove yourself from the line, you need to tell the
guy behind you that the guy in front of him will no longer be you, but
instead will be the guy who is currently in front of you. Got it?

Similarly for the second line: it tells the guy in front of you that the guy
behind him will no longer be you, but will instead be the guy who is
currently behind you.

So, if Bob was behind you and Frank was in front of you, then after you
leave, Frank will be in front of Bob, and Bob will be behind Frank
(naturally).

Clear?

-Howard

[Sigmathaar]

Thanks a lot, it's far more clear than all the explanations I've found
on the web.

[mlimber]

Sigmathaar wrote:

I wasn't the one who wrote the code, I'm having problems understanding
it because there's no comment on the sources. _LIST-ENTRY is in fact
part of one Visual C++ 6.0 library but their explaination of how to use
it it's neather clear or complete.

[snip]

May I suggest if you are writing new code that you prefer the
*standard* doubly-linked list provided with the same copiler's standard
library (in the <list> header). See your C++ book (e.g., Stroustrup's
_The C++ Programming Language_ 3rd ed. or Josuttis' mentioned above)
for more details or see these links:

http://www.sgi.com/tech/stl/List.html

http://www.cppreference.com/cpplist/

Cheers! --M