[tatikiran]

Hi,
getClosestTo function supposed to return "uMaxRequired" number of closest nodes to the target but it is not returning. I think let say we asked for 11 closest nodes and we went to leaf node at level 4 with zoneIndex 6 and got 7 nodes so we next ask for remaining 4 nodes in level 4 with zoneIndex 7, at this time we have 7 nodes in the results and we are asking for in the next bin for 4 nodes. Irrespective of number of nodes added in the next leaf node, the RoutingBin will delete the entries becuase the results has already has(7) more than (4) it needed.

[Unknown1]

Hmm, I will look at this right away... This may answere something I've been noticing..

[Unknown1]

After looking at this, I don't see any error here..

Look a little closer to the recursion..

When I finally get the to a zone with a the leaf, it will get the 7. It then sets found to 7. Since, 7 is less then the 11, it then asks the other leaf of that zone for 4 max. Lets say that leaf returns 1.. It then sets found to 8.. Now backs up one zone which then sets it's found to 8. Since 8 is less then 11, it then asks it's other branch (Or leaf if there is no branch) for more nodes with max a 3. If that returns 3 nodes, found is set to 11.. Now all zones just return back the results with found 11..

[tatikiran]

Unknown1, on Feb 3 2006, 09:34 PM, said:

After looking at this, I don't see any error here..

Look a little closer to the recursion..

Let say we called RoutingZone(2, target, distance,  11, results)

When I finally get the to a zone with a the leaf, it will get the 7. It then sets found to 7.

Since, 7 is less then the 11, it then asks the other leaf of that zone for 4 max.

at this point we will call routingBin(2, target, distance, 4, results) (The more important thing is that results has already 7 entries)

Lets say that leaf returns 1.. It then sets found to 8..

but routingBin has a conditionin the end
while(pmapResult->size() > uMaxRequired) {
// remoe the extra ones
}

in this case results has 8 entries and uMaxRequired is 4 so we are going to remove the 4 entries from the results but it returns the remaining the size of "results" so it returns 4.

(in fact we shouldn't remove any thing from the results). Fortunatly the recursion computes the n umber of nodes in the results as 11 and returns properly and ends the serach. This function returns the number of entries in the results again and again in recursion so we will always exit from the recursion.


Now backs up one zone which then sets it's found to 8. Since 8 is less then 11, it then asks it's other branch (Or leaf if there is no branch) for more nodes with max a 3. If that returns 3 nodes, found is set to 11.. Now all zones just return back the results with found 11..

let me go through one concrete example. Say we are looking for target and distance between this target and nodeid is 0x00000000.... and the this node has 17 levels on the left most tree and 17th level is leaf. At 16th level we have only two nodes with zoneIndex 0 and 1. These two nodes have 7 and 4 entries.

/
/
/
0 level 16 (Node - X)
/ \
/ \
/ \
/ \
(Node - Y) (Node - Z)

Node Y and Z are leafs and each has 7 and 1 entries respectively.

X->getClosestTo(2, target, 0x0000, results)

first we goes to Node Y
and it returns 7 entries in results
found will be 7
we still need 4 more so
we will call Z's Bin->getClosestTo(2, target, 4, results) (Note that results has already 7 entries)
now we will add 1more to the results and results will have 8 entries
and at the start of while loop results has 8 entries and we need only 4 (not 11) so
we will remove 4 more from the results and then return result's size which is 4

We are now finished the 16th level and return 11 (7 from the first bin and 4 from the second bin), so we to parent of X and at this point we got 11 so we return and everybody returns and we reach root and we return only 4 entries instead of 11.


Kiran

[Unknown1]

Yep.. Got it.. Guess I shouldn't look at it while trying to get my son in bed.. Will be correct in next release.. Thanks.. And yes, this is the issue I was trying to track down..

[tatikiran]

Unknown1, on Feb 3 2006, 10:57 PM, said:

Yep.. Got it.. Guess I shouldn't look at it while trying to get my son in bed.. Will be correct in next release.. Thanks.. And yes, this is the issue I was trying to track down..

I could patch this bug. but i don't know submit the code for this. Let me know if it ok to fix.

Kiran

[tatikiran]

tatikiran, on Feb 12 2006, 12:48 PM, said:

Unknown1, on Feb 3 2006, 10:57 PM, said:

Yep.. Got it.. Guess I shouldn't look at it while trying to get my son in bed.. Will be correct in next release.. Thanks.. And yes, this is the issue I was trying to track down..

I could patch this bug. but i don't know submit the code for this. Let me know if it ok to fix.

Kiran

Here is correct code snippent to fix this bug in RoutingBin.cpp file. Could you please include this in the next release.

uint32 CRoutingBin::getClosestTo(uint32 maxType, const CUInt128 &target, const CUInt128& WXUNUSED(distance), uint32 maxRequired, ContactMap *result, bool emptyFirst, bool inUse)
{
if (m_entries.size() == 0) {
return 0;
}

if (emptyFirst) {
result->clear();
}

//Put results in sort order for target.
uint32 added = 0;
ContactList::const_iterator it;
for (it = m_entries.begin(); it != m_entries.end(); ++it) {
if((*it)->getType() <= maxType) {
CUInt128 targetDistance((*it)->getClientID());
targetDistance.XOR(target);
(*result)[targetDistance] = *it;
if( inUse ) {
(*it)->incUse();
}
added++;
}
}

//Remove any extra results
while(added > maxRequired) {
if( inUse ) {
(--result->end())->second->decUse();
}
result->erase(--result->end());
added--;
}

return added;
}

[Masta2002]

i think john already postet a fix for this! Look here
http://forum.emule-p...showtopic=99316