Databases
StackOverflow2013
Postsdbo
POhaving trouble returning a best possible interface from a set of routing entries
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POhaving trouble returning a best possible interface from a set of routing entries
    primarykey
    data
    text
    <p>so i am trying to return a best possible matching interface from routing entries. However, it is not exactly working the way i want it to. I got 5 out 6 values returned the way should be but I am pretty sure I have a million entries in a routing table my algorithm would not work. I am using Binary Search to solve this problem. But, for example, the interface that i want to return has a ipaddress which is smaller than the ipaddress i am passing as an argument, then the binary search algorithm does not work. the structure looks like this:</p> <pre><code>struct routeEntry_t { uint32_t ipAddr; uint32_t netMask; int interface; }; routeEntry_t routing_table[100000]; </code></pre> <p>let's say the routing table looks like this:</p> <p>{ 0x00000000, 0x00000000, 1 }, // [0]</p> <p>{ 0x0A000000, 0xFF000000, 2 }, // [1]</p> <p>{ 0x0A010000, 0xFFFF0000, 10 }, // [2]</p> <p>{ 0x0D010100, 0xFFFFFF00, 4 }, // [3]</p> <p>{ 0x0B100000, 0xFFFF0000, 3 }, // [4]</p> <p>{ 0x0A010101, 0xFFFFFFFF, 5 }, // [5]</p> <p>Example input/output:</p> <ol> <li>Regular search</li> </ol> <p>Input: 0x0D010101 Output: 4 (entry [3])</p> <p>Input: 0x0B100505 Output: 3 (entry [4])</p> <ol> <li>To find an arbitrary address, it should go to the default interface.</li> </ol> <p>Input: 0x0F0F0F0F Output: 1 (entry [0])</p> <ol> <li>To find an address that matches multiple entries, take the best-match.</li> </ol> <p>Input: 0x0A010200 Output: 10 (entry [2])</p> <p>Input: 0x0A050001 Output: 2 (entry [1])</p> <p>Input: 0x0A010101 Output: 5 (entry [5])</p> <p>But my output looks like 2, 3, 1, 10, 1, 5. I don't understand where I am messing things up. Could you please explain where I am doing wrong? any help would be great. Thanks in advance. However this is what my algorithm looks like (assuming the entries are sorted):</p> <pre><code>int interface(uint32_t ipAddr) </code></pre> <p>{ int start = 0;</p> <pre><code>int end = SIZE-1; int mid = 0; vector&lt;int&gt; matched_entries; vector&lt;int&gt;::iterator it; matched_entries.reserve(SIZE); it = matched_entries.begin(); if (start &gt; end) return -1; while (start &lt;= end) { mid = start + ((end-start)/2); if (routing_table[mid].ipAddr == ipAddr) return routing_table[mid].interface; else if (routing_table[mid].ipAddr &gt; ipAddr) { uint32_t result = routing_table[mid].netMask &amp; ipAddr; if (result == routing_table[mid].ipAddr) { matched_entries.push_back(mid); } end = mid-1; } else { uint32_t result = routing_table[mid].netMask &amp; ipAddr; if (result == routing_table[mid].ipAddr) { matched_entries.insert(it,mid); } start = mid+1; } } int matched_ip = matched_entries.back(); if (routing_table[matched_ip].netMask &amp; ipAddr) return routing_table[matched_ip].interface; else return routing_table[0].interface; </code></pre> <p>}</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCharles
    1. USSherCoder
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POhaving trouble returning a best possible interface from a set of routing entries
      1. USSherCoder
      1. VTFavorite
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload