suckless/dwm - Unnamed repository; edit this file 'description' to name the repository.

# A doubly linked list permits bidirectional traversal.

container duplex-list:_elem [
  value:_elem
  next:address:duplex-list:_elem
  prev:address:duplex-list:_elem
]

recipe push-duplex x:_elem, in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
  local-scope
  load-ingredients
  result <- new {(duplex-list _elem): type}
  val:address:_elem <- get-address *result, value:offset
  *val <- copy x
  next:address:address:duplex-list:_elem <- get-address *result, next:offset
  *next <- copy in
  reply-unless in
  prev:address:address:duplex-list:_elem <- get-address *in, prev:offset
  *prev <- copy result
]

recipe first-duplex in:address:duplex-list:_elem -> result:_elem [
  local-scope
  load-ingredients
  reply-unless in, 0
  result <- get *in, value:offset
]

recipe next-duplex in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
  local-scope
  load-ingredients
  reply-unless in, 0
  result <- get *in, next:offset
]

recipe prev-duplex in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
  local-scope
  load-ingredients
  reply-unless in, 0
  result <- get *in, prev:offset
  reply result
]

scenario duplex-list-handling [
  run [
    # reserve locations 0, 1 and 2 to check for missing null check
    1:number <- copy 34
    2:number <- copy 35
    3:address:duplex-list:character <- copy 0
    3:address:duplex-list:character <- push-duplex 3, 3:address:duplex-list:character
    3:address:duplex-list:character <- push-duplex 4, 3:address:duplex-list:character
    3:address:duplex-list:character <- push-duplex 5, 3:address:duplex-list:character
    4:address:duplex-list:character <- copy 3:address:duplex-list:character
    5:character <- first-duplex 4:address:duplex-list:character
    4:address:duplex-list:character <- next-duplex 4:address:duplex-list:character
    6:character <- first-duplex 4:address:duplex-list:character
    4:address:duplex-list:character <- next-duplex 4:address:duplex-list:character
    7:character <- first-duplex 4:address:duplex-list:character
    8:address:duplex-list:character <- next-duplex 4:address:duplex-list:character
    9:character <- first-duplex 8:address:duplex-list:character
    10:address:duplex-list:character <- next-duplex 8:address:duplex-list:character
    11:address:duplex-list:character <- prev-duplex 8:address:duplex-list:character
    4:address:duplex-list:character <- prev-duplex 4:address:duplex-list:character
    12:character <- first-duplex 4:address:duplex-list:character
    4:address:duplex-list:character <- prev-duplex 4:address:duplex-list:character
    13:character <- first-duplex 4:address:duplex-list:character
    14:boolean <- equal 3:address:duplex-list:character, 4:address:duplex-list:character
  ]
  memory-should-contain [
    0 <- 0  # no modifications to null pointers
    1 <- 34
    2 <- 35
    5 <- 5  # scanning next
    6 <- 4
    7 <- 3
    8 <- 0  # null
    9 <- 0  # first of null
    10 <- 0  # next of null
    11 <- 0  # prev of null
    12 <- 4  # then start scanning prev
    13 <- 5
    14 <- 1  # list back at start
  ]
]

# Inserts 'x' after 'in'. Returns some pointer into the list.
recipe insert-duplex x:_elem, in:address:duplex-list:_elem -> new-node:address:duplex-list:_elem [
  local-scope
  load-ingredients
  new-node <- new {(duplex-list _elem): type}
  val:address:_elem <- get-address *new-node, value:offset
  *val <- copy x
  next-node:address:duplex-list:_elem <- get *in, next:offset
  # in.next = new-node
  y:address:address:duplex-list:_elem <- get-address *in, next:offset
  *y <- copy new-node
  # new-node.prev = in
  y <- get-address *new-node, prev:offset
  *y <- copy in
  # new-node.next = next-node
  y <- get-address *new-node, next:offset
  *y <- copy next-node
  # if next-node is not null
  reply-unless next-node, new-node
  # next-node.prev = new-node
  y <- get-address *next-node, prev:offset
  *y <- copy new-node
  reply new-node  # just signalling something changed; don't rely on the result
]

