# A doubly linked list permits bidirectional traversal.

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

# should I say in/contained-in:result, allow ingredients to refer to products?
recipe push x:_elem, in:address:shared:duplex-list:_elem -> in:address:shared:duplex-list:_elem [
  local-scope
  load-ingredients
  result:address:shared:duplex-list:_elem <- new {(duplex-list _elem): type}
  val:address:_elem <- get-address *result, value:offset
  *val <- copy x
  next:address:address:shared:duplex-list:_elem <- get-address *result, next:offset
  *next <- copy in
  {
    break-unless in
    prev:address:address:shared:duplex-list:_elem <- get-address *in, prev:offset
    *prev <- copy result
  }
  reply result  # needed explicitly because we need to replace 'in' with 'result'
]

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

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

recipe prev in:address:shared:duplex-list:_elem -> result:address:shared:duplex-list:_elem/contained-in:in [
  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:shared:duplex-list:character <- push 3, 0
    3:address:shared:duplex-list:character <- push 4, 3:address:shared:duplex-list:character
    3:address:shared:duplex-list:character <- push 5, 3:address:shared:duplex-list:character
    4:address:shared:duplex-list:character <- copy 3:address:shared:duplex-list:character
    5:character <- first 4:address:shared:duplex-list:character
    4:address:shared:duplex-list:character <- next 4:address:shared:duplex-list:character
    6:character <- first 4:address:shared:duplex-list:character
    4:address:shared:duplex-list:character <- next 4:address:shared:duplex-list:character
    7:character <- first 4:address:shared:duplex-list:character
    8:address:shared:duplex-list:character <- next 4:address:shared:duplex-list:character
    9:character <- first 8:address:shared:duplex-list:character
    10:address:shared:duplex-list:character <- next 8:address:shared:duplex-list:character
    11:address:shared:duplex-list:character <- prev 8:address:shared:duplex-list:character
    4:address:shared:duplex-list:character <- prev 4:address:shared:duplex-list:character
    12:character <- first 4:address:shared:duplex-list:character
    4:address:shared:duplex-list:character <- prev 4:address:shared:duplex-list:character
    13:character <- first 4:address:shared:duplex-list:character
    14:boolean <- equal 3:address:shared:duplex-list:character, 4:address:shared: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
  ]
]

# insert 'x' after 'in'
recipe insert x:_elem, in:address:shared:duplex-list:_elem -> in:address:shared:duplex-list:_elem [
  local-scope
  load-ingredients
  new-node:address:shared:duplex-list:_elem <- new {(duplex-list _elem): type}
  val:address:_elem <- get-address *new-node, value:offset
  *val <- copy x
  next-node:address:shared:duplex-list:_elem <- get *in, next:offset
  # in.next = new-node
  y:address:address:shared: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
  # next-node.prev = new-node
  y <- get-address *next-node, prev:offset
  *y <- copy new-node
]

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

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

# remove 'x' from its surrounding list 'in'
#
# Returns null if and only if list is empty. Beware: in that case any other
# pointers to the head are now invalid.
recipe remove x:address:shared:duplex-list:_elem/contained-in:in, in:address:shared:duplex-list:_elem -> in:address:shared:duplex-list:_elem [
  local-scope
  load-ingredients
  # if 'x' is null, return
  reply-unless x
  next-node:address:shared:duplex-list:_elem <- get *x, next:offset
  prev-node:address:shared:duplex-list:_elem <- get *x, prev:offset
  # null x's pointers
  tmp:address:address:shared:duplex-list:_elem <- get-address *x, next:offset
  *tmp <- copy 0
  tmp <- get-address *x, prev:offset
  *tmp <- copy 0
  # if next-node is not null, set its prev pointer
  {
    break-unless next-node
    tmp <- get-address *next-node, prev:offset
    *tmp <- copy prev-node
  }
  # if prev-node is not null, set its next pointer and return
  {
    break-unless prev-node
    tmp <- get-address *prev-node, next:offset
    *tmp <- copy next-node
    reply
  }
  # if prev-node is null, then we removed the node at 'in'
  # return the new head rather than the old 'in'
  reply next-node
]

scenario removing-from-duplex-list [
  run [
    1:address:shared:duplex-list:character <- push 3, 0
    1:address:shared:duplex-list:character <- push 4, 1:address:shared:duplex-list:character
    1:address:shared:duplex-list:character <- push 5, 1:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- next 1:address:shared:duplex-list:character  # 2 points at second element
    1:address:shared:duplex-list:character <- remove 2:address:shared:duplex-list:character, 1:address:shared:duplex-list:character
    3:boolean <- equal 2:address:shared:duplex-list:character, 0
    # check structure like before
    2:address:shared:duplex-list:character <- copy 1:address:shared:duplex-list:character
    4:character <- first 2:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- next 2:address:shared:duplex-list:character
    5:character <- first 2:address:shared:duplex-list:character
    6:address:shared:duplex-list:character <- next 2:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- prev 2:address:shared:duplex-list:character
    7:character <- first 2:address:shared:duplex-list:character
    8:boolean <- equal 1:address:shared:duplex-list:character, 2:address:shared:duplex-list:character
  ]
  memory-should-contain [
    3 <- 0  # remove returned non-null
    4 <- 5  # scanning next, skipping deleted element
    5 <- 3
    6 <- 0  # no more elements
    7 <- 5  # prev of final element
    8 <- 1  # list back at start
  ]
]

