func (l *List) Swap(i, j uint64) (err error) {
	if i >= l.count {
		return errors.Errorf("index, i, out of range")
	} else if j >= l.count {
		return errors.Errorf("index, j, out of range")
	}
	return l.blk(i, func(iIdx *idxBlk) (err error) {
		var ia uint64
		var I uint16 = uint16(i % itemsPerIdx)
		ia, err = iIdx.Get(I)
		if err != nil {
			return err
		}
		return l.blk(j, func(jIdx *idxBlk) (err error) {
			var ja uint64
			var J uint16 = uint16(j % itemsPerIdx)
			ja, err = jIdx.Get(J)
			if err != nil {
				return err
			}
			err = iIdx.Set(I, ja)
			if err != nil {
				return err
			}
			return jIdx.Set(J, ia)
		})
	})
}

func (n *internal) putKey(v *Varchar, key []byte, put func(i int) error) (err error) {
	if n.keyCount()+1 >= int(n.meta.keyCap) {
		return errors.Errorf("Block is full.")
	}

	var i int
	var has bool
	if n.meta.flags&consts.VARCHAR_KEYS == 0 {
		i, has, err = find(v, n, key)
	} else {
		err = v.Do(*slice.AsUint64(&key), func(key []byte) (err error) {
			i, has, err = find(v, n, key)
			return err
		})
	}
	if err != nil {
		return err
	}

	if i < 0 {
		return errors.Errorf("find returned a negative int")
	} else if i >= int(n.meta.keyCap) {
		return errors.Errorf("find returned a int > than len(keys)")
	} else if has {
		return errors.Errorf(fmt.Sprintf("would have inserted a duplicate key, %v", key))
	}
	if err := n.putKeyAt(key, i); err != nil {
		return err
	}
	return put(i)
}

/* returns the key at the address and index or an error
 */
func (self *BpTree) keyAt(a uint64, i int) (key []byte, err error) {
	err = self.do(
		a,
		func(n *internal) error {
			if i >= int(n.meta.keyCount) {
				return errors.Errorf("out of range")
			}
			return n.doKeyAt(self.varchar, i, func(k []byte) error {
				key = make([]byte, len(k))
				copy(key, k)
				return nil
			})
		},
		func(n *leaf) error {
			if i >= int(n.meta.keyCount) {
				return errors.Errorf("out of range")
			}
			return n.doKeyAt(self.varchar, i, func(k []byte) error {
				key = make([]byte, len(k))
				copy(key, k)
				return nil
			})
		},
	)
	if err != nil {
		return nil, err
	}
	return key, nil
}

func (v *Varchar) doFree(a uint64, do func(*varFree) error) error {
	return v.do(
		a,
		func(*varCtrl) error { return errors.Errorf("unexpected ctrl blk") },
		do,
		func(*varRunMeta) error { return errors.Errorf("unexpected run blk") },
	)
}

func (v *Varchar) doCtrl(do func(*varCtrl) error) error {
	return v.do(
		v.a,
		do,
		func(*varFree) error { return errors.Errorf("unexpected free blk") },
		func(*varRunMeta) error { return errors.Errorf("unexpected run blk") },
	)
}

// Remove the underlying file. (must be already closed).
func (self *BlockFile) Remove() error {
	if self.opened {
		return errors.Errorf("Expected file to be closed")
	}
	if self.Path() == "" {
		return errors.Errorf("This was an anonymous map")
	}
	return os.Remove(self.Path())
}

func (n *internal) updateK(v *Varchar, i int, key []byte) error {
	if i < 0 || i >= int(n.meta.keyCount) {
		return errors.Errorf("key is out of range")
	}
	if len(key) != int(n.meta.keySize) {
		return errors.Errorf("key was the wrong size")
	}
	idx, has, err := find(v, n, key)
	if err != nil {
		return err
	}
	if has && i != idx {
		log.Println(n.Debug(v))
		n.doKeyAt(v, idx, func(x []byte) error {
			k := n.key(idx)
			if v != nil {
				y, e := v.UnsafeGet(*slice.AsUint64(&k))
				log.Println(e)
				log.Println("key", x, y)
			} else {
				log.Println("key", x, "v was nil")
			}
			return nil
		})
		n.doKeyAt(v, i, func(x []byte) error {
			log.Println("replacing", x)
			return nil
		})
		return errors.Errorf("internal already had key %v, at %v, was going to put it at %v, replacing %v", key, idx, i, n.key(i))
	}
	oldk := make([]byte, len(n.key(i)))
	copy(oldk, n.key(i))
	flags := n.meta.flags
	if flags&consts.VARCHAR_KEYS != 0 {
		err := n.bigUpdateK(v, i, key)
		if err != nil {
			return err
		}
	} else {
		copy(n.key(i), key)
	}
	/*
		err = checkOrder(v, n)
		if err != nil {
			log.Println("replaced key", oldk)
			log.Println(n.Debug(v))
			return err
		}
	*/
	return nil
}

