Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>OK, the issue is, if you want your ranges to span all of n-bits, any calculations based on start/end has the potential to overflow.</p> <p>So the trick is to do a linear transform to a place where your start/end calculations do not overflow, do your calcs, and then linear transform back.</p> <p><strong>NOTES</strong></p> <p>Below the <em>we can safely call end() now</em> line, you can call the ordering checks (your original code) and it will be safe since the ordering is preserved during a linear transform.</p> <p>Also, as I noted in the previous post, there is a special boundary case where even if you do this transform, you will overflow (where you span the entire line) - but you can code for that special boundary condition.</p> <p><strong>OUTPUT</strong></p> <p>5 11</p> <p><strong>CODE</strong></p> <pre><code>#include &lt;iostream&gt; using type = uint8_t; struct segment { type start, length; type end() const { return start + length; } }; static segment intersect( segment s, segment t ) { type shift = std::min( s.start, t.start ); // transform so we can safely call end() s.start -= shift; // doesn't affect length t.start -= shift; // doesn't affect length // we can safely call end() now ---------------------------------------------- type u_start = std::max( s.start, t.start ); type u_end = std::min( s.end(), t.end() ); type u_length = u_end - u_start; segment u{ u_start, u_length }; // transform back u.start += shift; return u; } int main() { segment s{ 3, 13 }, t{ 5, 11 }; segment u = intersect( s, t ); std::cerr &lt;&lt; uint32_t( u.start ) &lt;&lt; " " &lt;&lt; uint32_t( u.length ) &lt;&lt; std::endl; return 0; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POSimple interval/range intersection with overflow
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USkfmfe04
    1. USkfmfe04
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI see no mistakes in my diagrams. There are 16 values (16 gaps between two marks): 0 through F. Also, in a 3-bit system there are 8 values: 0 through 7. So starting at 0, to have everything in an interval, the length of the interval is 8, not 6. In a 1 bit system there are 2 values: 0 and 1 (2^1 - 1). Starting at 0, my full interval has a length of 2 (2^1).
      singulars
      1. PO
      1. USVirtlink
    2. CO@Virtlink if you choose to have 16 values for intervals, your start and end points will have to go from 0 - 0 (which looks like overflow). Anyhow, my answer still stands. If you want to use the entire range of 16 values, you can do it with a combination of the shift (so you can do start/end math without overflow) and the cheat (simplification at the boundary where length==15 or length==16 depending on your convention and requirements). But I would comment heavily to avoid confusion (explaining why you need all this extra complexity).
      singulars
      1. PO
      1. USkfmfe04
    3. COI'm writing a physical memory manager that gets some ranges of memory from the BIOS that are not used by crucial system data. Each range has `0 <= start <= 2^32 - 1` and `0 <= length <= 2^32`. It is not a requirement that the lengths are non-zero, just that I already filtered out the zero-length ranges. You code with `if (length==max_len)` won't work for most cases. For example, with 16 values, if for S I start at value 15 (the last value) with a length of 1, I end up with an end of `15 + 1 = 0`. Yes, it not only looks like overflow, it actually is.
      singulars
      1. PO
      1. USVirtlink
 

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