Bit testing

[David Mott]

Hi all, hope someone can help me with an algorithm.

I have a bitmap representing available pages in a file. A
GetPage(PageCou nt) function should return the offset into the file where
PageCount of contiguous pages resides. Within the function I have a pointer
to the bitmap and want to scan the bitmap until PageCount of free bits is
found. For example assume the following bitmap is present in memory:

101011001100011 010100001111110 11001011001

If I wanted to retrieve the offset where 4 bits are free, the
FindFreeBitsInB itmap(4) function should return 18 (the location of 0000)

My FindFreeBitsInB itmap(BitCount) function should scan the block of memory
until it encounters BitCount of free bits. Then should return the offset
into the block where the free bits occur. There's several approaches to
this problem, can someone provide me with a very efficient algorithm to
locate the starting offset? This function resides in a DBMS and should be
very efficient as it's called very frequently. An assembler routine is also
an option. All input is greatly appreciated.

Cheers,
David

[Gianni Mariani]

Re: Bit testing

David Mott wrote:[color=blue]
> Hi all, hope someone can help me with an algorithm.
>
> I have a bitmap representing available pages in a file. A
> GetPage(PageCou nt) function should return the offset into the file where
> PageCount of contiguous pages resides. Within the function I have a pointer
> to the bitmap and want to scan the bitmap until PageCount of free bits is
> found. For example assume the following bitmap is present in memory:
>
> 101011001100011 010100001111110 11001011001
>
> If I wanted to retrieve the offset where 4 bits are free, the
> FindFreeBitsInB itmap(4) function should return 18 (the location of 0000)
>
> My FindFreeBitsInB itmap(BitCount) function should scan the block of memory
> until it encounters BitCount of free bits. Then should return the offset
> into the block where the free bits occur. There's several approaches to
> this problem, can someone provide me with a very efficient algorithm to
> locate the starting offset? This function resides in a DBMS and should be
> very efficient as it's called very frequently. An assembler routine is also
> an option. All input is greatly appreciated.[/color]

This is off-topic on comp.lang.c++ since there is nothing specific in
your question about C++ - try comp.programmin g or an algorithms group.

[David Mott]

Re: Bit testing



"Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
news:buq7f6$470 @dispatch.conce ntric.net...[color=blue]
> David Mott wrote:[color=green]
> > Hi all, hope someone can help me with an algorithm.
> >
> > I have a bitmap representing available pages in a file. A
> > GetPage(PageCou nt) function should return the offset into the file where
> > PageCount of contiguous pages resides. Within the function I have a[/color][/color]
pointer[color=blue][color=green]
> > to the bitmap and want to scan the bitmap until PageCount of free bits[/color][/color]
is[color=blue][color=green]
> > found. For example assume the following bitmap is present in memory:
> >
> > 101011001100011 010100001111110 11001011001
> >
> > If I wanted to retrieve the offset where 4 bits are free, the
> > FindFreeBitsInB itmap(4) function should return 18 (the location of 0000)
> >
> > My FindFreeBitsInB itmap(BitCount) function should scan the block of[/color][/color]
memory[color=blue][color=green]
> > until it encounters BitCount of free bits. Then should return the[/color][/color]
offset[color=blue][color=green]
> > into the block where the free bits occur. There's several approaches to
> > this problem, can someone provide me with a very efficient algorithm to
> > locate the starting offset? This function resides in a DBMS and should[/color][/color]
be[color=blue][color=green]
> > very efficient as it's called very frequently. An assembler routine is[/color][/color]
also[color=blue][color=green]
> > an option. All input is greatly appreciated.[/color]
>
> This is off-topic on comp.lang.c++ since there is nothing specific in
> your question about C++ - try comp.programmin g or an algorithms group.[/color]

Idiot, of course it's not C++ exclusive, the algorithm could be of any type,
C++ included. If you have a c/c++ algorithm, then post it. If not, don't
be a stupid ass and keep quiet.

[Jonathan Turkanis]

Re: Bit testing