func (n *internal) delKP(v *Varchar, key []byte) error {
	i, has, err := find(v, n, key)
	if err != nil {
		return err
	}
	if !has {
		return errors.Errorf("key was not in the internal node")
	} else if i < 0 {
		return errors.Errorf("find returned a negative int")
	} else if i >= int(n.meta.keyCount) {
		return errors.Errorf("find returned a int > than len(keys)")
	}
	return n.delItemAt(v, i)
}

func (l *List) Pop() (item []byte, err error) {
	if l.count == 0 {
		return nil, errors.Errorf("Cannot pop an empty list")
	}
	var a uint64
	err = l.lastBlk(func(idx *idxBlk) (err error) {
		a, err = idx.Pop()
		return err
	})
	if err != nil {
		return nil, err
	}
	err = l.varchar.Do(a, func(data []byte) error {
		item = make([]byte, len(data))
		copy(item, data)
		return nil
	})
	if err != nil {
		return nil, err
	}
	err = l.varchar.Free(a)
	if err != nil {
		return nil, err
	}
	err = l.doCtrl(l.a, func(ctrl *ctrlBlk) error {
		ctrl.count--
		l.count = ctrl.count
		return nil
	})
	if err != nil {
		return nil, err
	}
	return item, nil
}

func (a *internal) balance(v *Varchar, b *internal) error {
	if b.meta.keyCount != 0 {
		return errors.Errorf("b was not empty")
	}
	m, err := a.balancePoint(v)
	if err != nil {
		return err
	}
	var lim int = int(a.meta.keyCount) - m
	for i := 0; i < lim; i++ {
		j := m + i
		copy(b.key(i), a.key(j))
		fmap.MemClr(a.key(j))
		*b.ptr(i) = *a.ptr(j)
		*a.ptr(j) = 0
	}
	b.meta.keyCount = a.meta.keyCount - uint16(m)
	a.meta.keyCount = uint16(m)
	/*
		err = checkOrder(v, a)
		if err != nil {
			log.Println("balance point", m)
			log.Println(a)
			return err
		}
		err = checkOrder(v, b)
		if err != nil {
			log.Println("balance point", m)
			log.Println(b)
			return err
		}
	*/
	return nil
}

func (l *List) Set(i uint64, item []byte) (err error) {
	if i >= l.count {
		return errors.Errorf("index out of range")
	}
	var old_a uint64
	err = l.blk(i, func(idx *idxBlk) (err error) {
		old_a, err = idx.Get(uint16(i % itemsPerIdx))
		return err
	})
	if err != nil {
		return err
	}
	err = l.varchar.Free(old_a)
	if err != nil {
		return err
	}
	a, err := l.varchar.Alloc(len(item))
	if err != nil {
		return err
	}
	err = l.varchar.Do(a, func(data []byte) error {
		copy(data, item)
		return nil
	})
	if err != nil {
		return err
	}
	return l.blk(i, func(idx *idxBlk) (err error) {
		err = idx.Set(uint16(i%itemsPerIdx), a)
		if err != nil {
			return err
		}
		return
	})
}

func (v *Varchar) listRemove(node uint64, doNode nodeDoer) error {
	if node == 0 {
		return errors.Errorf("0 offset for node (the removed node)")
	}
	return doNode(node, func(n *listNode) (err error) {
		if n.prev != 0 {
			err = doNode(n.prev, func(pn *listNode) error {
				pn.next = n.next
				return nil
			})
			if err != nil {
				return nil
			}
		}
		if n.next != 0 {
			err = doNode(n.next, func(nn *listNode) error {
				nn.prev = n.prev
				return nil
			})
			if err != nil {
				return nil
			}
		}
		n.prev = 0
		n.next = 0
		return nil
	})
}

