From 2bc8ca0ca2fefcfb63a37723d7a9bbb9ae76ceb1 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Zbigniew=20J=C4=99drzejewski-Szmek?= Date: Wed, 5 Jun 2013 00:56:03 -0400 Subject: [PATCH] journal: loop less in MATCH_AND_TERM conditionals MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit AND term usually don't have many subterms (4 seems to be the maximum sensible number, e.g. _BOOT_ID && _SYSTEMD_UNIT && _PID && MESSAGE_ID). Nevertheless, the cost of checking each subterm can be relatively high, especially when the nested terms are compound, and it makes sense to minimize the number of checks. Instead of looping to the end and then again over the whole list once again after at least one term changed the offset, start the loop at the term which caused the change. This way ½ terms in the AND match are not checked unnecessarily again. --- src/journal/sd-journal.c | 41 +++++++++++++++++----------------------- src/shared/list.h | 7 +++++++ 2 files changed, 24 insertions(+), 24 deletions(-) diff --git a/src/journal/sd-journal.c b/src/journal/sd-journal.c index 46511df6b..8b9a589cd 100644 --- a/src/journal/sd-journal.c +++ b/src/journal/sd-journal.c @@ -593,42 +593,35 @@ static int next_for_match( } } else if (m->type == MATCH_AND_TERM) { - Match *i; - bool continue_looking; + Match *i, *last_moved; /* Always jump to the next matching entry and repeat - * this until we fine and offset that matches for all + * this until we find an offset that matches for all * matches. */ if (!m->matches) return 0; - np = 0; - do { - continue_looking = false; + r = next_for_match(j, m->matches, f, after_offset, direction, NULL, &np); + if (r <= 0) + return r; - LIST_FOREACH(matches, i, m->matches) { - uint64_t cp, limit; + assert(direction == DIRECTION_DOWN ? np >= after_offset : np <= after_offset); + last_moved = m->matches; - if (np == 0) - limit = after_offset; - else if (direction == DIRECTION_DOWN) - limit = MAX(np, after_offset); - else - limit = MIN(np, after_offset); + LIST_LOOP_BUT_ONE(matches, i, m->matches, last_moved) { + uint64_t cp; - r = next_for_match(j, i, f, limit, direction, NULL, &cp); - if (r <= 0) - return r; + r = next_for_match(j, i, f, np, direction, NULL, &cp); + if (r <= 0) + return r; - if ((direction == DIRECTION_DOWN ? cp >= after_offset : cp <= after_offset) && - (np == 0 || (direction == DIRECTION_DOWN ? cp > np : cp < np))) { - np = cp; - continue_looking = true; - } + assert(direction == DIRECTION_DOWN ? cp >= np : cp <= np); + if (direction == DIRECTION_DOWN ? cp > np : cp < np) { + np = cp; + last_moved = i; } - - } while (continue_looking); + } } if (np == 0) diff --git a/src/shared/list.h b/src/shared/list.h index 47f275a01..96d623797 100644 --- a/src/shared/list.h +++ b/src/shared/list.h @@ -123,3 +123,10 @@ #define LIST_FOREACH_AFTER(name,i,p) \ for ((i) = (p)->name##_next; (i); (i) = (i)->name##_next) + +/* Loop starting from p->next until p->prev. + p can be adjusted meanwhile. */ +#define LIST_LOOP_BUT_ONE(name,i,head,p) \ + for ((i) = (p)->name##_next ? (p)->name##_next : (head); \ + (i) != (p); \ + (i) = (i)->name##_next ? (i)->name##_next : (head)) -- 2.30.2