summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorKaz Kylheku <kaz@kylheku.com>2017-11-15 06:19:49 -0800
committerKaz Kylheku <kaz@kylheku.com>2017-11-15 06:19:49 -0800
commit8230a637a32ce0c88ba1c51aeb6c2d5edcece109 (patch)
treef8580dade862468172873b42cd1aaf82b3676478
parent6f7c75ed060f3c824740cf0a471be4a235f2fe51 (diff)
downloadtxr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.tar.gz
txr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.tar.bz2
txr-8230a637a32ce0c88ba1c51aeb6c2d5edcece109.zip
find-if: optimized rewrite and hash support.
* lib.c (find_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_max. * txr.1: Documentation updated regarding hash support of find-if.
-rw-r--r--lib.c57
-rw-r--r--txr.116
2 files changed, 63 insertions, 10 deletions
diff --git a/lib.c b/lib.c
index ab6e3beb..088281f8 100644
--- a/lib.c
+++ b/lib.c
@@ -8594,19 +8594,58 @@ val find_min(val seq, val testfun, val keyfun)
return find_max(seq, default_arg(testfun, less_f), keyfun);
}
-val find_if(val pred, val list, val key)
+val find_if(val pred, val seq, val key)
{
- key = default_arg(key, identity_f);
- list = nullify(list);
+ val keyfun = default_arg(key, identity_f);
+ seq_info_t si = seq_info(seq);
- 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(pred, key))
+ return cell;
+ }
- if (funcall1(pred, subj))
- return 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(pred, key))
+ return elt;
+ }
+
+ break;
+ }
+ case SEQ_VECLIKE:
+ {
+ val vec = si.obj;
+ val len = length(vec);
+ val i;
+
+ for (i = zero; lt(i, len); i = succ(i)) {
+ val elt = ref(vec, i);
+ val key = funcall1(keyfun, elt);
+ if (funcall1(pred, key))
+ return elt;
+ }
+
+ break;
+ }
+ case SEQ_NOTSEQ:
+ default:
+ uw_throwf(error_s, lit("find-if: unsupported object ~s"), seq, nao);
}
return nil;
diff --git a/txr.1 b/txr.1
index ab75e874..d7f3ad91 100644
--- a/txr.1
+++ b/txr.1
@@ -27419,7 +27419,7 @@ is returned.
.coNP Functions @ find and @ find-if
.synb
.mets (find < key < sequence >> [ testfun <> [ keyfun ]])
-.mets (find-if < predfun < sequence <> [ keyfun ])
+.mets (find-if < predfun >> { sequence | << hash } <> [ keyfun ])
.syne
.desc
The
@@ -27474,6 +27474,20 @@ element is found,
.code nil
is returned.
+In the case of
+.codn find-if ,
+a hash table may be specified instead of a sequence.
+The
+.meta hash
+is treated as if it were a sequence of hash key and hash
+value pairs represented as cons cells, the
+.code car
+slots of which are the hash keys, and the
+.code cdr
+of which are the hash values. If the caller doesn't specify a
+.meta keyfun
+then these cells are taken as their keys.
+
.coNP Functions @ rfind and @ rfind-if
.synb
.mets (rfind < key < sequence >> [ testfun <> [ keyfun ]])