func (v *Varchar) listInsert(node, prev, next uint64, doNode nodeDoer) error {
	if node == 0 {
		return errors.Errorf("0 offset for node (the inserted node)")
	}
	return doNode(node, func(n *listNode) error {
		if prev == 0 && next == 0 {
			n.prev = 0
			n.next = 0
			return nil
		} else if next == 0 {
			return doNode(prev, func(pn *listNode) error {
				n.next = 0
				n.prev = prev
				pn.next = node
				return nil
			})
		} else if prev == 0 {
			return doNode(next, func(nn *listNode) error {
				n.next = next
				n.prev = 0
				nn.prev = node
				return nil
			})
		}
		return doNode(prev, func(pn *listNode) error {
			return doNode(next, func(nn *listNode) error {
				n.next = next
				n.prev = prev
				pn.next = node
				nn.prev = node
				return nil
			})
		})
	})
}

// Get the bytes at the offset and block count. You probably want to use
// Do instead. You must call Release() on the bytes when done.
func (self *BlockFile) Get(offset, blocks uint64) ([]byte, error) {
	if !self.opened {
		return nil, errors.Errorf("File is not open")
	}
	length := blocks * uint64(self.blksize)
	if (offset + length) > uint64(self.size) {
		return nil, errors.Errorf("Get outside of the file, (%d) %d + %d > %d", offset+length, offset, length, self.size)
	}
	self.outstanding += 1
	slice := &slice.Slice{
		Array: unsafe.Pointer(uintptr(self.mmap) + uintptr(offset)),
		Len:   int(length),
		Cap:   int(length),
	}
	return *slice.AsBytes(), nil
}

func (v *Varchar) UnsafeGet(a uint64) (bytes []byte, err error) {
	rbytes, err := v.unsafeGet(a)
	if err != nil {
		return nil, err
	}
	m := asRunMeta(rbytes)
	fullLength := v.allocAmt(int(m.length))
	blks := uint64(v.blksNeeded(fullLength))
	offset, start, _ := v.startOffsetBlks(a)
	for offset+uint64(fullLength) >= blks*uint64(v.bf.BlockSize()) {
		blks++
	}
	size, err := v.bf.Size()
	if err != nil {
		return nil, err
	}
	for start+blks*uint64(v.bf.BlockSize()) > uint64(size) {
		blks--
	}
	allBytes, err := v.bf.Get(start, blks)
	if err != nil {
		return nil, err
	}
	err = v.bf.Release(allBytes)
	if err != nil {
		return nil, err
	}
	bytes = allBytes[offset:]
	flags := consts.AsFlag(bytes)
	if flags&consts.VARCHAR_RUN == 0 {
		return nil, errors.Errorf("bad address, was not a run block")
	}
	r := asRun(bytes)
	return r.bytes[:r.meta.length], nil
}

// Interact with the contents of the varchar. The bytes passed into the
// callback are UNSAFE. You could cause a segmentation fault if you
// simply copy the *slice* out of the function. You need to copy the
// data instead.
//
// The right way:
//
// 	var myBytes []byte
// 	err = v.Do(a, func(bytes []byte) error {
// 		myBytes = make([]byte, len(bytes))
// 		copy(myBytes, bytes)
// 		return nil
// 	})
// 	if err != nil {
// 		log.Fatal(err)
// 	}
//
// you can of course interact with the bytes in the callback in any way
// you want as long as no pointers escape. You can even change the
// values of the bytes (and these changes will be persisted). However,
// you cannot change the length of the varchar.
func (v *Varchar) Do(a uint64, do func([]byte) error) (err error) {
	return v.doRun(a, func(m *varRunMeta) error {
		fullLength := v.allocAmt(int(m.length))
		blks := uint64(v.blksNeeded(fullLength))
		offset, start, _ := v.startOffsetBlks(a)
		for offset+uint64(fullLength) >= blks*uint64(v.bf.BlockSize()) {
			blks++
		}
		size, err := v.bf.Size()
		if err != nil {
			return err
		}
		for start+blks*uint64(v.bf.BlockSize()) > uint64(size) {
			blks--
		}
		return v.bf.Do(start, blks, func(bytes []byte) error {
			bytes = bytes[offset:]
			flags := consts.AsFlag(bytes)
			if flags&consts.VARCHAR_RUN == 0 {
				return errors.Errorf("bad address, was not a run block")
			}
			r := asRun(bytes)
			return do(r.bytes[:r.meta.length])
		})
	})
}

