DJ Delorie wrote:
As written, the function will access element [30] of a 30-element array.
Um, no?
unsigned int mid = low + (high - low) / 2;
This can never give mid == high unless low == high, which won't happen
in that loop.
The math wants to search everything from (including) low to
(excluding) high.
(but I'm willing to be proven wrong...)
Whee, here we go...
(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)
Breakpoint 2, higher_prime_index (n=4294967295)
at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175 unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178 while (low < high)
(gdb)
180 unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181 if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182 low = mid + 1;
1: low = 0(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)
Breakpoint 2, higher_prime_index (n=4294967295)
at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175 unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178 while (low < high)
(gdb)
180 unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181 if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182 low = mid + 1;
1: low = 0
(gdb)
178 while (low < high)
1: low = 16
(gdb)
180 unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181 if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182 low = mid + 1;
(gdb)
178 while (low < high)
1: low = 16
(gdb)
180 unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181 if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182 low = mid + 1;
1: low = 16
(gdb)
178 while (low < high)
1: low = 24
(gdb)
180 unsigned int mid = low + (high - low) / 2;
1: low = 24
(gdb)
181 if (n > prime_tab[mid].prime)
1: low = 24
(gdb)
182 low = mid + 1;
1: low = 24
(gdb)
178 while (low < high)
1: low = 28
(gdb)
180 unsigned int mid = low + (high - low) / 2;
1: low = 28
(gdb)
181 if (n > prime_tab[mid].prime)
1: low = 28
(gdb)
182 low = mid + 1;
1: low = 28
(gdb)
178 while (low < high)
1: low = 30
(gdb)
188 if (n > prime_tab[low].prime)
1: low = 30
(gdb)