"David Mott" <dmott@austin.r r.not.home.com> wrote in message
news:Qc2Qb.9481 $RR3.6870@fe1.t exas.rr.com...[color=blue]
>
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
> news:buq7f6$470 @dispatch.conce ntric.net...[color=green]
> > David Mott wrote:
> >
> > This is off-topic on comp.lang.c++ since there is nothing specific[/color][/color]
in[color=blue][color=green]
> > your question about C++ - try comp.programmin g or an algorithms[/color][/color]
group.[color=blue]
>
> Idiot, of course it's not C++ exclusive, the algorithm could be of[/color]
any type,[color=blue]
> C++ included. If you have a c/c++ algorithm, then post it. If not,[/color]
don't[color=blue]
> be a stupid ass and keep quiet.
>[/color]

It may not be off topic, but do you really expect anyone to answer
your question now?

Jonathan

[Gianni Mariani]

Re: Bit testing

David Mott wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
> news:buq7f6$470 @dispatch.conce ntric.net...
>[color=green]
>>David Mott wrote:
>>[color=darkred]
>>>Hi all, hope someone can help me with an algorithm.[/color][/color][/color]
....[color=blue]
> Idiot, of course it's not C++ exclusive, the algorithm could be of any type,
> C++ included. If you have a c/c++ algorithm, then post it. If not, don't
> be a stupid ass and keep quiet.[/color]

Let's see - you ask for help, I offer some help, you start name calling

.... OK let's try again.

It really is off topic in this NG. This NG is about questions on the
standard and yeah, sometimes people are nice and they pitch in for off
topic questions but in your case the question is about performance and
algorithms and nothing specifically to do with C++. You also ask for
assembler options which begs the question - which ISA which you leave
unanswered.

There is no doubt that this is a solved problem, file systems (hint -
linux kernel) use bitmaps as well and there are some really good
resources in filesystems code (like find first set and find last set
assembler code for numerous architectures).

I'm sorry you took the tone of my answer to be other than what it was,
an attempt at being helpful; I truly meant it in the politest way possible.

Chill a little, go write some code, come back with some questions on
your C++ problems and I'm sure you'll find many willing helpers that
will do their best for you.

[David Harmon]

Re: Bit testing

On 23 Jan 2004 02:29:37 EST in comp.lang.c++, Gianni Mariani
<gi2nospam@mari ani.ws> was alleged to have written:[color=blue]
>It really is off topic in this NG. This NG is about questions on the
>standard and yeah, sometimes people are nice and they pitch in for off
>topic questions but in your case the question is about performance and
>algorithms and nothing specifically to do with C++.[/color]

No, it isn't. You totally miss the point. Let us assume that
performance of the algorithm is not actually the issue here. How would
you code the answer in C++? Use the simplest algorithm that comes to
mind, and show the poor fellow some way to approach the problem in C++.
Now that you have made such a big deal over it, that was obviously the
way to interpret the question all along, merely by the fact that it is
posted here.

So now is the time for you to put up some code.

[Gianni Mariani]

Re: Bit testing

David Harmon wrote:[color=blue]
> On 23 Jan 2004 02:29:37 EST in comp.lang.c++, Gianni Mariani
> <gi2nospam@mari ani.ws> was alleged to have written:
>[color=green]
>>It really is off topic in this NG. This NG is about questions on the
>>standard and yeah, sometimes people are nice and they pitch in for off
>>topic questions but in your case the question is about performance and
>>algorithms and nothing specifically to do with C++.[/color]
>
>
> No, it isn't. You totally miss the point. Let us assume that
> performance of the algorithm is not actually the issue here. How would
> you code the answer in C++?[/color]

I think you'll find that is not the case.

Karl writes :"Here we discuss only thing(s) which are defined in
Standard C++ (The language as described by the ISO document)."

Look up the FAQ, it states it more clearly.

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.9

Use the simplest algorithm that comes to[color=blue]
> mind, and show the poor fellow some way to approach the problem in C++.[/color]

