Linked List Problem(changing insertion pointer)

[John N.]

Hi All,

Here I have a linked list each containing a char and is double linked.
Then I have a pointer to an item in that list which is the current
insertion point.

In this funtion, the user hits the right
and left keys to move this insertion point (cursor)

Here is the problem:

But its not stable, the insertion point seems to skip an item
back, here and there. It could be the API Im using for the keyboard
input but Im not sure.

Thanks in advance for any help.
John

//a char structure, making a text string list
struct Word{
char *c;
struct Word *next,*back;
};
typedef struct Word Word;

Word *wrd;// a linked list of Word structures
Word *insert;// pointer to the current insertion point of *wrd

wrd = (allocate a list of Word structures)
insert = (pointer to an insertion point in the text in the *wrd list)

DoKey(insert,RIGHT_KEY);

/* etc */

void DoKey(struct Word *char_insert, int key){
switch(key){
case RIGHT_KEY:
if(char_insert->next!=NULL)
char_insert=char_insert->next;/* this is not fool proof,
any help? */
break;
case LEFT_KEY:
if(char_insert->back!=NULL)
char_insert=char_insert->back;/* this is not fool proof,
any help? */
break;
}
}

 

[Richard Heathfield]

[Followups set to comp.lang.c - nothing personal, Seebs!]

Hi All,

Here I have a linked list each containing a char and is double linked.

Your code says char *, not char.

Then I have a pointer to an item in that list which is the current
insertion point.

But its not stable, the insertion point seems to skip an item
back, here and there. It could be the API Im using for the keyboard
input but Im not sure.

It's your misunderstanding of pointers, I'm afraid.

//a char structure, making a text string list

If you have a C99 compiler, // is legal comment syntax. Do you?

struct Word{
char *c;
struct Word *next,*back;
};
typedef struct Word Word;

Word *wrd;// a linked list of Word structures
Word *insert;// pointer to the current insertion point of *wrd

wrd = (allocate a list of Word structures)

This ain't gonna compile.

insert = (pointer to an insertion point in the text in the *wrd list)

Nor is this. Please remember, when posting code here, that by definition you
do not know where the problem is. So it's not a good idea to chop out
random chunks of it when asking for help.

DoKey(insert,RIGHT_KEY);

/* etc */

