Inability to follow good programming practice by qualifying a pointer parameter with 'const'

[hzmonte]

typedef int t_compare_func(const void *, const void *);

struct node *tree_search(struct node *root, const void *keyy,
t_compare_func *comp)
{
struct node *cur_item;
int result;
if (root == NULL) return NULL;
cur_item = root;
while (cur_item != NULL) {
result = (*comp)(cur_item->key, keyy);
if (result == 0)
break;
else if (result > 0)
cur_item = cur_item->left;
else
cur_item = cur_item->right;
}
return cur_item;
}


Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!
Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

 

[Adrian P]

typedef int t_compare_func(const void *, const void *);

struct node *tree_search(struct node *root, const void *keyy,
t_compare_func *comp)
{
struct node *cur_item;
int result;
if (root == NULL) return NULL;
cur_item = root;
while (cur_item != NULL) {
result = (*comp)(cur_item->key, keyy);
if (result == 0)
break;
else if (result > 0)
cur_item = cur_item->left;
else
cur_item = cur_item->right;
}
return cur_item;
}


Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!
Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

You could try using recursion to search instead of iteration. That way you
never modify (or risk modifying) root. Your implementation may not allow for
recursion (ie if memory is limited). Also try looking for the C library "GNU
libavl 2.0.1" which has all tree manipulation functions.

 

[hzmonte]

Ok, but for the sake of discussion, let's stick with my code. Is there
any way for following good programming practice in this particular case?

 

[Malcolm]

typedef int t_compare_func(const void *, const void *);

struct node *tree_search(struct node *root, const void *keyy,
t_compare_func *comp)
{
struct node *cur_item;
int result;
if (root == NULL) return NULL;
cur_item = root;
while (cur_item != NULL) {
result = (*comp)(cur_item->key, keyy);
if (result == 0)
break;
else if (result > 0)
cur_item = cur_item->left;
else
cur_item = cur_item->right;
}
return cur_item;
}


Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!
Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

I don't see your problem here.
cur_item can be a const pointer (pointer to constant data), not a pointer
which is a constant (pointer whose value may not be modified).
You can then assign a non-const address to a const pointer, but you cannot
do the other thing without a cast, which is to assign a const pointer to a
normal non-const pointer.

 

[hzmonte]

This restriction prevents me from following good practice. and that's
exactly what i am talking about.

 

[Alex Fraser]

[snip]

Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!

If I understand correctly, this is equivalent to (for example) strchr(),
which doesn't modify its string argument but of course the caller may like
to write through the returned pointer (after checking it isn't NULL, of
course).

Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

IMHO, the best solution is to declare the root and cur_item pointers const,
and cast cur_item at the last possible moment - the return statement.

Alex

 

[hzmonte]

IMHO, the best solution is to declare the root and cur_item pointers const,
and cast cur_item at the last possible moment - the return statement.
Isn't that kind of casting is considered bad programming practice in
general?

 

[suresh]

and cast cur_item at the last possible moment - the return statement.
Isn't that kind of casting is considered bad programming practice in
general?

I see your point.

This is a typical problem of const qualifying a parameter. Even Ritchie
(K&R) had expressed his consern on a similar issue.
http://www.lysator.liu.se/c/dmr-on-noalias.html.

-suresh

 

[hzmonte]

Just for the record, according to
http://lxr.linux.no/source/lib/string.c#L254. strchr() is defined as
follows:
char * strchr(const char * s, int c)
{
for(; *s != (char) c; ++s)
if (*s == '\0')
return NULL;
return (char *) s;
}
Apparently the benefit of qualifying *s as const is considered as
outweighing the drawback of casting away the const-ness of s. Thanks.

 

[Robert Harris]

typedef int t_compare_func(const void *, const void *);

struct node *tree_search(struct node *root, const void *keyy,
t_compare_func *comp)
{
struct node *cur_item;
int result;
if (root == NULL) return NULL;
cur_item = root;
while (cur_item != NULL) {
result = (*comp)(cur_item->key, keyy);
if (result == 0)
break;
else if (result > 0)
cur_item = cur_item->left;
else
cur_item = cur_item->right;
}
return cur_item;
}


Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!
Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

