512array.mu

   1 # Inserting and deleting in arrays.
   2 #
   3 # The primitives here just do the work of making space and compacting.
   4
   5 fn slide-up _a: (addr array int), start: int, end: int, target: int {
   6   var a/esi: (addr array int) <- copy _a
   7   var src-idx/ecx: int <- copy start
   8   var dest-idx/edx: int <- copy target
   9   # if start == target, nothing to do
  10   {
  11     compare src-idx, dest-idx
  12     break-if-!=
  13     return
  14   }
  15   # if start < target, abort
  16   {
  17     compare src-idx, dest-idx
  18     break-if->
  19     abort "slide-up: target > start; use slide-down instead"
  20   }
  21   # perform the copy
  22   {
  23     compare src-idx, end
  24     break-if->=
  25     var dest/ebx: (addr int) <- index a, dest-idx
  26     var src/eax: (addr int) <- index a, src-idx
  27     var val/eax: int <- copy *src
  28     copy-to *dest, val
  29     src-idx <- increment
  30     dest-idx <- increment
  31     loop
  32   }
  33 }
  34
  35 fn slide-down _a: (addr array int), start: int, end: int, target: int {
  36   var a/esi: (addr array int) <- copy _a
  37   var src-idx/ecx: int <- copy end
  38   src-idx <- decrement
  39   var dest-idx/edx: int <- copy target
  40   dest-idx <- add end
  41   dest-idx <- subtract start
  42   dest-idx <- decrement
  43   # if start == target, nothing to do
  44   {
  45     compare src-idx, dest-idx
  46     break-if-!=
  47     return
  48   }
  49   # if start > target, abort
  50   {
  51     compare src-idx, dest-idx
  52     break-if-<
  53     abort "slide-down: target < start; use slide-down instead"
  54   }
  55   # perform the copy
  56   {
  57     compare src-idx, start
  58     break-if-<
  59     var dest/ebx: (addr int) <- index a, dest-idx
  60     var src/eax: (addr int) <- index a, src-idx
  61     var val/eax: int <- copy *src
  62     copy-to *dest, val
  63     src-idx <- decrement
  64     dest-idx <- decrement
  65     loop
  66   }
  67 }
  68
  69 fn test-slide-up {
  70   check-slide-up "0 1 2 3 0", 1/start 1/end, 0/target, "0 1 2 3 0", "F - test-slide-up/empty-interval"
  71   check-slide-up "0 1 2 3 0", 1/start 2/end, 0/target, "1 1 2 3 0", "F - test-slide-up/single-non-overlapping"
  72   check-slide-up "0 0 0 1 2 3 0", 3/start 6/end, 0/target, "1 2 3 1 2 3 0", "F - test-slide-up/multiple-non-overlapping"
  73   check-slide-up "0 1 2 3 0", 1/start 4/end, 0/target, "1 2 3 3 0", "F - test-slide-up/overlapping"
  74 }
  75
  76 fn test-slide-down {
  77   check-slide-down "0 1 2 3 0", 1/start 1/end, 4/target, "0 1 2 3 0", "F - test-slide-down/empty-interval"
  78   check-slide-down "0 1 2 3 0", 1/start 2/end, 4/target, "0 1 2 3 1", "F - test-slide-down/single-non-overlapping"
  79   check-slide-down "0 1 2 3 0 0 0", 1/start 4/end, 4/target, "0 1 2 3 1 2 3", "F - test-slide-down/multiple-non-overlapping"
  80   check-slide-down "0 1 2 3 0", 1/start 4/end, 2/target, "0 1 1 2 3", "F - test-slide-down/overlapping"
  81 }
  82
  83 # Return the index that val is at.
  84 # If not found, return len-1.
  85 # That way the result is always a valid index to pass into slide-down.
  86 fn find-slide-down-slot-in-array _a: (addr array int), _val: int -> _/ecx: int {
  87   var a/esi: (addr array int) <- copy _a
  88   var val/ebx: int <- copy _val
  89   var max/edx: int <- length a
  90   max <- decrement
  91   var i/ecx: int <- copy 0
  92   {
  93     compare i, max
  94     break-if->=
  95     var curr/eax: (addr int) <- index a, i
  96     compare *curr, val
  97     break-if-=
  98     i <- increment
  99     loop
 100   }
 101   return i
 102 }
 103
 104 # helpers for tests
 105 fn check-slide-up before: (addr array byte), start: int, end: int, target: int, after: (addr array byte), msg: (addr array byte) {
 106   var arr-h: (handle array int)
 107   var arr-ah/eax: (addr handle array int) <- address arr-h
 108   parse-array-of-decimal-ints before, arr-ah
 109   var arr/eax: (addr array int) <- lookup *arr-ah
 110   slide-up arr, start, end, target
 111   check-array-equal arr, after, msg
 112 }
 113
 114 fn check-slide-down before: (addr array byte), start: int, end: int, target: int, after: (addr array byte), msg: (addr array byte) {
 115   var arr-h: (handle array int)
 116   var arr-ah/eax: (addr handle array int) <- address arr-h
 117   parse-array-of-decimal-ints before, arr-ah
 118   var arr/eax: (addr array int) <- lookup *arr-ah
 119   slide-down arr, start, end, target
 120   check-array-equal arr, after, msg
 121 }