void DoKey(struct Word *char_insert, int key){
switch(key){
case RIGHT_KEY:
if(char_insert->next!=NULL)
char_insert=char_insert->next;/* this is not fool proof,
any help? */

C is pass-by-value.

void DoKey(struct Word **char_insert, int key)
{
switch(key)
{
case RIGHT_KEY:
if((*char_insert)->next != NULL)
{
*char_insert = (*char_insert)->next;
}
break;

case LEFT_KEY:
if((*char_insert)->back != NULL)
{
*char_insert = (*char_insert)->back;
}
break;
default:
/* unhandled key event */
break;
}
}

 

[Jonathan Leffler]

Here I have a linked list each containing a char and is double linked.
Then I have a pointer to an item in that list which is the current
insertion point.

In this function, the user hits the right
and left keys to move this insertion point (cursor)

Here is the problem:

But its not stable, the insertion point seems to skip an item
back, here and there. It could be the API Im using for the keyboard
input but Im not sure.

No, it isn't likely to be that.

Thanks in advance for any help.
John

//a char structure, making a text string list
struct Word{
char *c;
struct Word *next,*back;
};
typedef struct Word Word;

Word *wrd;// a linked list of Word structures
Word *insert;// pointer to the current insertion point of *wrd

wrd = (allocate a list of Word structures)

And how is this data structure initialized? Zero pointers, or
pointers to itself (a circular list)? Or are you allocating and
initializing a whole bunch of Word structures, and putting them into a
valid linked list?

insert = (pointer to an insertion point in the text in the *wrd list)

So, presumably this is a contraction for 'insert = wrd;'? If not, you
need to show the initialization, since without the initialization, it
is hard to tell what the heck you might be doing.

DoKey(insert,RIGHT_KEY);

You've not shown where the character is coming from. I know you said
the keyboard, but which variable contains the value? Or is the
'RIGHT_KEY' -- presumably a macro since it is in upper case -- the
value purportedly to be inserted?

/* etc */

void DoKey(struct Word *char_insert, int key){
switch(key){
case RIGHT_KEY:
if(char_insert->next!=NULL)
char_insert=char_insert->next;/* this is not fool proof,
any help? */
break;

With a doubly-linked list, when you insert a new node, you allocate
the new node and populate the data portion (c) with the data for the
node. Then, assuming that the new node is inserted after the
insertion point, you ensure that the next pointer of the new node
points to the node that the insertion point points to as the next
node, that the back pointer of the next node points to the new node,
that the back pointer of the new node points to where the back pointer
of the insertion pointer points, and the next pointer of the back node
points to the new node. You might or might not also adjust the
insertion point. The sequence is similar but different if the new
node goes before the insertion point.

You've not shown very much of any of this material. You don't
allocate new nodes and you don't fix up the pre-existing nodes.

case LEFT_KEY:
if(char_insert->back!=NULL)
char_insert=char_insert->back;/* this is not fool proof,
any help? */
break;
}
}

Any more help? Draw a diagram! Draw a lot of diagrams! And make
sure all your pointers are initialized.

Finally, a member 'char *c' is misleading (but not, I hasten to
emphasize, wrong). In general, a variable c is a single character,
not a pointer to a character. There are various possible names that
would be happier choices - s or p are primary options, and there are a
myriad others. From the code you show, it is impossible to deduce
whether you store pointers to null-terminated strings or pointers to
single characters in it - you don't show it being used at all, in fact.

Given your problem description, you might be better off using c as a
simple char - though a doubly linked list of single characters is an
incredibly heavy-weight structure (typically occupying 12 bytes per
character).

Another reading of your problem might be that you are wondering why
the value of 'insert' in the calling code is not modified by the code
in DoKey -- and the answer is because you don't pass insert as a
pointer to a Word pointer. This only applies if you are already sure
you've built your doubly-linked list correctly, which is (as far as
anyone can see) debatable.

 

[Malcolm]

struct Word{
char *c;
struct Word *next,*back;
};
typedef struct Word Word;

Run the following function

void integrity_test(Word *head)
{
Word *prev = NULL:
printf("Start\n");
while(head)
{
printf("%s\n", head->c);
prev = head;
head = head->next;
}
printf("End\n");
while(prev)
{
printf("%s\n", prev->c);
prev = prev->back;
}
}

This should expose problems with the linked list structure.

 

[Barry Schwarz]

Hi All,

Here I have a linked list each containing a char and is double linked.
Then I have a pointer to an item in that list which is the current
insertion point.

In this funtion, the user hits the right
and left keys to move this insertion point (cursor)

Here is the problem:

But its not stable, the insertion point seems to skip an item
back, here and there. It could be the API Im using for the keyboard
input but Im not sure.

Thanks in advance for any help.
John

//a char structure, making a text string list
struct Word{
char *c;
struct Word *next,*back;
};
typedef struct Word Word;

Word *wrd;// a linked list of Word structures
Word *insert;// pointer to the current insertion point of *wrd

wrd = (allocate a list of Word structures)
insert = (pointer to an insertion point in the text in the *wrd list)

DoKey(insert,RIGHT_KEY);

/* etc */

void DoKey(struct Word *char_insert, int key){
switch(key){
case RIGHT_KEY:
if(char_insert->next!=NULL)
char_insert=char_insert->next;/* this is not fool proof,
any help? */
break;
case LEFT_KEY:
if(char_insert->back!=NULL)
char_insert=char_insert->back;/* this is not fool proof,
any help? */
break;
}
}

The real question is why do you think it worked at all. The
char_insert variable inside your function is not the same variable you
defined near the top of your code.

Your function performs all of its assignments to a local variable
(actually a parameter which, since C passes by value, is a copy of the
argument and not the argument itself). When the function exits, all
local variables (other than static) are destroyed. The result of your
function's assignments are never communicated back to the calling
function.


<<Remove the del for email>>

 

[John N.]

//a char structure, making a text string list

The real question is why do you think it worked at all. The
char_insert variable inside your function is not the same variable you
defined near the top of your code.

Your function performs all of its assignments to a local variable
(actually a parameter which, since C passes by value, is a copy of the
argument and not the argument itself). When the function exits, all
local variables (other than static) are destroyed. The result of your
function's assignments are never communicated back to the calling
function.

Hi All, Thanks for the quick responses.

I posted a shorter example of my code. The problem turned out to be
my switch/case statement that handled key input (not posted here) and
the insertion pointer was being misshandled.