scenario inserting-into-duplex-list [
  run [
    1:address:duplex-list:character <- copy 0  # 1 points to head of list
    1:address:duplex-list:character <- push-duplex 3, 1:address:duplex-list:character
    1:address:duplex-list:character <- push-duplex 4, 1:address:duplex-list:character
    1:address:duplex-list:character <- push-duplex 5, 1:address:duplex-list:character
    2:address:duplex-list:character <- next-duplex 1:address:duplex-list:character  # 2 points inside list
    2:address:duplex-list:character <- insert-duplex 6, 2:address:duplex-list:character
    # check structure like before
    2:address:duplex-list:character <- copy 1:address:duplex-list:character
    3:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- next-duplex 2:address:duplex-list:character
    4:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- next-duplex 2:address:duplex-list:character
    5:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- next-duplex 2:address:duplex-list:character
    6:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- prev-duplex 2:address:duplex-list:character
    7:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- prev-duplex 2:address:duplex-list:character
    8:character <- first-duplex 2:address:duplex-list:character
    2:address:duplex-list:character <- prev-duplex 2:address:duplex-list:character
    9:character <- first-duplex 2:address:duplex-list:character
    10:boolean <- equal 1:address:duplex-list:character, 2:address:duplex-list:character
  ]
  memory-should-contain [
    3 <- 5  # scanning next
    4 <- 4
    5 <- 6  # inserted element
    6 <- 3
    7 <- 6  # then prev
    8 <- 4
    9 <- 5
    10 <- 1  # list back at start
  ]
]

scenario inserting-at-end-of-duplex-list [
  run [
    1:address:duplex-list:character <- copy 0  # 1 points to head of list
    1:address:duplex-list:character <- push-duplex 3, 1:address:duplex-list:character
    1:address:duplex-list:character <- push-duplex 4, 1:address:duplex-list:character
    1:address:duplex-list:character <- push-duplex 5, 1:address:duplex-list:character
    2:address:duplex-list:character <- next-duplex 1:address:duplex-list:character  # 2 points inside list
    2:address:duplex-list:character <- next-duplex 2, "run") << "storing 0x" << HEXWORD << *signed_arg1 << end();
  SF = (*signed_arg1 >> 31);
  ZF = (*signed_arg1 == 0);
  CF = false;
  OF = false;
  trace(Callstack_depth+1, "run") << "SF=" << SF << "; ZF=" << ZF << "; CF=" << CF << "; OF=" << OF << end();
  break;
}

//:: not

:(code)
void test_not_r32() {
  Reg[EBX].i = 0x0f0f00ff;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  f7     d3                                    \n"  // not EBX
      // ModR/M in binary: 11 (direct mode) 010 (subop not) 011 (dest EBX)
  );
  CHECK_TRACE_CONTENTS(
      "run: operate on r/m32\n"
      "run: r/m32 is EBX\n"
      "run: subop: not\n"
      "run: storing 0xf0f0ff00\n"
  );
}

:(before "End Op f7 Subops")
case 2: {  // not r/m32
  trace(Callstack_depth+1, "run") << "subop: not" << end();
  *arg1 = ~(*arg1);
  trace(Callstack_depth+1, "run") << "storing 0x" << HEXWORD << *arg1 << end();
  // no flags affected
  break;
}

//:: compare (cmp)

:(before "End Initialize Op Names")
put_new(Name, "39", "compare: set SF if rm32 < r32 (cmp)");

