<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><BR><DIV><DIV>On Jul 14, 2007, at 7:12, Paul Lindner wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Helvetica" size="3" style="font: 12.0px Helvetica">* Wildcard (regex deletes)</FONT></P> </BLOCKQUOTE></DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>There actually was some good discussion around wildcard deletes. It'd be good to capture some of that.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>As I understand it, the plan worked something like this:</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>There would be a ``rule list'' that was a sequential list of deletion rules to be applied. For example:</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>rule 11: /^dvd:/</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>rule 12: /^something:/</DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>...</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>Each item in the cache would have a latest rule applied indicator. When an item was to be retrieved from the cache, we'd check to see if any rules had been created since the last access, and if so, each rule would be evaluated against the item's key, and then the rule pointer would be updated.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>The typical overhead on a key fetch would be a fetch and number comparison. Deletions would be O(n) (n == items in the cache), but be amortized over cache retrievals. The actual queueing of a rule is O(1). In many cases, items may naturally expire, or be subject to LRU before retrieval, so normal case *may* be better. Worst case, a *lot* of rules get added in a short period of time, and then we go around looking for all of the keys.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>As for rule cleanup, each rule would also have a reference count. I don't exactly know how this would work, but the basic idea is that when a rule is added, the reference count is set to the number of items in the cache. Each time an item is retrieved, it'd walk through the rules that have not been applied, apply them, and decrement the count. The count would also have to be decremented when an item was deleted, replaced, or fell out due to LRU. When the reference count hits 0, the rule is no longer needed.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>I imagine the whole thing could be implemented with a linked list. An item in the cache would have a pointer to the latest applied item. if item->next, there's stuff to do.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>I'm not sure how important the regex is for this vs. simple prefix deletion. There'd need to be a regex engine. The PCRE code really scares me.</DIV><BR><DIV>-- </DIV><DIV>Dustin Sallings</DIV></BODY></HTML>