// Open a varchar structure in the given blockfile with the given offset
// as the control block. This function will confirm that the control
// block is indeed a properly formated control block.
func OpenVarchar(bf *fmap.BlockFile, a uint64) (v *Varchar, err error) {
	v = &Varchar{bf: bf, a: a, blkSize: bf.BlockSize()}
	var ptOff uint64
	var szOff uint64
	err = v.bf.Do(v.a, 1, func(bytes []byte) error {
		ctrl := asCtrl(bytes)
		if ctrl.flags&consts.VARCHAR_CTRL == 0 {
			return errors.Errorf("Expected a Varchar control block")
		}
		ptOff = ctrl.posTree
		szOff = ctrl.sizeTree
		return nil
	})
	if err != nil {
		return nil, err
	}
	v.posTree, err = OpenAt(bf, ptOff)
	if err != nil {
		return nil, err
	}
	v.sizeTree, err = OpenAt(bf, szOff)
	if err != nil {
		return nil, err
	}
	return v, nil
}

func (self *BpTree) delListNode(node uint64) (err error) {
	if node == 0 {
		return errors.Errorf("0 offset for n")
	}
	return self.doLeaf(node, func(n *leaf) (err error) {
		if n.meta.prev != 0 {
			err = self.doLeaf(n.meta.prev, func(pn *leaf) (err error) {
				pn.meta.next = n.meta.next
				return nil
			})
			if err != nil {
				return err
			}
		}
		if n.meta.next != 0 {
			err = self.doLeaf(n.meta.next, func(nn *leaf) (err error) {
				nn.meta.prev = n.meta.prev
				return nil
			})
			if err != nil {
				return err
			}
		}
		n.meta.prev = 0
		n.meta.next = 0
		return nil
	})
}

// Allocate 1 block and return its offset.
func (self *BlockFile) Allocate() (offset uint64, err error) {
	if !self.opened {
		return 0, errors.Errorf("File is not open")
	}
	var resize bool = false
	err = self.ctrl(func(ctrl *ctrlblk) error {
		var err error
		if ctrl.meta.free_len > 0 {
			offset, err = self.pop_free()
		} else {
			resize = true
		}
		return err
	})
	if err != nil {
		return 0, err
	}
	if resize {
		offset, err = self.allocOne()
		if err != nil {
			return 0, err
		}
	}
	return self.zero(offset, 1)
}

func (self *BpTree) pureRun(start uint64) ([]uint64, error) {
	/* this algorithm was pretty tricky to port do to the "interesting"
	 * memory management scheme that I am employing (everything inside
	 * of "do" methods). Basically, the problem was it was mutating
	 * variables which I can not mutate because they are stuck inside of
	 * the do methods. I had to find a way to hoist just the information
	 * I needed.
	 */
	var key []byte
	err := self.doLeaf(start, func(n *leaf) error {
		if n.meta.keyCount < 0 {
			return errors.Errorf("block was empty")
		}
		return n.doKeyAt(self.varchar, 0, func(k []byte) error {
			key = make([]byte, len(k))
			copy(key, k)
			return nil
		})
	})
	if err != nil {
		return nil, err
	}
	getNext := func(a uint64) (next uint64, err error) {
		err = self.doLeaf(a, func(n *leaf) error {
			next = n.meta.next
			return nil
		})
		return next, err
	}
	isValid := func(a uint64) (valid bool, err error) {
		if a == 0 {
			return false, nil
		}
		err = self.doLeaf(a, func(n *leaf) error {
			return n.doKeyAt(self.varchar, 0, func(k []byte) error {
				valid = bytes.Equal(key, k)
				return nil
			})
		})
		return valid, err
	}
	cur := start
	valid, err := isValid(cur)
	if err != nil {
		return nil, err
	}
	run := make([]uint64, 0, 10)
	for valid {
		run = append(run, cur)
		cur, err = getNext(cur)
		if err != nil {
			return nil, err
		}
		valid, err = isValid(cur)
		if err != nil {
			return nil, err
		}
	}
	return run, nil
}