1st post in LONG time!
Patrick Mendoza
OBHACK: I tend to come up with outrageous ideas/inventions from time to
time. Some call it a gift, some a curse. But for me its usually for fun
exploration of life in general. I thought of an "odor capture" gadget
like 2 years ago... Basically, small and portable it "captures" odors
from where you're at and "stores" the odor into this gadget. Too bad I
can NEVER make my inventive ideas IRL, but this is one of many I've
thought of.
You can see my drawing of the odor device here:
http://www.speakeasy.org/~rmendoza/ideas/odorcamera.jpg
jpd
Law enforcement would be very happy with that. The germans are already
taking ``samples'' from evil people like, oh, anti-globalism protesters
and storing them for future reference. Reproduction good enough for
search dogs would be a challenge, though.
ObHack: I have this C++ template class that builds a queue out of a
singly-linked list. In certain cases I need to go over the queue and
delete some elements. Only, the simplistic implementation is O(n)
because the list will have to first figure out the prior element. The
easy solution would be to use a doubly-linked list, but there's another:
Make the iterator a pointer to the previous element. It means iterator
dereferences now dereference two pointers and the solution is a tad
brittle if you're doing more fancy things than walk over and delete some
elements, but hey, only one pointer overhead per list element.
--
j p d (at) d s b (dot) t u d e l f t (dot) n l .
This message was originally posted on Usenet in plain text.
Any other representation, additions, or changes do not have my
consent and may be a violation of international copyright law.
Wim Lewis
jpd <read_t...@do.not.spam.it.invalid> wrote:
>because the list will have to first figure out the prior element. The
>easy solution would be to use a doubly-linked list, but there's another:
>Make the iterator a pointer to the previous element.
How does the iterator represent the first element?
In similar situations I will sometimes (ObVerySmallHack) have a cursor
of type pointer-to-pointer-to-element. It starts out pointing to the variable
holding the head of the list, and later points to the "next" field in
the previous list element. This way, removing an element is simply
*cursor = *cursor->next;
without any special cases for the first or last element, empty lists, etc.
It's also handy for structures with more than one outgoing link (like
trees) where you can point to the specific outgoing link you're interested in.
--
Wim Lewis <wi...@hhhh.org>, Seattle, WA, USA. PGP keyID 27F772C1
jpd
On 08 May 2008 19:16:23 GMT, Wim Lewis <wi...@hhhh.org> wrote:
> In article <slrnfv98a5.1cn...@mantell0.local>,
> jpd <read_t...@do.not.spam.it.invalid> wrote:
>>because the list will have to first figure out the prior element. The
>>easy solution would be to use a doubly-linked list, but there's another:
>>Make the iterator a pointer to the previous element.
>
> How does the iterator represent the first element?
The node struct is split up in a head_struct that contains a next pointer
(of type actual_struct), and an actual struct that inherits from that and
adds the contents to be stored. The first pointer is a head_struct instance
which can be static_cast<actual_struct *>(&_first) and then used as normal.
Because resolving *always* hops to the next pointer first, this is safe.
> In similar situations I will sometimes (ObVerySmallHack) have a cursor
> of type pointer-to-pointer-to-element. It starts out pointing to
> the variable holding the head of the list, and later points to the
> "next" field in the previous list element. This way, removing an
> element is simply *cursor = *cursor->next; without any special cases
> for the first or last element, empty lists, etc.
I think that's basically what I did, except I've packed it into C++
idioms and added a bit of template sugar.
> It's also handy for structures with more than one outgoing link (like
> trees) where you can point to the specific outgoing link you're
> interested in.
... except for that. Upside of providing an iterator struct with a
custom deref is that it can be fed to a number (but probably not all) of
stl-provided algorithms. Been a while since I last toyed with it, though.
ObIwontbethefirsttothinkofthisHack: I'm toying around with custom
outputstreams. C++ streams work by overloading operator<< a lot, so
making my own isn't difficult, if I'm willing to settle for something
that doesn't have all the bells and whistles of regular streams (EG no
formatting using stream manipulators), but has gongs and flags I do want
(say, a method printf() to ease integration with legacy code and save
*lots* of strcat(), strlen(), sprintf(buf,"%s ...",buf, ...) calls).
My stream components are templates that add functionality at will,
like, oh, inspecting the stream for certain sequences and replacing
them with something else. Think telnet {cr->cr\0,lf->crlf,iac->iaciac}
translation and getting more involved from there. This takes lots
individual character inspection, several layers deep.
To speed things up a bit, one such template will do a quick scan for the
known slowpath triggers and puts everything that doesn't match on the
fastpath to the end of the pipe (and has glue to make it stick). I'd like
to parametrise that, without passing it as a constructor parameter as that
is a bit involved, and storing a pointer eats up space in the stream for a
variable that won't ever change over its lifetime. So, I'd like to pass a
const char * through a template parameter. But I can't.
I can, of course, create a type with static members that return the
desired const char * and its length, then pass that as an argument.
#define FASTPATH_FILTER(a,b) struct a { \
static const char *c_str() { return b; } \
static const char *data() { return c_str(); } \
static size_t size() { return sizeof(b)-1; } \
}
FASTPATH_FILTER(fp_telnet_line_encoding,"\377\r\n");
So then the outputstream definition becomes something like:
typedef
streamfrontend<
speedstream<fp_telnet_line_encoding, telnet_line_encoding< brakestream<
streambackend > > > >
outputstream;
speedstream uses a chained method (`bool brake() const') to know when
it can resume fastpathing, so brakestream terminates that and folds the
fastpath back into the normal stream.
It's a lot of glue to just pass a const char *, but that's par for the
course for C++. Because of how the whole thing is setup it uses both
strcspn() and memcspn() so I'm providing both c_str() and data()+size().
I might change to const members instead of statics at some point, but
I don't really see why, either way, as of this writing.
The filter string requires manual intervention to get right, so it
doesn't solve the trick of interrogating all the underlying layers for
their trigger characters and combining them in a const char[] at compile
time. I don't quite see how that would be possible in C++ without
preprocessor tricks and how that would work together with templates I
don't see (yet?) either. Ideas?