:(code)
void test_compare_r32_with_r32_greater() {
  Reg[EAX].i = 0x0a0b0c0d;
  Reg[EBX].i = 0x0a0b0c07;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX with EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=0; ZF=0; CF=0; OF=0\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x39: {  // set SF if r/m32 < r32
  const uint8_t modrm = next();
  const uint8_t reg2 = (modrm>>3)&0x7;
  trace(Callstack_depth+1, "run") << "compare r/m32 with " << rname(reg2) << end();
  const int32_t* signed_arg1 = effective_address(modrm);
  const int32_t signed_difference = *signed_arg1 - Reg[reg2].i;
  SF = (signed_difference < 0);
  ZF = (signed_difference == 0);
  const int64_t signed_full_difference = static_cast<int64_t>(*signed_arg1) - Reg[reg2].i;
  OF = (signed_difference != signed_full_difference);
  // set CF
  const uint32_t unsigned_arg1 = static_cast<uint32_t>(*signed_arg1);
  const uint32_t unsigned_difference = unsigned_arg1 - Reg[reg2].u;
  const uint64_t unsigned_full_difference = static_cast<uint64_t>(unsigned_arg1) - Reg[reg2].u;
  CF = (unsigned_difference != unsigned_full_difference);
  trace(Callstack_depth+1, "run") << "SF=" << SF << "; ZF=" << ZF << "; CF=" << CF << "; OF=" << OF << end();
  break;
}

:(code)
void test_compare_r32_with_r32_lesser_unsigned_and_signed() {
  Reg[EAX].i = 0x0a0b0c07;
  Reg[EBX].i = 0x0a0b0c0d;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX with EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=1; ZF=0; CF=1; OF=0\n"
  );
}

void test_compare_r32_with_r32_lesser_unsigned_and_signed_due_to_overflow() {
  Reg[EAX].i = 0x7fffffff;  // largest positive signed integer
  Reg[EBX].i = 0x80000000;  // smallest negative signed integer
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX with EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=1; ZF=0; CF=1; OF=1\n"
  );
}

void test_compare_r32_with_r32_lesser_signed() {
  Reg[EAX].i = 0xffffffff;  // -1
  Reg[EBX].i = 0x00000001;  // 1
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX with EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=1; ZF=0; CF=0; OF=0\n"
  );
}

void test_compare_r32_with_r32_lesser_unsigned() {
  Reg[EAX].i = 0x00000001;  // 1
  Reg[EBX].i = 0xffffffff;  // -1
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX with EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=0; ZF=0; CF=1; OF=0\n"
  );
}

void test_compare_r32_with_r32_equal() {
  Reg[EAX].i = 0x0a0b0c0d;
  Reg[EBX].i = 0x0a0b0c0d;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  39     d8                                    \n"  // compare EAX and EBX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: compare r/m32 with EBX\n"
      "run: r/m32 is EAX\n"
      "run: SF=0; ZF=1; CF=0; OF=0\n"
  );
}

//:: copy (mov)

:(before "End Initialize Op Names")
put_new(Name, "89", "copy r32 to rm32 (mov)");

:(code)
void test_copy_r32_to_r32() {
  Reg[EBX].i = 0xaf;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  89     d8                                    \n"  // copy EBX to EAX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: copy EBX to r/m32\n"
      "run: r/m32 is EAX\n"
      "run: storing 0x000000af\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x89: {  // copy r32 to r/m32
  const uint8_t modrm = next();
  const uint8_t rsrc = (modrm>>3)&0x7;
  trace(Callstack_depth+1, "run") << "copy " << rname(rsrc) << " to r/m32" << end();
  int32_t* dest = effective_address(modrm);
  *dest = Reg[rsrc].i;
  trace(Callstack_depth+1, "run") << "storing 0x" << HEXWORD << *dest << end();
  break;
}

//:: xchg

:(before "End Initialize Op Names")
put_new(Name, "87", "swap the contents of r32 and rm32 (xchg)");