I think the OP wanted the highest performance algorithm. (not that that
changes my position, it's still OT even without that requirement.)
[color=blue]
> Now that you have made such a big deal over it, that was obviously the
> way to interpret the question all along, merely by the fact that it is
> posted here.[/color]

I don't think it's a "big deal". All I'm trying to do is give some
helpful suggestions. No skin off my nose if the OP or yourself don't
wish to take it - that's entirely up to you. I think I speak for most
of the people who regularly help on c.l.c++ in saying that this question
is OT.
[color=blue]
>
> So now is the time for you to put up some code.
>[/color]

If I wanted to, I would have done that already. I've already given the
best advice I can with my available time. If you take this question to
comp.programmin g or a better suited NG I honestly think you'll find
better answers.

BTW - I'm probably the worst offender of "answering off-topic questions"
in c.l.c++ (look at the next post -Subj: C vs C++ in pthreads- for
evidence). So when I say it's off topic, I'm usually right by a wide
margin...

Peace ... G

[David Mott]

Re: Bit testing


"Gianni Mariani" <gi2nospam@mari ani.ws> wrote[color=blue]
> David Harmon wrote:[color=green]
> > On 23 Jan 2004 02:29:37 EST in comp.lang.c++, Gianni Mariani
> > <gi2nospam@mari ani.ws> was alleged to have written:
> >[color=darkred]
> >>It really is off topic in this NG. This NG is about questions on the
> >>standard and yeah, sometimes people are nice and they pitch in for off
> >>topic questions but in your case the question is about performance and
> >>algorithms and nothing specifically to do with C++.[/color]
> >
> >
> > No, it isn't. You totally miss the point. Let us assume that
> > performance of the algorithm is not actually the issue here. How would
> > you code the answer in C++?[/color]
>
> I think you'll find that is not the case.
>
> Karl writes :"Here we discuss only thing(s) which are defined in
> Standard C++ (The language as described by the ISO document)."
>
> Look up the FAQ, it states it more clearly.
>
> http://www.parashift.com/c++-faq-lit...t.html#faq-5.9[/color]

Who is Karl? I don't care about Karl, nor take direction from him. He
hasnt helped me with an implementation. If Karl is the moderator of this
group, he should be moderating and remove the message before its posted to
the group.
[color=blue]
>
> Use the simplest algorithm that comes to[color=green]
> > mind, and show the poor fellow some way to approach the problem in C++.[/color]
>
> I think the OP wanted the highest performance algorithm. (not that that
> changes my position, it's still OT even without that requirement.)[/color]

High performance is good, however, anything is better than nothing. If you
wanted to help, why not forward the post to the other group yourself? It
certainly would have saved your limited time.
[color=blue][color=green]
> > Now that you have made such a big deal over it, that was obviously the
> > way to interpret the question all along, merely by the fact that it is
> > posted here.[/color]
>
> I don't think it's a "big deal". All I'm trying to do is give some
> helpful suggestions. No skin off my nose if the OP or yourself don't
> wish to take it - that's entirely up to you. I think I speak for most
> of the people who regularly help on c.l.c++ in saying that this question
> is OT.[/color]

Yes, its no big deal, sence its no big deal, why defend your post twice? No
big deal, but your suggestion was not helpful. If the goal was to give a
helpful suggestion, you failed. I'm not seeking direction on where to post
my question. I'm sure members of this group are qualified to answer it.
Dont take the responsibility for speaking for anyone but yourself. To
defend your post, you reference Karl and "most of the people" in this NG.
Is this the case? Have you been authorized to speak in their behalf?
[color=blue][color=green]
> >
> > So now is the time for you to put up some code.
> >[/color]
>
> If I wanted to, I would have done that already. I've already given the
> best advice I can with my available time. If you take this question to
> comp.programmin g or a better suited NG I honestly think you'll find
> better answers.[/color]

You seem to have enough time to complain, why not use your time more
constructively?
[color=blue]
> BTW - I'm probably the worst offender of "answering off-topic questions"
> in c.l.c++ (look at the next post -Subj: C vs C++ in pthreads- for
> evidence). So when I say it's off topic, I'm usually right by a wide
> margin...[/color]

If you are the worst offender, why was my post such an offense? What's the
point? I've heard people complain about posting to threads off topic, not
to groups. On rare occasion someone will complain about spam porn hitting
the NG. It's a matter of opinion as to whether the question was off topic
or not. The NG is as much my resource as anyone else's. If you are
bothered by off topic posts, then simply ignore them, your help wasn't help
at all, it was an insult. My post could be very much on-topic depending on
how you approach it.

I have several solutions to this problem, I'm looking for suggestions and/or
implementation details, not schooling on how or where to post my question.
If you cant answer it, simply ignore it.

[Jeff Flinn]

Re: Bit testing


"David Mott" <dmott@austin.r r.not.home.com> wrote in message
news:JygQb.1081 8$7D.9327@fe2.t exas.rr.com...[color=blue]
>
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote[color=green]
> > David Harmon wrote:[/color][/color]
....[color=blue]
>
> I have several solutions to this problem, I'm looking for suggestions[/color]
and/or[color=blue]
> implementation details, not schooling on how or where to post my question.
> If you cant answer it, simply ignore it.[/color]

Then post them and ask specific C++ questions about them. Perhaps some will
overlook your unprovoked rudeness and help you.

Jeff F

[Gianni Mariani]

Re: Bit testing

David Mott wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote[/color]
....[color=blue]
>
> Who is Karl? I don't care about Karl, nor take direction from him. He
> hasnt helped me with an implementation. If Karl is the moderator of this
> group, he should be moderating and remove the message before its posted to
> the group.[/color]

Who cares - do some research if you care so much... Google it and
you'll find it. You seem to have a phobia of researching things for
yourself.
[color=blue]
>
>[color=green]
>> Use the simplest algorithm that comes to
>>[color=darkred]
>>>mind, and show the poor fellow some way to approach the problem in C++.[/color]
>>
>>I think the OP wanted the highest performance algorithm. (not that that
>>changes my position, it's still OT even without that requirement.)[/color]
>
>
> High performance is good, however, anything is better than nothing. If you
> wanted to help, why not forward the post to the other group yourself? It
> certainly would have saved your limited time.[/color]

Because it's not my problem - I have plenty of my own. Take the time to
do some more research work - or pay someone to do it.

....
[color=blue][color=green]
>>I don't think it's a "big deal". All I'm trying to do is give some
>>helpful suggestions. No skin off my nose if the OP or yourself don't
>>wish to take it - that's entirely up to you. I think I speak for most
>>of the people who regularly help on c.l.c++ in saying that this question
>>is OT.[/color]
>
>
> Yes, its no big deal, sence its no big deal, why defend your post twice?[/color]

Because I'm still trying to help you - this time with the best way to
use this resource. Admitedly, I'm starting to think it's a lost cause.

No[color=blue]
> big deal, but your suggestion was not helpful.[/color]

Oh well, hopefully someone else might get the benefit.

If the goal was to give a[color=blue]
> helpful suggestion, you failed.[/color]

Some people are incapable of being helped by me. Nothing I can do about
that.

I'm not seeking direction on where to post[color=blue]
> my question. I'm sure members of this group are qualified to answer it.[/color]

I don't think so. Yes, any programmer with enough experience could
probably come up with an algorithm, but not one which is going to be as
good as someone who implemented it before. As I suggested before,
kernels (mostly implemented in C) are places where these kinds of
algorithms are found. Many new file systems don't use bitmaps at all -
for performance reasons.
[color=blue]
> Dont take the responsibility for speaking for anyone but yourself.[/color]

I believe my statement was asserted as an opinion, not as fact, so I
completly own that opinion. Telling me I should not have such an
opinion without supporting argument is not going to change my position.


To[color=blue]
> defend your post, you reference Karl and "most of the people" in this NG.
> Is this the case? Have you been authorized to speak in their behalf?[/color]

It does not work like this. In a sense, this NG is a "comminity" of
people who choose to work by the rules. I don't like some of the rules
myself but my dislike of them is inconsequential so I (for the most
part) play by the rules. If you want to participate (i.e. get help or
give help), you'll get much better success if you play by the rules.
The rules are clearly stated in the FAQ (which I posted earlier) and so
far I believe that's where you need to go an seek your "authorization" .
[color=blue]
>
>[color=green][color=darkred]
>>>So now is the time for you to put up some code.
>>>[/color]
>>
>>If I wanted to, I would have done that already. I've already given the
>>best advice I can with my available time. If you take this question to
>>comp.programm ing or a better suited NG I honestly think you'll find
>>better answers.[/color]
>
>
> You seem to have enough time to complain, why not use your time more
> constructively?[/color]

I don't believe I have made any complaint whatsoever. If you interpret
anything I said as a complaint you are mistaken. Absolutely everything
I have attempted to say to you have been with good intentions.

This medium (the written word) is a poor conveyor of intent and emotion,
hence I am very careful about jumping to conclusions. It's almost
impossible to write anything that can't be misinterpreted.

[color=blue]
>
>[color=green]
>>BTW - I'm probably the worst offender of "answering off-topic questions"
>>in c.l.c++ (look at the next post -Subj: C vs C++ in pthreads- for
>>evidence). So when I say it's off topic, I'm usually right by a wide
>>margin...[/color]
>
>
> If you are the worst offender, why was my post such an offense?[/color]

I NEVER intended to offend you. I'll apologise right now - no offence
was intended - even after you called *me* an idiot - I really have no
wish to offend you whatsoever.


What's the[color=blue]
> point?[/color]

To attempt to help you or others wishing to read this.

I've heard people complain about posting to threads off topic, not[color=blue]
> to groups.[/color]

This NG has a very long history of OT fights - some people have become
all bend out of shape because of it. c.l.c++ is unfortunately named in
that some people think that anything that could be remotely related to
C++ get's sent to c.l.c++. If you don't believe this, look at some of
the other posts.

On rare occasion someone will complain about spam porn hitting[color=blue]
> the NG. It's a matter of opinion as to whether the question was off topic
> or not.[/color]

In some cases, I agree - in fact, see my response to the thread "C vs.
C++ in pthreads..." which was started just after this one. But this
thread has no hope of being on topic because there is nothing specific
to C++ as written in the standard. Your question has alot more to it
than I think you understand there is. There is a significant investment
in effort to get to a good answer I don't think you'll get the best
answer here.


The NG is as much my resource as anyone else's. If you are[color=blue]
> bothered by off topic posts, then simply ignore them, your help wasn't help
> at all, it was an insult.[/color]

The "insult" is all in your mind. Nobody wanted to insult you. I don't
believe anyone else but you would see it that way.

My post could be very much on-topic depending on[color=blue]
> how you approach it.[/color]

Nice try - no cigar :-)
[color=blue]
>
> I have several solutions to this problem, I'm looking for suggestions and/or
> implementation details, not schooling on how or where to post my question.
> If you cant answer it, simply ignore it.
>[/color]

This applies to you too. If you can't stand the advice, ignore it.

[David Harmon]

Re: Bit testing

On 23 Jan 2004 12:34:18 EST in comp.lang.c++, Gianni Mariani
<gi2nospam@mari ani.ws> was alleged to have written:[color=blue]
>Look up the FAQ, it states it more clearly.
>http://www.parashift.com/c++-faq-lit...t.html#faq-5.9[/color]

I know what the FAQ says, having quoted and cited it many times.
Some might say too many times.

"Only post to comp.lang.c++ if your question is about the C++
language itself. For example, C++ code design, syntax, style,
rules, bugs, etc."

The question was about C++ code design, the first of those categories
that Cline mentions.

The question was never off topic. The problem is in your imagination.
You forgot to imagine that the poster had included the magic words "How
should I do this in standard C++?". But those words ought to be assumed
wherever they fit in questions in comp.lang.c++.
[color=blue][color=green]
>> So now is the time for you to put up some code.[/color]
>
>If I wanted to, I would have done that already. I've already given the
>best advice I can with my available time. If you take this question to
>comp.programmi ng or a better suited NG I honestly think you'll find
>better answers.[/color]

You flamed a questioner, and you were wrong, and you were adamantly and
bizarrely wrong. So now you owe it to him to give him some help, by way
of apology. If you do not have time to help, then you do not have time
to post here. It is a bad thing for comp.lang.c++ to have the
reputation as a place to go to get flamed and not get help. If a
question can plausibly be interpreted as on topic, then interpret it
that way. If part of the question is on topic, then answer that part.

You will find that the C++ code to do this is not so easy, probably why
he came here with his question anyway. Maybe you are incapable of
writing it.
[color=blue]
>BTW - I'm probably the worst offender of "answering off-topic questions"[/color]

So, don't do that, it's also part of the problem. "How should I do this
in standard C++" is not off-topic - it IS the topic.

[Gianni Mariani]

Re: Bit testing

David Harmon wrote:[color=blue]
> On 23 Jan 2004 12:34:18 EST in comp.lang.c++, Gianni Mariani
> <gi2nospam@mari ani.ws> was alleged to have written:
>[color=green]
>>Look up the FAQ, it states it more clearly.
>>http://www.parashift.com/c++-faq-lit...t.html#faq-5.9[/color]
>
>
> I know what the FAQ says, having quoted and cited it many times.
> Some might say too many times.
>
> "Only post to comp.lang.c++ if your question is about the C++
> language itself. For example, C++ code design, syntax, style,
> rules, bugs, etc."
>
> The question was about C++ code design, the first of those categories
> that Cline mentions.
>
> The question was never off topic. The problem is in your imagination.
> You forgot to imagine that the poster had included the magic words "How
> should I do this in standard C++?". But those words ought to be assumed
> wherever they fit in questions in comp.lang.c++.[/color]

I think you're wrong.

Take this question : "I'd like to design a program in C++ that solves
world hunger - can someone help me write such a program please ?"

Such a question is "off topic" - replace the "world hunger" the bit run
requirement and it's still off topic.
[color=blue]
>
>[color=green][color=darkred]
>>>So now is the time for you to put up some code.[/color]
>>
>>If I wanted to, I would have done that already. I've already given the
>>best advice I can with my available time. If you take this question to
>>comp.programm ing or a better suited NG I honestly think you'll find
>>better answers.[/color]
>
>
> You flamed a questioner, and you were wrong, and you were adamantly and
> bizarrely wrong. So now you owe it to him to give him some help, by way
> of apology.[/color]

Please cite the words you believe "flamed a questioner". Once you have
found such words, try to say them exactly without any thoughts of
flaming in your head and you'll find that you mis-interpretted them.

As I have already written, I take caution in interpretting emotional
responses becuase it's too easy make errors. Writing responses that
can't be interpreted emotionally is night impossible to do. Hence the
flame is usually in the eye of the beholder.


If you do not have time to help, then you do not have time[color=blue]
> to post here.[/color]

(Arrogance alert.) I'd like to see you justify this comment.

It is a bad thing for comp.lang.c++ to have the[color=blue]
> reputation as a place to go to get flamed and not get help.[/color]

Not everyone can be helped. If someone is too arrogant to see the help
when they get it, that's not my problem. One day they may grow out of
it, some never do. I'll not loose any sleep over that.

If a[color=blue]
> question can plausibly be interpreted as on topic, then interpret it
> that way. If part of the question is on topic, then answer that part.[/color]

Go ahead - nobody is stopping you.
[color=blue]
>
> You will find that the C++ code to do this is not so easy, probably why
> he came here with his question anyway. Maybe you are incapable of
> writing it.[/color]

Well, there is nothing C++ about it then is there ? It's simply a hard
problem regarless of language. Actually, it's probably harder that the
OP thought it was because if performance is an issue, you may want to
cache a free list/tree.

[color=blue]
>[color=green]
>>BTW - I'm probably the worst offender of "answering off-topic questions"[/color]
>
>
> So, don't do that, it's also part of the problem. "How should I do this
> in standard C++" is not off-topic - it IS the topic.[/color]

Great, I have a question for you "Can you please show me a program that
that computes free body trajectories at the quantum level using standard
C++ ?"

[David Harmon]

Re: Bit testing

On 23 Jan 2004 21:10:25 EST in comp.lang.c++, Gianni Mariani
<gi2nospam@mari ani.ws> was alleged to have written:[color=blue]
>Please cite the words you believe "flamed a questioner".[/color]

You are right. I was wrong. I apologize for the accusation.
I seem to have conflated David Mott's response to you with what you
actually wrote. Which does pretty well wipe out most of what I said,
except that I still think the original question should be interpreted
as being about C++ programming, and thereby on topic.
Sorry.