scenario removing-from-start-of-duplex-list [
  run [
    1:address:shared:duplex-list:character <- push 3, 0
    1:address:shared:duplex-list:character <- push 4, 1:address:shared:duplex-list:character
    1:address:shared:duplex-list:character <- push 5, 1:address:shared:duplex-list:character
    1:address:shared:duplex-list:character <- remove 1:address:shared:duplex-list:character, 1:address:shared:duplex-list:character
    # check structure like before
    2:address:shared:duplex-list:character <- copy 1:address:shared:duplex-list:character
    3:character <- first 2:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- next 2:address:shared:duplex-list:character
    4:character <- first 2:address:shared:duplex-list:character
    5:address:shared:duplex-list:character <- next 2:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- prev 2:address:shared:duplex-list:character
    6:character <- first 2:address:shared:duplex-list:character
    7:boolean <- equal 1:address:shared:duplex-list:character, 2:address:shared:duplex-list:character
  ]
  memory-should-contain [
    3 <- 4  # scanning next, skipping deleted element
    4 <- 3
    5 <- 0  # no more elements
    6 <- 4  # prev of final element
    7 <- 1  # list back at start
  ]
]

scenario removing-from-end-of-duplex-list [
  run [
    1:address:shared:duplex-list:character <- push 3, 0
    1:address:shared:duplex-list:character <- push 4, 1:address:shared:duplex-list:character
    1:address:shared:duplex-list:character <- push 5, 1:address:shared:duplex-list:character
    # delete last element
    2:address:shared:duplex-list:character <- next 1:address:shared:duplex-list:character
    2:address:shared:duplex-list:character <- next 2:address:shared:duplex-list:character
    1:address:shared:duplex-list:character <- remove 2:address:shared:dup<style>pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */</style><div class="highlight"><pre><span></span><span class="cm">/*</span>
<span class="cm"> * (C)opyright MMVI Anselm R. Garbe &lt;garbeam at gmail dot com&gt;</span>
<span class="cm"> * See LICENSE file for license details.</span>
<span class="cm"> */</span>
<span class="cp">#include</span><span class="w"> </span><span class="cpf">&quot;dwm.h&quot;</span>

<span class="cp">#include</span><span class="w"> </span><span class="cpf">&lt;stdlib.h&gt;</span>
<span class="cp">#include</span><span class="w"> </span><span class="cpf">&lt;X11/keysym.h&gt;</span>
<span class="cp">#include</span><span class="w"> </span><span class="cpf">&lt;X11/Xatom.h&gt;</span>

<span class="cm">/* static */</span>

<span class="k">typedef</span><span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="p">{</span>
<span class="w">	</span><span class="kt">unsigned</span><span class="w"> </span><span class="kt">long</span><span class="w"> </span><span class="n">mod</span><span class="p">;</span>
<span class="w">	</span><span class="n">KeySym</span><span class="w"> </span><span class="n">keysym</span><span class="p">;</span>
<span class="w">	</span><span class="kt">void</span><span class="w"> </span><span class="p">(</span><span class="o">*</span><span class="n">func</span><span class="p">)(</span><span class="n">Arg</span><span class="w"> </span><span class="o">*</span><span class="n">arg</span><span class="p">);</span>
<span class="w">	</span><span class="n">Arg</span><span class="w"> </span><span class="n">arg</span><span class="p">;</span>
<span class="p">}</span><span class="w"> </span><span class="n">Key</span><span class="p">;</span>

<span class="n">KEYS</span>

<span class="k">static</span><span class="w"> </span><span class="kt">unsigned</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">valid_mask</span><span class="w"> </span><span class="o">=</span><span class="w">  </span><span class="mi">255</span><span class="w"> </span><span class="o">&amp;</span><span class="w">  </span><span class="o">~</span><span class="p">(</span><span class="n">NUMLOCKMASK</span><span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="n">LockMask</span><span class="p">);</span>

<span class="k">static</span><span class="w"> </span><span class="kt">void</span>
<span class="nf">movemouse</span><span class="p">(</span><span class="n">Client</span><span class="w"> </span><span class="o">*</span><span class="n">c</span><span class="p">)</span>
<span class="p">{</span>
<span class="w">	</span><span class="kt">int</span><span class="w"> </span><span class="n">x1</span><span class="p">,</span><span class="w"> </span><span class="n">y1</span><span class="p">,</span><span class="w"> </span><span class="n">ocx</span><span class="p">,</span><span class="w"> </span><span class="n">ocy</span><span class="p">,</span><span class="w"> </span><span class="n">di</span><span class="p">;</span>
<span class="w">	</span><span class="kt">unsigned</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">dui</span><span class="p">;</span>
<span class="w">	</span><span class="n">Window</span>