:(code)
void test_xchg_r32_with_r32() {
  Reg[EBX].i = 0xaf;
  Reg[EAX].i = 0x2e;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  87     d8                                    \n"  // exchange EBX with EAX
      // ModR/M in binary: 11 (direct mode) 011 (src EBX) 000 (dest EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: exchange EBX with r/m32\n"
      "run: r/m32 is EAX\n"
      "run: storing 0x000000af in r/m32\n"
      "run: storing 0x0000002e in EBX\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x87: {  // exchange r32 with r/m32
  const uint8_t modrm = next();
  const uint8_t reg2 = (modrm>>3)&0x7;
  trace(Callstack_depth+1, "run") << "exchange " << rname(reg2) << " with r/m32" << end();
  int32_t* arg1 = effective_address(modrm);
  const int32_t tmp = *arg1;
  *arg1 = Reg[reg2].i;
  Reg[reg2].i = tmp;
  trace(Callstack_depth+1, "run") << "storing 0x" << HEXWORD << *arg1 << " in r/m32" << end();
  trace(Callstack_depth+1, "run") << "storing 0x" << HEXWORD << Reg[reg2].i << " in " << rname(reg2) << end();
  break;
}

//:: increment

:(before "End Initialize Op Names")
put_new(Name, "40", "increment EAX (inc)");
put_new(Name, "41", "increment ECX (inc)");
put_new(Name, "42", "increment EDX (inc)");
put_new(Name, "43", "increment EBX (inc)");
put_new(Name, "44", "increment ESP (inc)");
put_new(Name, "45", "increment EBP (inc)");
put_new(Name, "46", "increment ESI (inc)");
put_new(Name, "47", "increment EDI (inc)");