You need to declare the function as returning a const struct node *
value (i.e. const struct node *tree_search(...)) Then it's OK to declare
root and cur_item as const.

Robert

 

[hzmonte]

So are you going to declare the "node" in the calling function 'const'
too? But you may have to modify it in the calling function!

 

[Jordan Abel]

[snip]

Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!

If I understand correctly, this is equivalent to (for example) strchr(),
which doesn't modify its string argument but of course the caller may like
to write through the returned pointer (after checking it isn't NULL, of
course).

Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

IMHO, the best solution is to declare the root and cur_item pointers const,
and cast cur_item at the last possible moment - the return statement.

Note: comp.std.c added.

This is an inherent concern with C. The const modifier has two slightly
different meanings.

When applied to an object definition, it means that the object may not
be modified. The implementation may place the object in a read-only
region.

It is also used with pointers. A const* basically means "I promise not
to modify the pointed-to object", which is appropriate for parameters to
a function that should not modify the pointed-to object.

Not exactly.

"const (type) *x" means *x is an object of type "const (type)", and thus
x is an object of type "pointer to const (type)". The declaration to get
z"const pointer-zto-(type)" would be "(type) * const x".

When a function returns a pointer derived from such a parameter, the
permissions for the returned pointer should logically revert to the
permissions the caller had for the pointer passed to the function: if
the caller passed a pointer to a const object, the returned derived
pointer should also be considered a pointer to const. If however, the
caller did not have the const modifier applied to the object, then it
logically would not have const restriction on using the returned derived
pointer. Currently there is no way in C to express the relationship
between a pointer argument and a return pointer.

Which unfortunately leads to such things as strchr

const char *something; // assume it's somehow initialized
char * constviol=strchr(something,*something);

 

[Chad]

You could try using recursion to search instead of iteration. That way you
never modify (or risk modifying) root. Your implementation may not allow for
recursion (ie if memory is limited). Also try looking for the C library "GNU
libavl 2.0.1" which has all tree manipulation functions.

I don't see how the current code could risk modifying the root. Can
anyone provide a corney example?

Thanks in advance.

Chad

 

[Thad Smith]

[snip]

Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!

If I understand correctly, this is equivalent to (for example) strchr(),
which doesn't modify its string argument but of course the caller may like
to write through the returned pointer (after checking it isn't NULL, of
course).

Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?

IMHO, the best solution is to declare the root and cur_item pointers const,
and cast cur_item at the last possible moment - the return statement.

Note: comp.std.c added.

This is an inherent concern with C. The const modifier has two slightly
different meanings.

When applied to an object definition, it means that the object may not
be modified. The implementation may place the object in a read-only
region.

It is also used with pointers. A const* basically means "I promise not
to modify the pointed-to object", which is appropriate for parameters to
a function that should not modify the pointed-to object.

When a function returns a pointer derived from such a parameter, the
permissions for the returned pointer should logically revert to the
permissions the caller had for the pointer passed to the function: if
the caller passed a pointer to a const object, the returned derived
pointer should also be considered a pointer to const. If however, the
caller did not have the const modifier applied to the object, then it
logically would not have const restriction on using the returned derived
pointer. Currently there is no way in C to express the relationship
between a pointer argument and a return pointer.

 

[kuyper]

Not exactly.

"const (type) *x" means *x is an object of type "const (type)",

Yes, and no. The type of the expression *x is 'const type', but the
object referred to by *x isn't required to have been declared with a
const-qualified type. In fact, most of the uses I've seen of
const-qualified pointers have been to refer to things that were not so
declared. The point of const-qualification of the pointed-at type is
that it triggers mandatory diagnostics if you write code that attempts
to modify it without an explicit cast to remove the const
qualification. Thus, Thad's description of the meaning is colloquially
correct.

... and thus
x is an object of type "pointer to const (type)". The declaration to get
z"const pointer-zto-(type)" would be "(type) * const x".

I don't believe that he wrote anything to suggest that he was unaware
of that fact.

 

[Jordan Abel]

Yes, and no. The type of the expression *x is 'const type', but
the object referred to by *x isn't required to have been declared
with a const-qualified type. In fact, most of the uses I've seen
of const-qualified pointers have been to refer to things that were
not so declared. The point of const-qualification of the
pointed-at type is that it triggers mandatory diagnostics if you
write code that attempts to modify it without an explicit cast to
remove the const qualification. Thus, Thad's description of the
meaning is colloquially correct.


I don't believe that he wrote anything to suggest that he was
unaware of that fact.

He suggested that const had a special meaning when applied to
pointer types that it did not on other objects, when in fact "const"
does not apply to the pointer in "const type *x"

 

[kuyper]

He suggested that const had a special meaning when applied to
pointer types that it did not on other objects, when in fact "const"
does not apply to the pointer in "const type *x"

He didn't say that the special meaning occured when "const" is applied
to the pointer type. He said that it has that meaning when used "with"
a pointer type. Specifically, it occurs when used with a pointer type
to qualify the type pointed at by the pointer. Since he explicitly
referred to a "const*" type, rather than a "*const" type, it's pretty
clear that he was correctly understanding the context in which "const"
does indead have a subtly different meaning, and his description of
that subtle difference was accurate.

 

[Mabden]

He didn't say that the special meaning occured when "const" is applied
to the pointer type. He said that it has that meaning when used "with"
a pointer type. Specifically, it occurs when used with a pointer type
to qualify the type pointed at by the pointer. Since he explicitly
referred to a "const*" type, rather than a "*const" type, it's pretty
clear that he was correctly understanding the context in which "const"
does indead have a subtly different meaning, and his description of
that subtle difference was accurate.

And so you snipped it out of the message? That's not very helpful...

Sorry, I got here late... ;-(

 

[kuyper]

And so you snipped it out of the message? That's not very helpful...

I try to keep quotations to a minimum. Most people with decent
newsreaders can look back at previous messages if they need to. People
with poor newsreaders should upgrade; if nothing else,
groups.google.com is available to anyone with a web browser. However,
because it's inconvenient to backtrack, and because many people
haven't yet upgraded to decent newsreaders, I do try to quote more than
the absolute minimum needed to supply adequate context. It's ultimately
a judgement call, and my judgement was (and remains) that I didn't need
to quote Thad's message. However, for your sake I'll give you a full
copy of the message from November 12th, which is the one I was
respondit to when I wrote "I don't believe ...":

[snip]

Here, I traverse the tree to find a node whose key member is the same
as keyy. And the node found is returned. Nothing in the tree is ever
modified. So naturally I would like to const-ify root (in the param
list). But then I am forced to also const-ify cur_item. And the return
value also has to be const-ifed as a consequence. Now, (part of) the
tree in the calling function cannot be modified as a consequence!


If I understand correctly, this is equivalent to (for example) strchr(),
which doesn't modify its string argument but of course the caller may like
to write through the returned pointer (after checking it isn't NULL, of
course).


Therefore I have to give up const-ifying root even though nothing in
the function modifies the tree. Can I avoid this side effect? I guess
I need to just cast root like:
cur_item = (struct node *)root;
if I decalre root as a const parameter. Right?
So I either have to give up const-ifying root or un-const-ifying root
inside the function? Any better solution?


IMHO, the best solution is to declare the root and cur_item pointers const,
and cast cur_item at the last possible moment - the return statement.

Note: comp.std.c added.

This is an inherent concern with C. The const modifier has two slightly
different meanings.

When applied to an object definition, it means that the object may not
be modified. The implementation may place the object in a read-only
region.

It is also used with pointers. A const* basically means "I promise not

Note that he's talking about "const*", not "*const"