Please modify this small program to make it safe

1

/*
Rust version of shellsort
~/.cargo/bin/rustc -O -o shellsort shellsort.rust; strip shellsort; time shellsort
*/

const N : usize = 100000000;
static mut THE_ARRAY : [f64;N] = [0.0_f64;N];

fn main() {
unsafe {
fill(&mut THE_ARRAY);
shell_sort(&mut THE_ARRAY);
}
}

/* Initialize an array of reals with a 'pseudo-random' sequence of values. */

fn fill(a : &mut [f64]) {
let n : usize = a.len();

if n > 0 {
const FACTOR : i64 = 8209;
const OFFSET : i64 = 1;
const MODULUS : i64 = 65537;
let mut seed : i64 = 1;

for i in 0..n {
  seed = (FACTOR * seed + OFFSET) % MODULUS;
  a[i] = seed as f64;
}

}
}

/* Shellsort (insertion sort by diminishing increment) an array of reals. */

fn shell_sort(a : &mut [f64]) {
let n : usize = a.len();

if n > 1 {
let mut h : usize = 4;

/*
 * Initialize h to value in sequence [..., 121, 40, 13, 4, 1]
 * that bounds n and results in about n ^ 1.25 comparisons.
 */

while h <= n {
  h = 3 * h + 1;
}

while h > 1 {
  h /= 3;

  for i in h..n {
    let ai : f64 = a[i];
    let mut j : usize = i;
    let mut jh : usize = j - h;
    let mut ajh : f64 = a[jh];

    while ai < ajh {
      a[j] = ajh;
      j = jh;

      if j < h {
        ajh = ai; /* Done. */
      } else {
        jh  = j - h;
        ajh = a[jh];
      }
    }

    a[j] = ai;
  }
}

}
}

2

The only unsafe part of the code is that you're taking a mutable reference to a static, but there's no need for THE_ARRAY to be static in the first place. Just define THE_ARRAY as a regular variable inside main().

1 Like
3

P.S. please read the pinned code formatting guide.

11 Likes
4

fn main() {

const N : usize = 100000000;

let mut THE_ARRAY : [f64;N] = [0.0_f64;N];

fill(&mut THE_ARRAY);

shell_sort(&mut THE_ARRAY);

}

~/.cargo/bin/rustc -O -o shellsort_safe shellsort_safe.rust ; strip shellsort_safe ; time shellsort_safe

warning: variable THE_ARRAY should have a snake case name

--> shellsort_safe.rust:9:11

9 | let mut THE_ARRAY : [f64;N] = [0.0_f64;N];

^^^^^^^^^ help: convert the identifier to snake case: the_array

= note: #[warn(non_snake_case)] on by default

warning: 1 warning emitted

thread 'main' has overflowed its stack

fatal runtime error: stack overflow

Abort (core dumped)

5

There's no way that you're on an OS where the stack size exceeds 800 MB.
You may want to use a heap-allocated collection, such as a Vec instead.
Also re-read and implement @quinedot 's post.