:(code)
void test_increment_r32() {
  Reg[ECX].u = 0x1f;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  41                                           \n"  // increment ECX
  );
  CHECK_TRACE_CONTENTS(
      "run: increment ECX\n"
      "run: storing value 0x00000020\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x40:
case 0x41:
case 0x42:
case 0x43:
case 0x44:
case 0x45:
case 0x46:
case 0x47: {  // increment r32
  const uint8_t reg = op & 0x7;
  trace(Callstack_depth+1, "run") << "increment " << rname(reg) << end();
  ++Reg[reg].u;
  trace(Callstack_depth+1, "run") << "storing value 0x" << HEXWORD << Reg[reg].u << end();
  break;
}

:(before "End Initialize Op Names")
put_new(Name, "ff", "increment/decrement/jump/push/call rm32 based on subop (inc/dec/jmp/push/call)");

:(code)
void test_increment_rm32() {
  Reg[EAX].u = 0x20;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  ff     c0                                    \n"  // increment EAX
      // ModR/M in binary: 11 (direct mode) 000 (subop inc) 000 (EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: increment r/m32\n"
      "run: r/m32 is EAX\n"
      "run: storing value 0x00000021\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0xff: {
  const uint8_t modrm = next();
  const uint8_t subop = (modrm>>3)&0x7;  // middle 3 'reg opcode' bits
  switch (subop) {
    case 0: {  // increment r/m32
      trace(Callstack_depth+1, "run") << "increment r/m32" << end();
      int32_t* arg = effective_address(modrm);
      ++*arg;
      trace(Callstack_depth+1, "run") << "storing value 0x" << HEXWORD << *arg << end();
      break;
    }
    default:
      cerr << "unrecognized subop for ff: " << HEXBYTE << NUM(subop) << '\n';
      exit(1);
    // End Op ff Subops
  }
  break;
}

//:: decrement

:(before "End Initialize Op Names")
put_new(Name, "48", "decrement EAX (dec)");
put_new(Name, "49", "decrement ECX (dec)");
put_new(Name, "4a", "decrement EDX (dec)");
put_new(Name, "4b", "decrement EBX (dec)");
put_new(Name, "4c", "decrement ESP (dec)");
put_new(Name, "4d", "decrement EBP (dec)");
put_new(Name, "4e", "decrement ESI (dec)");
put_new(Name, "4f", "decrement EDI (dec)");

:(code)
void test_decrement_r32() {
  Reg[ECX].u = 0x1f;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  49                                           \n"  // decrement ECX
  );
  CHECK_TRACE_CONTENTS(
      "run: decrement ECX\n"
      "run: storing value 0x0000001e\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x48:
case 0x49:
case 0x4a:
case 0x4b:
case 0x4c:
case 0x4d:
case 0x4e:
case 0x4f: {  // decrement r32
  const uint8_t reg = op & 0x7;
  trace(Callstack_depth+1, "run") << "decrement " << rname(reg) << end();
  --Reg[reg].u;
  trace(Callstack_depth+1, "run") << "storing value 0x" << HEXWORD << Reg[reg].u << end();
  break;
}

:(code)
void test_decrement_rm32() {
  Reg[EAX].u = 0x20;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  ff     c8                                    \n"  // decrement EAX
      // ModR/M in binary: 11 (direct mode) 001 (subop inc) 000 (EAX)
  );
  CHECK_TRACE_CONTENTS(
      "run: decrement r/m32\n"
      "run: r/m32 is EAX\n"
      "run: storing value 0x0000001f\n"
  );
}

:(before "End Op ff Subops")
case 1: {  // decrement r/m32
  trace(Callstack_depth+1, "run") << "decrement r/m32" << end();
  int32_t* arg = effective_address(modrm);
  --*arg;
  trace(Callstack_depth+1, "run") << "storing value 0x" << HEXWORD << *arg << end();
  break;
}

//:: push

:(before "End Initialize Op Names")
put_new(Name, "50", "push EAX to stack (push)");
put_new(Name, "51", "push ECX to stack (push)");
put_new(Name, "52", "push EDX to stack (push)");
put_new(Name, "53", "push EBX to stack (push)");
put_new(Name, "54", "push ESP to stack (push)");
put_new(Name, "55", "push EBP to stack (push)");
put_new(Name, "56", "push ESI to stack (push)");
put_new(Name, "57", "push EDI to stack (push)");

:(code)
void test_push_r32() {
  Mem.push_back(vma(0xbd000000));  // manually allocate memory
  Reg[ESP].u = 0xbd000008;
  Reg[EBX].i = 0x0000000a;
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  53                                           \n"  // push EBX to stack
  );
  CHECK_TRACE_CONTENTS(
      "run: push EBX\n"
      "run: decrementing ESP to 0xbd000004\n"
      "run: pushing value 0x0000000a\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x50:
case 0x51:
case 0x52:
case 0x53:
case 0x54:
case 0x55:
case 0x56:
case 0x57: {  // push r32 to stack
  uint8_t reg = op & 0x7;
  trace(Callstack_depth+1, "run") << "push " << rname(reg) << end();
//?   cerr << "push: " << NUM(reg) << ": " << Reg[reg].u << " => " << Reg[ESP].u << '\n';
  push(Reg[reg].u);
  break;
}

//:: pop

:(before "End Initialize Op Names")
put_new(Name, "58", "pop top of stack to EAX (pop)");
put_new(Name, "59", "pop top of stack to ECX (pop)");
put_new(Name, "5a", "pop top of stack to EDX (pop)");
put_new(Name, "5b", "pop top of stack to EBX (pop)");
put_new(Name, "5c", "pop top of stack to ESP (pop)");
put_new(Name, "5d", "pop top of stack to EBP (pop)");
put_new(Name, "5e", "pop top of stack to ESI (pop)");
put_new(Name, "5f", "pop top of stack to EDI (pop)");

:(code)
void test_pop_r32() {
  Mem.push_back(vma(0xbd000000));  // manually allocate memory
  Reg[ESP].u = 0xbd000008;
  write_mem_i32(0xbd000008, 0x0000000a);  // ..before this write
  run(
      "== code 0x1\n"  // code segment
      // op     ModR/M  SIB   displacement  immediate
      "  5b                                           \n"  // pop stack to EBX
      "== data 0x2000\n"  // data segment
      "0a 00 00 00\n"  // 0x0000000a
  );
  CHECK_TRACE_CONTENTS(
      "run: pop into EBX\n"
      "run: popping value 0x0000000a\n"
      "run: incrementing ESP to 0xbd00000c\n"
  );
}

:(before "End Single-Byte Opcodes")
case 0x58:
case 0x59:
case 0x5a:
case 0x5b:
case 0x5c:
case 0x5d:
case 0x5e:
case 0x5f: {  // pop stack into r32
  const uint8_t reg = op & 0x7;
  trace(Callstack_depth+1, "run") << "pop into " << rname(reg) << end();
//?   cerr << "pop from " << Reg[ESP].u << '\n';
  Reg[reg].u = pop();
//?   cerr << "=> " << NUM(reg) << ": " << Reg[reg].u << '\n';
  break;
}
:(code)
uint32_t pop() {
  const uint32_t result = read_mem_u32(Reg[ESP].u);
  trace(Callstack_depth+1, "run") << "popping value 0x" << HEXWORD << result << end();
  Reg[ESP].u += 4;
  trace(Callstack_depth+1, "run") << "incrementing ESP to 0x" << HEXWORD << Reg[ESP].u << end();
  assert(Reg[ESP].u < AFTER_STACK);
  return result;
}

end for hygiene. recipe remove-duplex-between start:address:duplex-list:_elem, end:address:duplex-list:_elem -> start:address:duplex-list:_elem [ local-scope load-ingredients reply-unless start # start->next->prev = 0 # start->next = end next:address:address:duplex-list:_elem <- get-address *start, next:offset nothing-to-delete?:boolean <- equal *next, end reply-if nothing-to-delete? prev:address:address:duplex-list:_elem <- get-address **next, prev:offset *prev <- copy 0 *next <- copy end reply-unless end # end->prev->next = 0 # end->prev = start prev <- get-address *end, prev:offset next <- get-address **prev, next:offset *next <- copy 0 *prev <- copy start ] scenario remove-range [ # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] 1:address:duplex-list:character <- copy 0 # 1 points to singleton list 1:address:duplex-list:character <- push-duplex 18, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 17, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 16, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 15, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 14, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 13, 1:address:duplex-list:character run [ # delete 16 onwards # first pointer: to the third element 2:address:duplex-list:character <- next-duplex 1:address:duplex-list:character 2:address:duplex-list:character <- next-duplex 2:address:duplex-list:character 2:address:duplex-list:character <- remove-duplex-between 2:address:duplex-list:character, 0 # now check the list 4:character <- get *1:address:duplex-list:character, value:offset 5:address:duplex-list:character <- next-duplex 1:address:duplex-list:character 6:character <- get *5:address:duplex-list:character, value:offset 7:address:duplex-list:character <- next-duplex 5:address:duplex-list:character 8:character <- get *7:address:duplex-list:character, value:offset 9:address:duplex-list:character <- next-duplex 7:address:duplex-list:character ] memory-should-contain [ 4 <- 13 6 <- 14 8 <- 15 9 <- 0 ] ] scenario remove-range-to-end [ # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] 1:address:duplex-list:character <- copy 0 # 1 points to singleton list 1:address:duplex-list:character <- push-duplex 18, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 17, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 16, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 15, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 14, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 13, 1:address:duplex-list:character run [ # delete 15, 16 and 17 # first pointer: to the third element 2:address:duplex-list:character <- next-duplex 1:address:duplex-list:character # second pointer: to the fifth element 3:address:duplex-list:character <- next-duplex 2:address:duplex-list:character 3:address:duplex-list:character <- next-duplex 3:address:duplex-list:character 3:address:duplex-list:character <- next-duplex 3:address:duplex-list:character 3:address:duplex-list:character <- next-duplex 3:address:duplex-list:character remove-duplex-between 2:address:duplex-list:character, 3:address:duplex-list:character # now check the list 4:character <- get *1:address:duplex-list:character, value:offset 5:address:duplex-list:character <- next-duplex 1:address:duplex-list:character 6:character <- get *5:address:duplex-list:character, value:offset 7:address:duplex-list:character <- next-duplex 5:address:duplex-list:character 8:character <- get *7:address:duplex-list:character, value:offset 9:address:duplex-list:character <- next-duplex 7:address:duplex-list:character ] memory-should-contain [ 4 <- 13 6 <- 14 8 <- 18 9 <- 0 ] ] scenario remove-range-empty [ # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] 1:address:duplex-list:character <- copy 0 # 1 points to singleton list 1:address:duplex-list:character <- push-duplex 14, 1:address:duplex-list:character 1:address:duplex-list:character <- push-duplex 13, 1:address:duplex-list:character run [ # delete 16 onwards # first pointer: to the third element 2:address:duplex-list:character <- next-duplex 1:address:duplex-list:character remove-duplex-between 1:address:duplex-list:character, 2:address:duplex-list:character # now check the list 4:character <- get *1:address:duplex-list:character, value:offset 5:address:duplex-list:character <- next-duplex 1:address:duplex-list:character 6:character <- get *5:address:duplex-list:character, value:offset 7:address:duplex-list:character <- next-duplex 5:address:duplex-list:character ] memory-should-contain [ 4 <- 13 6 <- 14 7 <- 0 ] ] # Inserts list beginning at 'new' after 'in'. Returns some pointer into the list. recipe insert-duplex-range in:address:duplex-list:_elem, start:address:duplex-list:_elem -> in:address:duplex-list:_elem [ local-scope load-ingredients reply-unless in reply-unless start end:address:duplex-list:_elem <- copy start { next:address:duplex-list:_elem <- next-duplex end/insert-range break-unless next end <- copy next loop } next:address:duplex-list:_elem <- next-duplex in dest:address:address:duplex-list:_elem <- get-address *end, next:offset *dest <- copy next { break-unless next dest <- get-address *next, prev:offset *dest <- copy end } dest <- get-address *in, next:offset *dest <- copy start dest <- get-address *start, prev:offset *dest <- copy in ] recipe append-duplex in:address:duplex-list:_elem, new:address:duplex-list:_elem -> in:address:duplex-list:_elem [ local-scope load-ingredients last:address:duplex-list:_elem <- last-duplex in dest:address:address:duplex-list:_elem <- get-address *last, next:offset *dest <- copy new reply-unless new dest <- get-address *new, prev:offset *dest <- copy last ] recipe last-duplex in:address:duplex-list:_elem -> result:address:duplex-list:_elem [ local-scope load-ingredients result <- copy in { next:address:duplex-list:_elem <- next-duplex result break-unless next result <- copy next loop } ] # helper for debugging recipe dump-duplex-from x:address:duplex-list:_elem [ local-scope load-ingredients $print x, [: ] { break-unless x c:_elem <- get *x, value:offset $print c, [ ] x <- next-duplex x { is-newline?:boolean <- equal c, 10/newline break-unless is-newline? $print 10/newline $print x, [: ] } loop } $print 10/newline, [---], 10/newline ] recipe force-specialization-duplex-list-character [ 1:address:duplex-list:character <- push-duplex 2:character, 1:address:duplex-list:character 2:character <- first-duplex 1:address:duplex-list:character 1:address:duplex-list:character <- next-duplex 1:address:duplex-list:character 1:address:duplex-list:character <- prev-duplex 1:address:duplex-list:character 1:address:duplex-list:character <- insert-duplex 2:character, 1:address:duplex-list:character 1:address:duplex-list:character <- remove-duplex 1:address:duplex-list:character 1:address:duplex-list:character <- remove-duplex-between 1:address:duplex-list:character, 1:address:duplex-list:character 1:address:duplex-list:character <- insert-duplex-range 1:address:duplex-list:character, 1:address:duplex-list:character 1:address:duplex-list:character <- append-duplex 1:address:duplex-list:character, 1:address:duplex-list:character 1:address:duplex-list:character <- last-duplex 1:address:duplex-list:character ]


context:
space:
mode: