tags:

views:

443

answers:

10

I have the following struct in C++:

struct routing_entry {
  unsigned long destSeq; // 32 bits
  unsigned long nextHop // 32 bits
  unsigned char hopCount; // 8 bits
};

And I have the following function:

routing_entry Cnode_router_aodv::consultTable(unsigned int destinationID ) {    
    routing_entry route;

    if ( routing_table.find(destinationID) != routing_table.end() )
        route = routing_table[destinationID];

    return route; // will be "empty" if not found
}

"routing_table" is a stl::map defined as follows:

map< unsigned long int, routing_entry > routing_table;

My question now is, when using the consultTable function, I want to check that the return value is actually initialized, some how like in Java pseudocode (because I come from the Java camp):

Route consultTable(int id) {
    Route r = table.find(id);
    return r;
}

then checking if r == null

A: 

You can't because the struct is there and the members are copied. You could throw an exception if there is nothing to fill in.

stefaanv
I prefer not to use exceptions because of possible inefficiencies.The way I saw it done using a vector was to create a vector like so: vector<int> empty;and return it if I determine that there is nothing to return, then when calling the function, I would check if the myvector.empty()But in my case here, I need to return a struct.
sabbour
You don't throw exceptions if it is normal not to have a route, but in this case you don't return structs, especially not if performance is an issue.
stefaanv
I think both performance costs are overestimated: exceptions and returning small structs by value.
Steve Jessop
A: 

Another way is to make your function return a status value (HRESULT or similar) indicating whether it was initialized, and pass the pointer to the struct as one of the parameters.

In C++, it's common to return a status indicating the error code (or 0 if success), but this of course depends on your programming habits.

Simply passing a pointer and checking for null would work anyway.

Groo
+14  A: 

There are a few problems here. The most urgent may be what happens when the destination ID is not found. Since you have no constructor on the routing_entry and you are not default initialising, it will have undefined values.

// the data inside route is undefined at this point
routing_entry route;

One way to handle this is to default initialise. This works by instructing the compiler to fill the structure with zeros. This is kind of a trick borrowed from C but it works well here.

routing_entry route={0};

You mention you are coming from Java, unlike in Java, structure and class members are not 0 initialised, so you should really handle that somehow. Another way is to define a constructor:

struct routing_entry
{
  routing_entry()
  : destSeq(0)
  , nextHop(0)
  , hopCount(0)
  { }

            unsigned long destSeq;  // 32 bits
            unsigned long nextHop;   // 32 bits
            unsigned char hopCount; // 8 bits
};

Also note that in C++, the size of the integer and char members is not defined in bits. The char type is 1 byte (but a byte is a not defined, but usually 8 bits). The longs are usually 4 bytes these days but can be some other value.

Moving on to your consultTable, with the initialisation fixed:

routing_entry Cnode_router_aodv::consultTable(unsigned int destinationID )
{    
  routing_entry route={0};

  if ( routing_table.find(destinationID) != routing_table.end() )
        route = routing_table[destinationID];

  return route; // will be "empty" if not found
}

One way to tell might be to check if the structure is still zeroed out. I prefer to refactor to have the function return bool to indicate success. Additionally, I always typedef STL structures for simplicity, so I'll do that here:

typedef map< unsigned long int, routing_entry > RoutingTable;
RoutingTable routing_table;

Then we pass in a reference to the routing entry to populate. This can be more efficient for the compiler, but probably that is irrelevant here - anyway this is just one method.

bool Cnode_router_aodv::consultTable(unsigned int destinationID, routing_entry &entry)
{
  RoutingTable::const_iterator iter=routing_table.find(destinationID);
  if (iter==routing_table.end())
    return false;
  entry=iter->second;
  return true;
}

You would call it like this:

routing_entry entry={0};
if (consultTable(id, entry))
{
  // do something with entry
}
1800 INFORMATION
This looks good. Another way is if you really wanted to return the routing_entry is having a function on your struct called empty() or something which would return whether your member values were still the same as their default values.
Salgar
That's really helpful :) You opened my eyes to a lot of things!
sabbour
+1: Small point: the 0 isn't needed in the initialisers: routing_entry entry = {}; is fine.
James Hopkin
+2  A: 

