<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Jan 25, 2012, at 9:44 PM, Preston Briggs wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Reading the LLVM Programmer's Manual, the description of DenseSet mentions:<div><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="arial, helvetica, sans-serif"><i><span style="text-align:left">Note that DenseSet has the same requirements for the value type that </span><a href="http://llvm.org/docs/ProgrammersManual.html#dss_densemap" style="text-align:left">DenseMap</a><span style="text-align:left"> has.</span></i></font></div>
</blockquote><font face="Times"><br></font><div><font face="arial, helvetica, sans-serif">But when I read about DenseMap, I don't really see any requirements for the values, just a warning about space.</font></div></div></blockquote><div><br></div><div>DenseSet<T> is implemented as a DenseMap<T,char>, so requirements for DenseMap keys apply. It seems the documentation could be clearer.</div><div><br></div><div>If your elements are pointers, SmallPtrSet<> is a better choice.</div><br><blockquote type="cite"><div><div><font face="arial, helvetica, sans-serif"> On the other hand, the <i>keys</i> have special requirements, which aren't entirely clear to me. It says</font></div>
</div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="arial, helvetica, sans-serif"><br></font></div><div><span style="text-align:left"><font face="arial, helvetica, sans-serif"><i>Finally, you must implement a partial specialization of DenseMapInfo for the key that you want, if it isn't already supported. This is required to tell DenseMap about two special marker values (which can never be inserted into the map) that it needs internally.</i></font></span></div>
<div><span style="text-align:left"><font face="arial, helvetica, sans-serif"><br></font></span></div></blockquote><div style="text-align:left"><font face="arial, helvetica, sans-serif">Will my code fail to compile if the required specialization of DenseMapInfo is not present?</font></div></blockquote><div><br></div><div>Yes. The non-specialized DenseMapInfo template doesn't provide any of the required methods.</div><br><blockquote type="cite">
<div style="text-align:left"><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif; ">I wonder all these things because I've tripped across a problem where a method hangs repeatably, and I don't see the problem.</span></div>
<div style="text-align:left"><font face="arial, helvetica, sans-serif"><br></font></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div style="text-align:left"><div><font face="'courier new', monospace">typedef SmallVector<BasicBlock *, 4> Frontier;</font></div>
</div><div style="text-align:left"><div><font face="'courier new', monospace">DenseMap<BasicBlock *, Frontier> frontier(blocks*3/2);</font></div></div></blockquote></blockquote><div><br></div><div>Pointer keys work fine, you don't need to provide any specializations for that.</div><br><blockquote type="cite"><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div style="text-align:left"><div><font face="'courier new', monospace"><br>
</font></div><div><font face="'courier new', monospace">BasicBlock *Xblock = ...</font></div><div><font face="'courier new', monospace"><br></font></div></div><div style="text-align:left"><div><font face="'courier new', monospace">errs() << "start\n";</font></div>
</div><div style="text-align:left"><div><font face="'courier new', monospace">Frontier &f = frontier[Xblock]; // Xblock is not yet represented in frontier</font></div></div><div style="text-align:left"><div>
<font face="'courier new', monospace">errs() << "finish\n";</font></div></div></blockquote><div style="text-align:left"><font face="arial, helvetica, sans-serif"><div><br></div><div>It compiles fine (as part of a function-level pass), but the call frontier[Xblock] fails (hangs) after several successful calls. I tried replacing the declaration of frontier with </div>
<div><br></div></font></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div style="text-align:left"><div><font face="'courier new', monospace">DenseMap<BasicBlock *, Frontier *> frontier(blocks*3/2);</font></div>
</div></blockquote><font face="arial, helvetica, sans-serif"><div><font face="arial, helvetica, sans-serif"><br></font></div>but trip over the same problem in the same place.<br></font><div style="text-align:left"><font face="arial, helvetica, sans-serif"><div>
<br></div><div>I've used the DenseMap successfully in several other places, so I'm not sure that's gone wrong here.</div><div><br></div><div>Any ideas?</div></font></div></blockquote><div><br></div><div>DenseMap iterators are invalidated by any container mutation. That is different behavior from std::map. Same thing for pointers and references to elements in the container. DenseMap invalidation works more like std::vector. It is not clear from your code if that is our problem.</div><div><br></div><div>I don't recall seeing a DenseMap::operator[] hanging. Most likely, the backing memory was corrupted somehow.</div><div><br></div><div>/jakob</div><div><br></div></div></body></html>