Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #14808 > unrolled thread
| Started by | pozz <pozzugno@gmail.com> |
|---|---|
| First post | 2011-12-21 00:13 +0100 |
| Last post | 2012-01-25 16:44 -0800 |
| Articles | 4 on this page of 64 — 18 participants |
Back to article view | Back to comp.lang.c
A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 00:13 +0100
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 00:14 +0000
Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 06:26 -0800
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 21:04 +0000
Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-21 23:59 -0800
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-22 12:02 +0000
Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 05:48 -0800
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-22 19:24 +0000
Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 00:08 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-22 08:49 +0000
Re: A binary search algorithm that searches for an element similar to the key Barry Schwarz <schwarzb@dqel.com> - 2011-12-20 21:27 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 01:01 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 04:36 -0800
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-21 12:49 +0000
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-21 19:12 +0000
Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-21 13:37 -0800
Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-21 23:37 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 11:25 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 20:13 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 13:25 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 22:14 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 15:12 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 00:09 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 16:22 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 03:03 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-27 13:51 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-27 22:14 +0000
Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-27 14:53 -0800
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-23 19:45 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 06:45 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 09:52 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-24 16:37 +0100
Re: A binary search algorithm that searches for an element similar to the key hopcode <hopcode@nulnulul.de> - 2011-12-24 19:11 +0100
Re: A binary search algorithm that searches for an element similar to the key Nathan <nathancbaker@gmail.com> - 2011-12-24 12:20 -0800
Re: A binary search algorithm that searches for an element similar to the key Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-28 03:21 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 04:01 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-28 18:17 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 16:58 -0800
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-29 00:43 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:16 -0800
Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-28 18:28 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:39 -0800
Re: A binary search algorithm that searches for an element similar to the key Keith Thompson <kst-u@mib.org> - 2011-12-28 19:00 -0800
Re: A binary search algorithm that searches for an element similar to the key Geoff <geoff@invalid.invalid> - 2011-12-28 22:04 -0800
Re: A binary search algorithm that searches for an element similar to the key pacman@kosh.dhis.org (Alan Curry) - 2011-12-29 07:50 +0000
Re: A binary search algorithm that searches for an element similar to the key Seebs <usenet-nospam@seebs.net> - 2011-12-29 18:50 +0000
Re: A binary search algorithm that searches for an element similar to the key Patrick Scheible <kkt@zipcon.net> - 2011-12-29 12:52 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 02:45 -0800
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-03 16:30 -0800
Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-29 10:00 +0000
Re: A binary search algorithm that searches for an element similar to the key gazelle@shell.xmission.com (Kenny McCormack) - 2011-12-29 09:58 +0000
Re: A binary search algorithm that searches for an element similar to the key 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-21 06:44 -0800
Re: A binary search algorithm that searches for an element similar to the key John Tsiombikas <nuclear@member.fsf.org> - 2011-12-21 17:27 +0000
Re: A binary search algorithm that searches for an element similar to the key pete <pfiland@mindspring.com> - 2011-12-21 17:54 -0500
Re: A binary search algorithm that searches for an element similar to the key Peter Nilsson <airia@acay.com.au> - 2011-12-21 23:09 -0800
Re: A binary search algorithm that searches for an element similar to the key pozz <pozzugno@gmail.com> - 2011-12-22 00:14 -0800
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-22 09:50 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-22 18:23 +0100
Re: A binary search algorithm that searches for an element similar to the key pete <pfiland@mindspring.com> - 2011-12-22 06:56 -0500
Re: A binary search algorithm that searches for an element similar to the key pacman@kosh.dhis.org (Alan Curry) - 2011-12-22 21:59 +0000
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-25 11:54 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-25 15:45 +0100
Re: A binary search algorithm that searches for an element similar to the key "io_x" <a@b.c.invalid> - 2011-12-29 09:06 +0100
Re: A binary search algorithm that searches for an element similar to the key Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 16:44 -0800
Page 4 of 4 — ← Prev page 1 2 3 [4]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2011-12-25 11:54 +0100 |
| Message-ID | <4ef7001c$0$1386$4fafbaef@reader2.news.tin.it> |
| In reply to | #14808 |
"pozz" <pozzugno@gmail.com> ha scritto nel messaggio
news:jcr4q0$ps2$1@nnrp.ngi.it...
>I want to write the function binsearch_low() with the same interface of
>bsearch() standard function:
>
> void * binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare);
>
> This function should return a pointer to the element of the array that is the
> greatest among the element with a lower value than key. If no element lower
> than key exists, the function should return NULL.
>
> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the function
> should return NULL for key=8, 10 for key=11, 12 for key=12, 20 for key=22, 30
> for key=33.
yes i not miss the above...
here is the one i wrote
; return (u8*)-1 error, 0 not find, address of the found element in array
; if return 0 [not found]
; in ecx return the address element of the array < than key if exist
; else ecx=0
; in edx return the address element of the array > than key if exist
; else edx=0
; would be like the C library one, with the only difference return (u8*)-1 for
error
;u8* __stdcall
;binSearchR(u8* InPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 24 28 32 36 40
; 0k,4j,8i,12b,16ra, 20InKey,24InBase,28P_nElmBase,32P_SizeElmBase,36P_cmp + 64
; 84 88 92 96 100
binSearchR:
push ebx
push esi
push edi
push ebp
sub esp, 64
;int3
mov dword[esp+ 4], 0
mov dword[esp+ 8], 0 ; in ^4 and ^8 thre is the last element <
and >
cmp dword[esp+ 84], 0
je .e
cmp dword[esp+ 88], 0
je .e
mov edi, dword[esp+ 92]
mov ebx, dword[esp+ 100]
cmp dword[esp+ 96], 0
jle .e
xor ecx, ecx
cmp edi, 0
je .nf
mov esi, 0
jl .e
cmp ebx, 0
je .e
dec edi
jmp short .2
.nf: xor eax, eax
clc
jmp short .z
.e: xor eax, eax
dec eax
stc
jmp short .z
.2: cmp esi, edi
jg .nf
mov ebp, esi
add ebp, edi
shr ebp, 1 ; k=(i+j)/2
mov eax, dword[esp+ 96]
mul ebp
mov ecx, dword[esp+ 84]
cmp edx, 0
jne .e
add eax, dword[esp+ 88]
jc .e
mov dword[esp+ 0], eax
push ecx
push eax
call ebx
add esp, 8
cmp eax, 0
jle .3
dec ebp
mov ecx, dword[esp+ 0]
mov edi, ebp
mov dword[esp+ 4], ecx
jmp short .2
.3: jz .4
inc ebp
mov ecx, dword[esp+ 0]
mov esi, ebp
mov dword[esp+ 8], ecx
jmp short .2
.4: mov eax, dword[esp+ 0]
clc
.z: mov edx, dword[esp+ 4]
mov ecx, dword[esp+ 8]
lea esp, [esp+64]
pop ebp
pop edi
pop esi
pop ebx
ret 20
--------------------
the C test program
--------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define u32 unsigned
#define i32 int
#define u8 unsigned char
#define R return
#define P printf
#define F for
// const, how is smart...
#define cn const
/*
;return (u8*)-1 error, 0 not found, address of the found element in array
;if return 0 [not found]
; in ecx return the address element of the array < than key if exist
; else ecx=0
; in edx return the address element of the array > than key if exist
; else edx=0
would be like the C library one, with the only difference return (u8*)-1 for
error
*/
u8* __stdcall
binSearchR(u8* InPKey, u8* InBase, u32 nElmBase, u32 SizeElmBase,
i32 cmp(cn u8* elm1, cn u8* elm2) );
u32 __stdcall ReturnEcx(void);
u32 __stdcall ReturnEdx(void);
i32 cmpu32s(const void* elm1, const void* elm2)
{u32 m1, m2;
m1=*(u32*)elm1; m2=*(u32*)elm2;
if(m1<m2) R -1;
else if(m1>m2) R 1;
else R 0;
}
int main(int argc, char** argv)
{time_t in, fin;
double d;
u32 v[]={1, 2, 5, 7, 8, 8, 9, 13, 20}, val=4, *w, *ww, i;
u8 *r;
F(i=0; i<23; ++i)
{r=binSearchR((u8*)&i, (u8*) v, 9, sizeof(u32), cmpu32s);
w=(u32*) ReturnEcx(); ww=(u32*) ReturnEdx();
/* this is ok here because the -S traslation is:
;
; {r=binSearchR((u8*)&i, (u8*) v, 9, sizeof(u32), cmpu32s);
;
@10:
@12:
push offset _cmpu32s
push 4
push 9
lea edx,dword ptr [ebp-52]
push edx
lea ecx,dword ptr [ebp-60]
push ecx
call binSearchR
mov ebx,eax
;
; w=(u32*) ReturnEcx(); ww=(u32*) ReturnEdx();
;
?live1@176: ; EBX = r
call ReturnEcx
mov edi,eax
call ReturnEdx
mov esi,eax
it not will be ok if the compiler use something to trash ecx and edx
*/
if(r!=0) P("For %u r=%p find=%u\n", i, (void*)r, *r);
else {P("For %u ", i);
if(w!=0) P("w =%p find=%u- ", (void*)w, *w);
else P("w = 0- ");
if(ww!=0) P("ww=%p find=%u+ ", (void*)ww, *ww);
else P("ww= 0+ ");
P("\n");
}
}
r=bsearch(&val, v, 9, sizeof(u32), cmpu32s);
if(r!=0) P("r=%p find=%u\n", (void*)r, *r);
if(argc==2)
{int n=atoi(argv[1]);
int *data = (int *)malloc(n * sizeof *data);
if(data)
{int i, length, step, key;
long int sum;
for(i=0; i<n; i++) data[i]=2*i+1;
// Include one zero-length search for correctness testing
r = binSearchR(data, data, 0, sizeof(data[0]), cmpu32s);
printf("r=%p\n", (void*) r);
sum=0;
time(&in);
for(length=1; length<=n; length++)
for(step=1; step<=length; step++)
for(key=0; key<=2*length; key+=step)
{r=binSearchR(&key, data, length, sizeof(data[0]), cmpu32s);
if(r) sum+=(r-(u8*)data)/sizeof(data[0]);
}
time(&fin);
P("myBsearch=%f\n", (double) d=difftime(fin, in));
printf("sum=%ld\n", sum);
sum=0;
time(&in);
for(length=1; length<=n; length++)
for(step=1; step<=length; step++)
for(key=0; key<=2*length; key+=step)
{r=bsearch(&key, data, length, sizeof(data[0]), cmpu32s);
if(r) sum+=(r-(u8*)data)/sizeof(data[0]);
}
time(&fin);
P(" bsearch=%f\n", (double) d=difftime(fin, in));
printf("sum=%ld\n", sum);
return 0;
}
}
R 0;
}
-------------------------
the asm source code
-------------------------
PREPARSE MACRO2D
section DATA
hInstance dd 0
; 9
arrayInt dd 0,2,4,5,8,8,9,10, 11
export binSearchR
export ReturnEcx
export ReturnEdx
section TEXT
ReturnEcx: a=c|ret
ReturnEdx: a=r|ret
; return (u8*)-1 error, 0 not find, address of the found element in array
; if return 0 [not found]
; in ecx return the address element of the array < than key if exist
; else ecx=0
; in edx return the address element of the array > than key if exist
; else edx=0
; would be like the C library one, with the only difference return (u8*)-1 for
error
;u8* __stdcall
;binSearchR(u8* InPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 24 28 32 36 40
; 0k,4j,8i,12b,16ra, 20InKey,24InBase,28P_nElmBase,32P_SizeElmBase,36P_cmp + 64
; 84 88 92 96 100
binSearchR:
<b,i,j,k
s-=64
;int3
^4=0|^8=0 ; in ^4 and ^8 thre is the last element < and >
^84==0#.e|^88==0#.e|j=^92|b=^100|^96<=0?#.e
c^=c|j==0#.nf |i=0 |<?#.e|b==0#.e|--j|#.2
.nf: a^=a |clc|#.z
.e: a^=a|--a|stc|#.z
.2: i>j?#.nf|k=i|k+=j|k>>=1 ; k=(i+j)/2
a=^96|mul k|c=^84|r#.e|a+=^88|jc .e|^0=a
b<(a,c) |a>0!?#.3|--k |c=^0|j=k|^4=c|#.2
.3: =#.4|++k |c=^0|i=k|^8=c|#.2
.4: a=^0|clc
.z: r=^4|c=^8
s=&*s+64
>b,i,j,k
ret 20
Main:
mov eax D$esp+8
mov D$hInstance eax
mov eax 1
ret 12
---------------------------
the test result
---------------------------
For 0 w = 0- ww=0012FF58 find=1+
For 1 r=0012FF58 find=1
For 2 r=0012FF5C find=2
For 3 w =0012FF5C find=2- ww=0012FF60 find=5+
For 4 w =0012FF5C find=2- ww=0012FF60 find=5+
For 5 r=0012FF60 find=5
For 6 w =0012FF60 find=5- ww=0012FF64 find=7+
For 7 r=0012FF64 find=7
For 8 r=0012FF68 find=8
For 9 r=0012FF70 find=9
For 10 w =0012FF70 find=9- ww=0012FF74 find=13+
For 11 w =0012FF70 find=9- ww=0012FF74 find=13+
For 12 w =0012FF70 find=9- ww=0012FF74 find=13+
For 13 r=0012FF74 find=13
For 14 w =0012FF74 find=13- ww=0012FF78 find=20+
For 15 w =0012FF74 find=13- ww=0012FF78 find=20+
For 16 w =0012FF74 find=13- ww=0012FF78 find=20+
For 17 w =0012FF74 find=13- ww=0012FF78 find=20+
For 18 w =0012FF74 find=13- ww=0012FF78 find=20+
For 19 w =0012FF74 find=13- ww=0012FF78 find=20+
For 20 r=0012FF78 find=20
For 21 w =0012FF78 find=20- ww= 0+
For 22 w =0012FF78 find=20- ww= 0+
r=00000000
myBsearch=7.000000
sum=1373176982
bsearch=7.000000
sum=1373176982
-----------------------------------
the asm code here is better of your C code
in the error detection
and in the few lines of the source code
and in the algo implementation
etc
[toc] | [prev] | [next] | [standalone]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2011-12-25 15:45 +0100 |
| Message-ID | <4ef7362b$0$1374$4fafbaef@reader1.news.tin.it> |
| In reply to | #14984 |
"io_x" <a@b.c.invalid> ha scritto nel messaggio news:4ef7001c$0$1386$4fafbaef@reader2.news.tin.it... > ; return (u8*)-1 error, 0 not find, address of the found element in array > ; if return 0 [not found] > ; in ecx return the address element of the array < than key if exist > ; else ecx=0 > ; in edx return the address element of the array > than key if exist > ; else edx=0 > ; would be like the C library one, with the only difference return (u8*)-1 for > error > ;u8* __stdcall > ;binSearchR(u8* InPKey, u8* InBase, > ; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) ); > ; 24 28 32 36 40 > ; 0k,4j,8i,12b,16ra, 20InKey,24InBase,28P_nElmBase,32P_SizeElmBase,36P_cmp + > 64 >; 84 88 92 96 100 > binSearchR: > <b,i,j,k > s-=64 > ;int3 > ^4=0|^8=0 ; in ^4 and ^8 thre is the last element < and > > ^84==0#.e|^88==0#.e|j=^92|b=^100|^96<=0?#.e > c^=c|j==0#.nf |i=0 |<?#.e|b==0#.e|--j|#.2 i can cancel from above "c^=c" > .nf: a^=a |clc|#.z > .e: a^=a|--a|stc|#.z > .2: i>j?#.nf|k=i|k+=j|k>>=1 ; k=(i+j)/2 > a=^96|mul k|c=^84|r#.e|a+=^88|jc .e|^0=a for the error detection... for example here the "jc .e" jump if index+=address overflow how do you that in C? here "r#.e" chenck if index overflow with mult element size how do you that in C? for the C one there is only seg fault > b<(a,c) |a>0!?#.3|--k |c=^0|j=k|^4=c|#.2 > .3: =#.4|++k |c=^0|i=k|^8=c|#.2 > .4: a=^0|clc > .z: r=^4|c=^8 > s=&*s+64 >>b,i,j,k > ret 20 > ----------------------------------- > the asm code here is better of your C code > in the error detection > and in the few lines of the source code > and in the algo implementation > etc there is someone understand a proper subset of intel x86 + some macro sys is, as language, better than C? where better means: better in the error detection better in syntetize algos better in readability better in algo implementaton etc and no more UB ... do you think i'm delusional because i think that after many effort and time spend to this NG help me in the C language questions?
[toc] | [prev] | [next] | [standalone]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2011-12-29 09:06 +0100 |
| Message-ID | <4efc1e9f$0$1383$4fafbaef@reader1.news.tin.it> |
| In reply to | #14986 |
"io_x" <a@b.c.invalid> ha scritto nel messaggio news:4ef7362b$0$1374$4fafbaef@reader1.news.tin.it... >> the asm code here is better of your C code >> in the error detection >> and in the few lines of the source code >> and in the algo implementation >> etc > > there is someone understand a proper subset > of intel x86 + some macro sys is, > as language, better than C? > > where better means: > better in the error detection > better in syntetize algos > better in readability > better in algo implementaton > etc > and no more UB ... and structured programming if has some meaning... it has nothing in common with if() for(;;) while() etc loop it has something to do with the righ jumps in the right places, and in representing code in visual 2D dimension am i alone that say that? > do you think i'm delusional because i think that > after many effort and time spend to this NG > help me in the C language questions? > >
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2012-01-25 16:44 -0800 |
| Message-ID | <kfn39b35m2t.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #14808 |
pozz <pozzugno@gmail.com> writes:
> I want to write the function binsearch_low() with the same interface
> of bsearch() standard function:
>
> void * binsearch_low (const void *key, const void *array, size_t
> count, size_t size, comparison_fn_t compare);
>
> This function should return a pointer to the element of the array that
> is the greatest among the element with a lower value than key.
> [corrected in later message to specify less than or equal to key].
> If no element lower than [or equal to] key exists, the function should
> return NULL.
>
> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12,
> 20 for key=22, 30 for key=33.
>
> I started from a bsearch() implementation... [...snip that...]
> ...and arrived to the following algorithm:
>
> void *
> binsearch_low (const void *key, const void *array, size_t count,
> size_t size, comparison_fn_t compare)
> {
> int left = 0, right = count - 1;
> while (left < right - 1) {
> const int mid = (left + right) / 2;
> void *element = (unsigned char *)array + mid * size;
> if (compare(key, element) > 0) left = mid;
> else if (compare(key, element) < 0) right = mid - 1;
> else return (unsigned char *)array + mid * size;
> }
> if (compare(key, (unsigned char *)array + left * size) < 0) {
> return NULL;
> } else if (compare(key, (unsigned char *)array + right * size) >= 0) {
> return (unsigned char *)array + right * size;
> } else {
> return (unsigned char *)array + left * size;
> }
> }
>
> Do you have any suggestions and/or improvements?
What I thought was interesting was how much code people
wrote to do what seems like a fairly simple algorithm.
Here is a solution with one cast, one call to 'compare()',
and one 'return' at the bottom of the function:
void *
binsearch_low(
const void *key,
const void *keys_array, size_t count, size_t size,
comparison_fn_t compare
){
size_t n = count;
unsigned char (*blobs)[size] = (void*) keys_array;
while( n > 0 ){
size_t m = n/2;
if( compare( blobs[ m ], key ) > 0 ) n = m;
else blobs += m+1, n -= m+1;
}
return blobs == keys_array ? 0 : blobs[-1];
}
To see that it works, note the invariants (assuming the
keys in 'keys_array' are sorted to begin with):
1. If 'n > 0', then m (== n/2) is less than n, and m+1 is
greater than zero.
2. The assignment 'n = m;' adjusts (only) the upper end of
the search region and must reduce n; the assignments
'blobs += m+1, n -= m+1;' adjusts (only) the lower end
of the search region and also must reduce n.
3. Either 'blobs == keys_array', or 'blobs[-1]' is the
largest acceptable value in the set of keys examined
so far.
4. Any entries at 'blobs[n]' or beyond are too large.
5. Therefore, when 'n == 0', either 'blobs == keys_array'
and the answer is NULL, or 'blobs[-1]' has the largest
acceptable value, since all values 'blobs[0]' and
beyond are too large.
[toc] | [prev] | [standalone]
Page 4 of 4 — ← Prev page 1 2 3 [4]
Back to top | Article view | comp.lang.c
csiph-web