Refactor `update` to reduce wasted lookups

By moving most of the `update` logic into `add`, we can reduce all of the duplicated work in the existence check loop.