Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Alternative approach to bitfields
68 views
Skip to first unread message
W Karas
Jul 22, 2012, 10:21:44 PM7/22/12
to
The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to a bit in an unsigned integer. Here is some example code:
/* Notes
** 1. parameters to these macros may appear multiple times in the
** macro definition, so do not use expresions with side-effects as
** actual parameters.
** 2. If parameters to these macros are not in the correct range,
** results are undetermined.
*/
/* Get the value of the bitfield with the given WIDTH at the offset OFS in
** the rvalue RV of unsigned integer type UT.
*/
#define BF_GET_N(UT, RV, WIDTH, OFS) \
(((RV) >> (OFS)) & BF_H_MW(UT, WIDTH))
/* Logically OR the value VAL into lvalue LV after left-bit-shifting it
** by OFS bits.
*/
#define BF_OR_N(LV, OFS, VAL) \
{ BF_H_OR_N_EXPR(LV, OFS, VAL); }
/* Set the value VAL in the bitfield with the given WIDTH at the offset OFS
** in the lvalue LV of unsigned integer type UT.
*/
#define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
{ ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(*&(LV) = (VAL)) : \
(*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
BF_H_OR_N_EXPR(LV, OFS, VAL)); }
/* A "bitfield map structure" is recursively defined as a C/POD struct or
** union where each member is an array of char or a bitfield map structure.
** Each array of char represents a bitfield. The sizeof the array gives
** the width of the bitfield. The byte offset of the array from the
** start of the top-level structure gives the offset of the bitfield.
*/
/* Get the value of the bitfield in the rvalue RV of unsigned integer type
** UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_GET(UT, RV, MSTRU, FLD) \
BF_GET_N(UT, RV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD))
/* Logically OR the value VAL into value of the bitfield in the rvalue RV of
** unsigned integer type ** UT corresponding to the field FLD in bitfield map
** structure MSTRU.
*/
#define BF_OR(LV, MSTRU, FLD, VAL) \
BF_OR_N(LV, BF_H_OFS(MSTRU, FLD), VAL)
/* Set the value VAL in the bitfield in the rvalue RV of unsigned integer
** type UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_SET(UT, LV, MSTRU, FLD, VAL) \
BF_SET_N(UT, LV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD), VAL)
/* --------------------------------------------------------------------- */
/* "Private" macros, not meant for direct use. */
#include <limits.h>
/* Mask of WIDTH and type UT.
*/
#define BF_H_MW(UT, WIDTH) \
((UT) (((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(~ (UT) 0) : ((((UT) 1) << (WIDTH)) - 1)))
/* BF_OR_N as expression not statement.
*/
#define BF_H_OR_N_EXPR(LV, OFS, VAL) \
(*&(LV) |= ((VAL) << (OFS)))
/* Returns offset of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_WIDTH(MSTRU, FLD) \
(sizeof(((MSTRU *) 0x100)->FLD))
/* Returns width of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_OFS(MSTRU, FLD) \
((((MSTRU *) 0x100)->FLD) - ((char *) 0x100))
/* These macros lay out the bit fields with higher offsets at higher
** significance, but the reverse is also possible.
*/
/* --------------------------------------------------------------------- */
/* Test code */
typedef struct
{
union
{
/* Array of 4 5-bit-wide bitfields (cool eh?). */
char fa[4][5];
struct
{
char f1[6], f2[14];
}
sm;
}
u;
char f3[12];
}
Map_bf;
#include <stdio.h>
#include <stdlib.h>
void bail(void)
{
printf("FAIL\n");
exit(1);
}
int main(void)
{
unsigned va[4], v1, v2, v3, i, v;
v = 0xabcd1234;
for (i = 0; i < 4; ++i)
va[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]);
v3 = BF_GET(unsigned, v, Map_bf, f3);
if (v != 0xabcd1234)
bail();
v = 0x1234abcd;
for (i = 0; i < 4; ++i)
BF_SET(unsigned, v, Map_bf, u.fa[i], va[i])
BF_SET(unsigned, v, Map_bf, f3, v3);
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);
if (v != 0xabcd1234)
bail();
v = 0x1234abcd;
BF_SET(unsigned, v, Map_bf, u.sm.f1, v1)
BF_SET(unsigned, v, Map_bf, u.sm.f2, v2)
BF_SET(unsigned, v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
for (i = 0; i < 4; ++i)
va[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]);
v3 = BF_GET(unsigned, v, Map_bf, f3);
v = 0;
for (i = 0; i < 4; ++i)
BF_OR(v, Map_bf, u.fa[i], va[i])
BF_OR(v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);
v = 0;
BF_OR(v, Map_bf, u.sm.f1, v1)
BF_OR(v, Map_bf, u.sm.f2, v2)
BF_OR(v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
printf("SUCCESS\n");
return(0);
}
/* Notes
** 1. parameters to these macros may appear multiple times in the
** macro definition, so do not use expresions with side-effects as
** actual parameters.
** 2. If parameters to these macros are not in the correct range,
** results are undetermined.
*/
/* Get the value of the bitfield with the given WIDTH at the offset OFS in
** the rvalue RV of unsigned integer type UT.
*/
#define BF_GET_N(UT, RV, WIDTH, OFS) \
(((RV) >> (OFS)) & BF_H_MW(UT, WIDTH))
/* Logically OR the value VAL into lvalue LV after left-bit-shifting it
** by OFS bits.
*/
#define BF_OR_N(LV, OFS, VAL) \
{ BF_H_OR_N_EXPR(LV, OFS, VAL); }
/* Set the value VAL in the bitfield with the given WIDTH at the offset OFS
** in the lvalue LV of unsigned integer type UT.
*/
#define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
{ ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(*&(LV) = (VAL)) : \
(*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
BF_H_OR_N_EXPR(LV, OFS, VAL)); }
/* A "bitfield map structure" is recursively defined as a C/POD struct or
** union where each member is an array of char or a bitfield map structure.
** Each array of char represents a bitfield. The sizeof the array gives
** the width of the bitfield. The byte offset of the array from the
** start of the top-level structure gives the offset of the bitfield.
*/
/* Get the value of the bitfield in the rvalue RV of unsigned integer type
** UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_GET(UT, RV, MSTRU, FLD) \
BF_GET_N(UT, RV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD))
/* Logically OR the value VAL into value of the bitfield in the rvalue RV of
** unsigned integer type ** UT corresponding to the field FLD in bitfield map
** structure MSTRU.
*/
#define BF_OR(LV, MSTRU, FLD, VAL) \
BF_OR_N(LV, BF_H_OFS(MSTRU, FLD), VAL)
/* Set the value VAL in the bitfield in the rvalue RV of unsigned integer
** type UT corresponding to the field FLD in bitfield map structure MSTRU.
*/
#define BF_SET(UT, LV, MSTRU, FLD, VAL) \
BF_SET_N(UT, LV, BF_H_WIDTH(MSTRU, FLD), BF_H_OFS(MSTRU, FLD), VAL)
/* --------------------------------------------------------------------- */
/* "Private" macros, not meant for direct use. */
#include <limits.h>
/* Mask of WIDTH and type UT.
*/
#define BF_H_MW(UT, WIDTH) \
((UT) (((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
(~ (UT) 0) : ((((UT) 1) << (WIDTH)) - 1)))
/* BF_OR_N as expression not statement.
*/
#define BF_H_OR_N_EXPR(LV, OFS, VAL) \
(*&(LV) |= ((VAL) << (OFS)))
/* Returns offset of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_WIDTH(MSTRU, FLD) \
(sizeof(((MSTRU *) 0x100)->FLD))
/* Returns width of bitfield corresponding to char array FLD in bitfield
** map structure MSTRU.
*/
#define BF_H_OFS(MSTRU, FLD) \
((((MSTRU *) 0x100)->FLD) - ((char *) 0x100))
/* These macros lay out the bit fields with higher offsets at higher
** significance, but the reverse is also possible.
*/
/* --------------------------------------------------------------------- */
/* Test code */
typedef struct
{
union
{
/* Array of 4 5-bit-wide bitfields (cool eh?). */
char fa[4][5];
struct
{
char f1[6], f2[14];
}
sm;
}
u;
char f3[12];
}
Map_bf;
#include <stdio.h>
#include <stdlib.h>
void bail(void)
{
printf("FAIL\n");
exit(1);
}
int main(void)
{
unsigned va[4], v1, v2, v3, i, v;
v = 0xabcd1234;
for (i = 0; i < 4; ++i)
va[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]);
v3 = BF_GET(unsigned, v, Map_bf, f3);
if (v != 0xabcd1234)
bail();
v = 0x1234abcd;
for (i = 0; i < 4; ++i)
BF_SET(unsigned, v, Map_bf, u.fa[i], va[i])
BF_SET(unsigned, v, Map_bf, f3, v3);
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);
if (v != 0xabcd1234)
bail();
v = 0x1234abcd;
BF_SET(unsigned, v, Map_bf, u.sm.f1, v1)
BF_SET(unsigned, v, Map_bf, u.sm.f2, v2)
BF_SET(unsigned, v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
for (i = 0; i < 4; ++i)
va[i] = BF_GET(unsigned, v, Map_bf, u.fa[i]);
v3 = BF_GET(unsigned, v, Map_bf, f3);
v = 0;
for (i = 0; i < 4; ++i)
BF_OR(v, Map_bf, u.fa[i], va[i])
BF_OR(v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
v = 0xabcd1234;
v1 = BF_GET(unsigned, v, Map_bf, u.sm.f1);
v2 = BF_GET(unsigned, v, Map_bf, u.sm.f2);
v3 = BF_GET(unsigned, v, Map_bf, f3);
v = 0;
BF_OR(v, Map_bf, u.sm.f1, v1)
BF_OR(v, Map_bf, u.sm.f2, v2)
BF_OR(v, Map_bf, f3, v3)
if (v != 0xabcd1234)
bail();
printf("SUCCESS\n");
return(0);
}
Jorgen Grahn
Jul 23, 2012, 3:52:37 AM7/23/12
to
On Mon, 2012-07-23, W Karas wrote:
> The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to
> a bit in an unsigned integer.
Why do we need an alternative? I didn't read the code carefully, but
> The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to
> a bit in an unsigned integer.
I don't see what problem you're trying to solve.
...
> #define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
> { ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
> (*&(LV) = (VAL)) : \
> (*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
> BF_H_OR_N_EXPR(LV, OFS, VAL)); }
...
> { ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
> (*&(LV) = (VAL)) : \
> (*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
> BF_H_OR_N_EXPR(LV, OFS, VAL)); }
/Jorgen
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
W Karas
Jul 23, 2012, 10:10:02 AM7/23/12
to
On Monday, July 23, 2012 3:52:37 AM UTC-4, Jorgen Grahn wrote:
> On Mon, 2012-07-23, W Karas wrote:
> > The idea is to define the bitfields using a "map" structure of arrays of char, with each char corresponding to
> On Mon, 2012-07-23, W Karas wrote:
> > a bit in an unsigned integer.
>
> Why do we need an alternative? I didn't read the code carefully, but
> I don't see what problem you're trying to solve.
>
> ...
> > #define BF_SET_N(UT, LV, WIDTH, OFS, VAL) \
> > { ((WIDTH) >= (sizeof(UT) * CHAR_BIT)) ? \
> > (*&(LV) = (VAL)) : \
> > (*&(LV) &= ~(BF_H_MW(UT, WIDTH) << (OFS)), \
> > BF_H_OR_N_EXPR(LV, OFS, VAL)); }
> ...
>
> /Jorgen
>
> --
> // Jorgen Grahn <grahn@ Oo o. . .
> \X/ snipabacken.se> O o .
Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
Victor Bazarov
Jul 23, 2012, 10:48:27 AM7/23/12
to
On 7/23/2012 10:10 AM, W Karas wrote:
> [..] Like bitfields cannot be used when optimization is enabled, as
V
--
I do not respond to top-posted replies, please don't ask
> [..] Like bitfields cannot be used when optimization is enabled, as
> was (is?) true for many years with MS-C/C++ .
What?? Where did you get that information?
V
--
I do not respond to top-posted replies, please don't ask
W Karas
Jul 23, 2012, 3:23:48 PM7/23/12
to
On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> On 7/23/2012 10:10 AM, W Karas wrote:
> > [..] Like bitfields cannot be used when optimization is enabled, as
> On 7/23/2012 10:10 AM, W Karas wrote:
> > was (is?) true for many years with MS-C/C++ .
>
> What?? Where did you get that information?
From personal experience back in the mid 1990s. I assume it's fixed now, but MS did not seem to see it as a priority at the time so...
> What?? Where did you get that information?
>
> V
> --
> I do not respond to top-posted replies, please don't ask
Geoff
Jul 23, 2012, 4:52:07 PM7/23/12
to
On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas <wka...@yahoo.com>
wrote:
>Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
What optimization modes affect bitfields? I've never heard of any
problems with bitfields on any version of Microsoft's compilers.
wrote:
>Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
problems with bitfields on any version of Microsoft's compilers.
Victor Bazarov
Jul 23, 2012, 4:55:19 PM7/23/12
to
On 7/23/2012 3:23 PM, W Karas wrote:
> On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
>> On 7/23/2012 10:10 AM, W Karas wrote:
>> > [..] Like bitfields cannot be used when optimization is enabled, as
>> > was (is?) true for many years with MS-C/C++ .
>>
>> What?? Where did you get that information?
>
> From personal experience back in the mid 1990s. I assume it's fixed
> now, but MS did not seem to see it as a priority at the time so...
If you assume it's fixed now, what is your motivation for inventing such
> On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
>> On 7/23/2012 10:10 AM, W Karas wrote:
>> > [..] Like bitfields cannot be used when optimization is enabled, as
>> > was (is?) true for many years with MS-C/C++ .
>>
>> What?? Where did you get that information?
>
> From personal experience back in the mid 1990s. I assume it's fixed
> now, but MS did not seem to see it as a priority at the time so...
an "alternative" as Jorgen put it? Is it just for exercise? Seems to
me something akin to implementing "a better quicksort" or "a more
reliable Bresenham's line drawing"...
V
--
I do not respond to top-posted replies, please don't ask
W Karas
Jul 23, 2012, 6:31:34 PM7/23/12
to
On Monday, July 23, 2012 4:52:07 PM UTC-4, Geoff wrote:
> On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas ;
> wrote:
>
> >Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
>
> What optimization modes affect bitfields? I've never heard of any
> problems with bitfields on any version of Microsoft's compilers.
As best as I can recall now, any optimization for speed could cause code containing bitfields to result in incorrect object code.
> On Mon, 23 Jul 2012 07:10:02 -0700 (PDT), W Karas ;
> wrote:
>
> >Only in unusual circumstances. Like bitfields cannot be used when optimization is enabled, as was (is?) true for many years with MS-C/C++ .
>
> What optimization modes affect bitfields? I've never heard of any
> problems with bitfields on any version of Microsoft's compilers.
As best as I can recall now, any optimization for speed could cause code containing bitfields to result in incorrect object code.
W Karas
Jul 23, 2012, 7:03:53 PM7/23/12
to
On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote:
> On 7/23/2012 3:23 PM, W Karas wrote:
> > On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> On 7/23/2012 3:23 PM, W Karas wrote:
> >> On 7/23/2012 10:10 AM, W Karas wrote:
> >> &gt; [..] Like bitfields cannot be used when optimization is enabled, as
> >> &gt; was (is?) true for many years with MS-C/C++ .
> >>
> >> What?? Where did you get that information?
> >
> > From personal experience back in the mid 1990s. I assume it's fixed
> > now, but MS did not seem to see it as a priority at the time so...
>
> If you assume it's fixed now, what is your motivation for inventing such
> an "alternative" as Jorgen put it? Is it just for exercise? Seems to
> me something akin to implementing "a better quicksort" or "a more
> reliable Bresenham's line drawing"...
>
> V
> --
> I do not respond to top-posted replies, please don't ask
The code is meant to demonstrate (in a fairly short and simple way) an approach, more so than to be a substitute for language-provided bitfields. I used this approach for structures (of bitfields) that were multiples of 10 bytes long. The bitfields could be up to 32 bits wide, and could straddle 32-bit boundaries. The ability to have arrays and unions was useful in these structures. I used templates rather than macros (much cleaner), but was disappointed at how easily both the compilers we use would "give up" (not fully inline) in the face of several nested levels of inline function calls.
BTW I have implemented a "better" QuickSort. Instead of recursion, it uses an explicit, resizeable stack in dynamic storage. It's useful for environments without VM-base resizing process call stacks.
Robert Wessel
Jul 23, 2012, 11:54:17 PM7/23/12
to
On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas <wka...@yahoo.com>
wrote:
Why? Properly implemented Quicksort (semi-recursive, recurse on the
smaller partition only), does not usually have a big stack frame, and
a quite limited recursion depth ( lg(n) - so even a billion items will
result in no more than 30 levels).
wrote:
smaller partition only), does not usually have a big stack frame, and
a quite limited recursion depth ( lg(n) - so even a billion items will
result in no more than 30 levels).
W Karas
Jul 24, 2012, 2:19:32 PM7/24/12
to
On Monday, July 23, 2012 11:54:17 PM UTC-4, robert...@yahoo.com wrote:
> On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas
> wrote:
> On Mon, 23 Jul 2012 16:03:53 -0700 (PDT), W Karas
>
> >On Monday, July 23, 2012 4:55:19 PM UTC-4, Victor Bazarov wrote:
> >> On 7/23/2012 3:23 PM, W Karas wrote:
> >> &gt; On Monday, July 23, 2012 10:48:27 AM UTC-4, Victor Bazarov wrote:
> >> &gt;&gt; On 7/23/2012 10:10 AM, W Karas wrote:
> >> &gt;&gt; &amp;gt; [..] Like bitfields cannot be used when optimization is enabled, as
> >> &gt;&gt; &amp;gt; was (is?) true for many years with MS-C/C++ .
> >> &gt;&gt;
> >> &gt;&gt; What?? Where did you get that information?
> >> &gt;
> >> &gt; From personal experience back in the mid 1990s. I assume it&#39;s fixed
> >> &gt; now, but MS did not seem to see it as a priority at the time so...
> >>
> >> If you assume it&#39;s fixed now, what is your motivation for inventing such
> >> an &quot;alternative&quot; as Jorgen put it? Is it just for exercise? Seems to
> >> me something akin to implementing &quot;a better quicksort&quot; or &quot;a more
> >> reliable Bresenham&#39;s line drawing&quot;...
> >>
> >> V
> >> --
> >> I do not respond to top-posted replies, please don&#39;t ask
> >
> >The code is meant to demonstrate (in a fairly short and simple way) an approach, more so than to be a substitute for language-provided bitfields. I used this approach for structures (of bitfields) that were multiples of 10 bytes long. The bitfields could be up to 32 bits wide, and could straddle 32-bit boundaries. The ability to have arrays and unions was useful in these structures. I used templates rather than macros (much cleaner), but was disappointed at how easily both the compilers we use would "give up" (not fully inline) in the face of several nested levels of inline function calls.
> >
> >BTW I have implemented a "better" QuickSort. Instead of recursion, it uses an explicit, resizeable stack in dynamic storage. It's useful for environments without VM-base resizing process call stacks.
>
>
> Why? Properly implemented Quicksort (semi-recursive, recurse on the
> smaller partition only), does not usually have a big stack frame, and
> a quite limited recursion depth ( lg(n) - so even a billion items will
> result in no more than 30 levels).
Cool, thanks, that handn't occurred to me, I assume you mean like:
>
> Why? Properly implemented Quicksort (semi-recursive, recurse on the
> smaller partition only), does not usually have a big stack frame, and
> a quite limited recursion depth ( lg(n) - so even a billion items will
> result in no more than 30 levels).
quicksort(partition p)
{
loop while ((size of p) > 1)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
p=largepart
}
}
( from http://coding.derkeiler.com/Archive/General/comp.programming/2008-01/msg00337.html )
Robert Wessel
Jul 24, 2012, 3:07:30 PM7/24/12
to
On Tue, 24 Jul 2012 11:19:32 -0700 (PDT), W Karas <wka...@yahoo.com>
wrote:
That's correct.
As usual for Quicksort you should also avoid Quicksorting small
partitions (often n<5), and clean those up en-mass with a final
insertion sort pass over the dataset.
Wait a minute - I *thought* that bit of pseudo-code looked familiar...
;-)
wrote:
As usual for Quicksort you should also avoid Quicksorting small
partitions (often n<5), and clean those up en-mass with a final
insertion sort pass over the dataset.
Wait a minute - I *thought* that bit of pseudo-code looked familiar...
;-)
0 new messages