This is typical solution for your problem:

bool Cnode_router_aodv::consultTable(unsigned int destinationID, 
                                     routing_entry* route ) {    
  if ( routing_table.find(destinationID) != routing_table.end() ) {
    *route = routing_table[destinationID];
    return true;
  }
  return false;
}

Instead of a pointer you could use a reference; it's a matter of style.

Igor Krivokon
A: 

As an alternative to the input - output parameter solution, you could follow Uncle Bobs advice and create a entry reader class.

typedef map< unsigned long int, routing_entry > routing_table_type;
routing_table_type routing_table;


//Is valid as long as the entry is not removed from the map
class routing_entry_reader 
{
    const routing_table_type::const_iterator routing_table_entry;  
    const routing_table_type& routing_table;

public: 
    routing_entry_reader( const routing_table_type& routing_table, int destination_id ) 
    : routing_table(routing_table),
      routing_table_entry( routing_table.find(destination_id) ) { 
    }

    bool contains_entry() const { 
        return  routing_table_entry!=routing_table.end(); 
    }

    const routing_entry& entryByRef() const {
        assert(contains_entry());
        return routing_table_entry->second;
    }
};


routing_entry_reader entry_reader(routing_table, destination_id);
if( entry_reader.contains_entry() )
{
    // read the values from the entry
}
TimW
A: 

shared_ptr<routing_entry> Cnode_router_aodv::consultTable(unsigned int destinationID ) {    
  shared_ptr<routing_entry> route;

  if ( routing_table.find(destinationID) != routing_table.end() )
    route.reset( new routing_entry( routing_table[destinationID] ) );

  return route; // will be "empty" if not found
}

// using
void Cnode_router_aodv::test() 
{
  shared_ptr<routing_entry> r = consultTable( some_value );
  if ( r != 0 ) {
    // do something with r
  }
  // r will be freed automatically when leaving the scope.
}

Kirill V. Lyadvinsky
+3  A: 

The best way I've found for this is to use boost::optional, which is designed to solve exactly this issue.

Your function would look something like this:-

boost::optional<routing_entry> consultTable(unsigned int destinationID )
{    
  if ( routing_table.find(destinationID) != routing_table.end() )
    return routing_table[destinationID];
  else
    return boost::optional<routing_entry>()
}

And your calling code looks like

boost::optional<routing_entry> route = consultTable(42);
if (route)
  doSomethingWith(route.get())   
else
  report("consultTable failed to locate 42");

Generally, the use of "out" parameters (passing a pointer - or reference - to an object which is then "filled in" by the called function is frowned on in C++. The approach that everything "returned" by a function is contained in the return value, and that no function parameters are modified can make code more readable and maintainable in the long term.

Roddy
Nice, I like too!
sabbour
A: 

G'day,

Agreeing with most of what 1800 has to say, I'd be more inclined to make your function consultTable return a pointer to a routing_entry structure rather than a boolean.

If the entry is found in the table, the function returns a pointer to a new routing_entry. If it is not found, then it returns NULL.

BTW Good answer, 1800.

HTH

cheers,

Rob Wells
I think the last thing a recent Java -> C++ convert should do is write functions returning pointers to newly-allocated heap objects. Memory leaks ahoy! ;-)
Steve Jessop
@1by1, that's true. Maybe even worse if they stick their head in the sand and ignore memory management when they can't spot a memory leak in the first place? He's in C++ land. The genie is out of the bottle! (-:
Rob Wells
I've been suffering with memory leaks but I recently discovered valgrind, helped me a bit!
sabbour
+1  A: 

First note that in C++, unlike in Java, users can define value types. This means that there are 2^32 * 2^32 * 2^8 possible values for a routing_entry. If you want, you can think of routing_entry as a 72-bit primitive type, although you have to be a bit careful with the analogy.

