+
+ll_iter_t *ll_iter_begin (list_t *ll, map_key_t key) {
+ ll_iter_t *iter = (ll_iter_t *)nbd_malloc(sizeof(ll_iter_t));
+ if (key != DOES_NOT_EXIST) {
+ find_pred(&iter->pred, NULL, ll, key, FALSE);
+ } else {
+ iter->pred = ll->head;
+ }
+#ifdef LIST_USE_HAZARD_POINTER
+ haz_register_dynamic((void **)&iter->pred);
+#endif
+ return iter;
+}
+
+map_val_t ll_iter_next (ll_iter_t *iter, map_key_t *key_ptr) {
+ assert(iter);
+ if (iter->pred == NULL)
+ return DOES_NOT_EXIST;
+
+ // advance iterator to next item; skip items that have been removed
+ markable_t item;
+#ifdef LIST_USE_HAZARD_POINTER
+ haz_t *hp0 = haz_get_static(0);
+#endif
+ do {
+#ifndef LIST_USE_HAZARD_POINTER
+ item = iter->pred->next;
+#else //LIST_USE_HAZARD_POINTER
+ do {
+ item = iter->pred->next;
+ haz_set(hp0, STRIP_MARK(item));
+ } while (item != ((volatile node_t *)iter->pred)->next);
+#endif//LIST_USE_HAZARD_POINTER
+ iter->pred = STRIP_MARK(item);
+ if (iter->pred == NULL)
+ return DOES_NOT_EXIST;
+ } while (HAS_MARK(item));
+
+ if (key_ptr != NULL) {
+ *key_ptr = GET_NODE(item)->key;
+ }
+ return GET_NODE(item)->val;
+}
+
+void ll_iter_free (ll_iter_t *iter) {
+#ifdef LIST_USE_HAZARD_POINTER
+ haz_unregister_dynamic((void **)&iter->pred);
+#endif
+ nbd_free(iter);
+}