rfind-if: optimized rewrite and hash support.

* lib.c (rfind_if): Function rewritten to use the seq_info
sequence classification mechanism, for much better
performance on vector-like objects. Also, supports hash
tables just like find_if.

* txr.1: Documentation updated regarding hash support
of rfind-if.

2 files changed, 60 insertions, 10 deletions

diff --git a/lib.c b/lib.c
index 088281f8..3575a957 100644
--- a/lib.c
+++ b/lib.c
@@ -8651,20 +8651,58 @@ val find_if(val pred, val seq, val key)
   return nil;
 }
 
-val rfind_if(val pred, val list, val key)
+val rfind_if(val predi, val seq, val key)
 {
+  val keyfun = default_arg(key, identity_f);
+  seq_info_t si = seq_info(seq);
   val found = nil;
-  key = default_arg(key, identity_f);
-  list = nullify(list);
 
-  gc_hint(list);
+  switch (si.kind) {
+  case SEQ_NIL:
+    break;
+  case SEQ_HASHLIKE:
+    {
+      val hiter = hash_begin(si.obj);
+      val cell;
 
-  for (; list; list = cdr(list)) {
-    val item = car(list);
-    val subj = funcall1(key, item);
+      while ((cell = hash_next(hiter))) {
+        val key = funcall1(keyfun, cell);
+        if (funcall1(predi, key))
+          found = cell;
+      }
 
-    if (funcall1(pred, subj))
-      found = item;
+      break;
+    }
+  case SEQ_LISTLIKE:
+    {
+      gc_hint(seq);
+
+      for (seq = z(si.obj); seq; seq = cdr(seq)) {
+        val elt = car(seq);
+        val key = funcall1(keyfun, elt);
+        if (funcall1(predi, key))
+          found = elt;
+      }
+
+      break;
+    }
+  case SEQ_VECLIKE:
+    {
+      val vec = si.obj;
+      val i = pred(length(vec));
+
+      for (; plusp(i); i = pred(i)) {
+        val elt = ref(vec, i);
+        val key = funcall1(keyfun, elt);
+        if (funcall1(predi, key))
+          return elt;
+      }
+
+      break;
+    }
+  case SEQ_NOTSEQ:
+  default:
+    uw_throwf(error_s, lit("rfind-if: unsupported object ~s"), seq, nao);
   }
 
   return found;
diff --git a/txr.1 b/txr.1
index d7f3ad91..26bc2051 100644
--- a/txr.1
+++ b/txr.1
@@ -27491,7 +27491,7 @@ then these cells are taken as their keys.
 .coNP Functions @ rfind and @ rfind-if
 .synb
 .mets (rfind < key < sequence >> [ testfun <> [ keyfun ]])
-.mets (rfind-if < predfun < sequence <> [ keyfun ])
+.mets (rfind-if < predfun >> { sequence | << hash }  <> [ keyfun ])
 .syne
 .desc
 The
@@ -27509,6 +27509,18 @@ in
 they return the right-most element rather than
 the leftmost.
 
+In the case of
+.code rfind-if
+when a
+.meta hash
+is specified instead of a
+.metn sequence ,
+the function searches through the hash entries in the same order as
+.codn find-if ,
+but finds the last match rather than the first.
+Note: hashes are inherently not ordered; the relative order of items in
+a hash table can change when other items are inserted or deleted.
+
 .coNP Functions @ find-max and @ find-min
 .synb
 .mets (find-max >> { sequence | << hash } >> [ testfun <> [ keyfun ]])