So, in Java route can be null, and there are 2^32 * 2^32 * 2^8 + 1 usefully different values for a routing_entry variable. In C++, it cannot be null. In Java "empty" might mean returning a null reference. In C++ only pointers can be null, and routing_entry is not a pointer type. So in your code in this case "empty" means "I have no idea what value this thing has, because I never initialized it or assigned to it".

In Java, a routing_entry object would be allocated on the heap. In C++ you don't want to do that unless you have to, because memory management in C++ takes effort.

You have a few (good) options:

1) add a field to the routing entry, to indicate that it has been initialised. Chances are this won't make the struct any bigger, because of padding and alignment requirements of your implementation:

struct routing_entry {
    unsigned long destSeq;  // 32 bits on Win32. Could be different.
    unsigned long nextHop   // 32 bits on Win32. Could be different.
    unsigned char hopCount; // 8 bits on all modern CPUs. Could be different.
    unsigned char initialized; // ditto
};

Why not use bool? Because the standard helpfully allows sizeof(bool) != 1. It's entirely possible that a bool is implemented as an int, especially if you have an oldish C++ compiler. That would make your struct bigger.

Then make sure the struct is inited with 0 values in your function, instead of whatever garbage was on the stack:

routing_entry Cnode_router_aodv::consultTable(unsigned int destinationID ) {    
    routing_entry route = {};

    if ( routing_table.find(destinationID) != routing_table.end() )
        route = routing_table[destinationID];

    return route; // will be "empty" if not found
}

And make sure that all the entriess in the map have the initialized field set to non-zero. Caller then checks initialized.

2) Use "magic" values of the existing fields as markers.

Suppose for the sake of argument that you never deal in routes with hopCount 0. Then as long as you 0-initialize as above, callers can check hopCount != 0. The max values of the types are also good flag values - since you're restricting your routes to 256 hops, chances are you won't do any harm by restricting them to 255 hops. Rather than callers having to remember this, add a method to the struct:

struct routing_entry {
    unsigned long destSeq;  // 32 bits
    unsigned long nextHop   // 32 bits
    unsigned char hopCount; // 8 bits
    bool routeFound() { return hopCount != (unsigned char)-1; }
};

Then you'd initialise like this:

routing_entry route = {0, 0, -1};

or if you're worried what happens when you change the order or number of fields in future:

routing_entry route = {0};
route.hopCount = -1;

And the caller does:

routing_entry myroute = consultTable(destID);
if (myroute.routeFound()) {
    // get on with it
} else {
    // destination unreachable. Look somewhere else.
}

3) Caller passes in a routing_entry by pointer or non-const reference. Callee fills the answer into that, and returns a value indicating whether it succeeded or not. This is commonly called an "out param", because it sort of simulates the function returning a routing_entry and a bool.

bool consultTable(unsigned int destinationID, routing_entry &route) {    
    if ( routing_table.find(destinationID) != routing_table.end() ) {
        route = routing_table[destinationID];
        return true;
    }
    return false;
}

Caller does:

routing_entry route;
if (consultTable(destID, route)) {
    // route found
} else {
    // destination unreachable
}

By the way, when using a map your code as it is looks up the ID twice. You can avoid this as follows, although it's unlikely to make a noticeable difference to the performance of your app:

map< unsigned long int, routing_entry >::iterator it =
    routing_table.find(destinationID);
if (it != routing_table.end()) route = *it;
Steve Jessop
Thanks, that was pretty helpful!
sabbour
A: 

Hi:

In your method

routing_entry Cnode_router_aodv::consultTable(unsigned int destinationID ) {

    routing_entry route;
    ...
    return route;
}

You are trying to return an automatic, i.e. the object is on the local stack frame, object. This will never do what you want it to do as this memory is not available when the function goes out of scope.

You will need to create the object, and then return the newly created object. I suggest you consult Scott Meyers Effective C++ Third Edition, Item #21.

gthuffman