+ return NULL;
+
+ m->type = t;
+
+ if (p) {
+ m->parent = p;
+ LIST_PREPEND(Match, matches, p->matches, m);
+ }
+
+ return m;
+}
+
+static void match_free(Match *m) {
+ assert(m);
+
+ while (m->matches)
+ match_free(m->matches);
+
+ if (m->parent)
+ LIST_REMOVE(Match, matches, m->parent->matches, m);
+
+ free(m->data);
+ free(m);
+}
+
+static void match_free_if_empty(Match *m) {
+ assert(m);
+
+ if (m->matches)
+ return;
+
+ match_free(m);
+}
+
+_public_ int sd_journal_add_match(sd_journal *j, const void *data, size_t size) {
+ Match *l2, *l3, *add_here = NULL, *m;
+ le64_t le_hash;
+
+ if (!j)
+ return -EINVAL;
+
+ if (!data)
+ return -EINVAL;
+
+ if (size == 0)
+ size = strlen(data);
+
+ if (!match_is_valid(data, size))
+ return -EINVAL;
+
+ /* level 0: OR term
+ * level 1: AND terms
+ * level 2: OR terms
+ * level 3: concrete matches */
+
+ if (!j->level0) {
+ j->level0 = match_new(NULL, MATCH_OR_TERM);
+ if (!j->level0)
+ return -ENOMEM;
+ }
+
+ if (!j->level1) {
+ j->level1 = match_new(j->level0, MATCH_AND_TERM);
+ if (!j->level1)
+ return -ENOMEM;
+ }
+
+ assert(j->level0->type == MATCH_OR_TERM);
+ assert(j->level1->type == MATCH_AND_TERM);
+
+ le_hash = htole64(hash64(data, size));
+
+ LIST_FOREACH(matches, l2, j->level1->matches) {
+ assert(l2->type == MATCH_OR_TERM);
+
+ LIST_FOREACH(matches, l3, l2->matches) {
+ assert(l3->type == MATCH_DISCRETE);
+
+ /* Exactly the same match already? Then ignore
+ * this addition */
+ if (l3->le_hash == le_hash &&
+ l3->size == size &&
+ memcmp(l3->data, data, size) == 0)
+ return 0;
+
+ /* Same field? Then let's add this to this OR term */
+ if (same_field(data, size, l3->data, l3->size)) {
+ add_here = l2;
+ break;
+ }
+ }
+
+ if (add_here)
+ break;
+ }
+
+ if (!add_here) {
+ add_here = match_new(j->level1, MATCH_OR_TERM);
+ if (!add_here)
+ goto fail;
+ }
+
+ m = match_new(add_here, MATCH_DISCRETE);
+ if (!m)
+ goto fail;
+
+ m->le_hash = le_hash;
+ m->size = size;
+ m->data = memdup(data, size);
+ if (!m->data)
+ goto fail;
+
+ detach_location(j);
+
+ return 0;
+
+fail:
+ if (add_here)
+ match_free_if_empty(add_here);
+
+ if (j->level1)
+ match_free_if_empty(j->level1);
+
+ if (j->level0)
+ match_free_if_empty(j->level0);
+
+ return -ENOMEM;
+}
+
+_public_ int sd_journal_add_disjunction(sd_journal *j) {
+ Match *m;
+
+ assert(j);
+
+ if (!j->level0)
+ return 0;
+
+ if (!j->level1)
+ return 0;
+
+ if (!j->level1->matches)
+ return 0;
+
+ m = match_new(j->level0, MATCH_AND_TERM);
+ if (!m)
+ return -ENOMEM;
+
+ j->level1 = m;
+ return 0;
+}
+
+static char *match_make_string(Match *m) {
+ char *p, *r;
+ Match *i;
+ bool enclose = false;
+
+ if (!m)
+ return strdup("");
+
+ if (m->type == MATCH_DISCRETE)
+ return strndup(m->data, m->size);
+
+ p = NULL;
+ LIST_FOREACH(matches, i, m->matches) {
+ char *t, *k;
+
+ t = match_make_string(i);
+ if (!t) {
+ free(p);
+ return NULL;
+ }
+
+ if (p) {
+ k = strjoin(p, m->type == MATCH_OR_TERM ? " OR " : " AND ", t, NULL);
+ free(p);
+ free(t);
+
+ if (!k)
+ return NULL;
+
+ p = k;
+
+ enclose = true;
+ } else {
+ free(p);
+ p = t;
+ }
+ }
+
+ if (enclose) {
+ r = strjoin("(", p, ")", NULL);
+ free(p);
+ return r;
+ }
+
+ return p;
+}
+
+char *journal_make_match_string(sd_journal *j) {
+ assert(j);
+
+ return match_make_string(j->level0);
+}
+
+_public_ void sd_journal_flush_matches(sd_journal *j) {
+
+ if (!j)
+ return;
+
+ if (j->level0)
+ match_free(j->level0);
+
+ j->level0 = j->level1 = NULL;
+
+ detach_location(j);
+}
+
+static int compare_entry_order(JournalFile *af, Object *_ao,
+ JournalFile *bf, uint64_t bp) {
+
+ uint64_t a, b;
+ Object *ao, *bo;
+ int r;
+
+ assert(af);
+ assert(bf);
+ assert(_ao);
+
+ /* The mmap cache might invalidate the object from the first
+ * file if we look at the one from the second file. Hence
+ * temporarily copy the header of the first one, and look at
+ * that only. */
+ ao = alloca(offsetof(EntryObject, items));
+ memcpy(ao, _ao, offsetof(EntryObject, items));
+
+ r = journal_file_move_to_object(bf, OBJECT_ENTRY, bp, &bo);
+ if (r < 0)
+ return strcmp(af->path, bf->path);
+
+ /* We operate on two different files here, hence we can access
+ * two objects at the same time, which we normally can't.
+ *
+ * If contents and timestamps match, these entries are
+ * identical, even if the seqnum does not match */
+
+ if (sd_id128_equal(ao->entry.boot_id, bo->entry.boot_id) &&
+ ao->entry.monotonic == bo->entry.monotonic &&
+ ao->entry.realtime == bo->entry.realtime &&
+ ao->entry.xor_hash == bo->entry.xor_hash)
+ return 0;
+
+ if (sd_id128_equal(af->header->seqnum_id, bf->header->seqnum_id)) {
+
+ /* If this is from the same seqnum source, compare
+ * seqnums */
+ a = le64toh(ao->entry.seqnum);
+ b = le64toh(bo->entry.seqnum);
+
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+
+ /* Wow! This is weird, different data but the same
+ * seqnums? Something is borked, but let's make the
+ * best of it and compare by time. */
+ }
+
+ if (sd_id128_equal(ao->entry.boot_id, bo->entry.boot_id)) {
+
+ /* If the boot id matches compare monotonic time */
+ a = le64toh(ao->entry.monotonic);
+ b = le64toh(bo->entry.monotonic);
+
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+ }
+
+ /* Otherwise compare UTC time */
+ a = le64toh(ao->entry.realtime);
+ b = le64toh(bo->entry.realtime);
+
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+
+ /* Finally, compare by contents */
+ a = le64toh(ao->entry.xor_hash);
+ b = le64toh(bo->entry.xor_hash);
+
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+
+ return 0;
+}
+
+static int compare_with_location(JournalFile *af, Object *ao, Location *l) {
+ uint64_t a;
+
+ assert(af);
+ assert(ao);
+ assert(l);
+ assert(l->type == LOCATION_DISCRETE);
+
+ if (l->monotonic_set &&
+ sd_id128_equal(ao->entry.boot_id, l->boot_id) &&
+ l->realtime_set &&
+ le64toh(ao->entry.realtime) == l->realtime &&
+ l->xor_hash_set &&
+ le64toh(ao->entry.xor_hash) == l->xor_hash)
+ return 0;
+
+ if (l->seqnum_set &&
+ sd_id128_equal(af->header->seqnum_id, l->seqnum_id)) {
+
+ a = le64toh(ao->entry.seqnum);
+
+ if (a < l->seqnum)
+ return -1;
+ if (a > l->seqnum)
+ return 1;
+ }
+
+ if (l->monotonic_set &&
+ sd_id128_equal(ao->entry.boot_id, l->boot_id)) {
+
+ a = le64toh(ao->entry.monotonic);
+
+ if (a < l->monotonic)
+ return -1;
+ if (a > l->monotonic)
+ return 1;
+ }
+
+ if (l->realtime_set) {
+
+ a = le64toh(ao->entry.realtime);
+
+ if (a < l->realtime)
+ return -1;
+ if (a > l->realtime)
+ return 1;
+ }
+
+ if (l->xor_hash_set) {
+ a = le64toh(ao->entry.xor_hash);
+
+ if (a < l->xor_hash)
+ return -1;
+ if (a > l->xor_hash)
+ return 1;
+ }
+
+ return 0;
+}
+
+static int next_for_match(
+ sd_journal *j,
+ Match *m,
+ JournalFile *f,
+ uint64_t after_offset,
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset) {
+
+ int r;
+ uint64_t np = 0;
+ Object *n;
+
+ assert(j);
+ assert(m);
+ assert(f);
+
+ if (m->type == MATCH_DISCRETE) {
+ uint64_t dp;
+
+ r = journal_file_find_data_object_with_hash(f, m->data, m->size, le64toh(m->le_hash), NULL, &dp);
+ if (r <= 0)
+ return r;
+
+ return journal_file_move_to_entry_by_offset_for_data(f, dp, after_offset, direction, ret, offset);
+
+ } else if (m->type == MATCH_OR_TERM) {
+ Match *i;
+
+ /* Find the earliest match beyond after_offset */
+
+ LIST_FOREACH(matches, i, m->matches) {
+ uint64_t cp;
+
+ r = next_for_match(j, i, f, after_offset, direction, NULL, &cp);
+ if (r < 0)
+ return r;
+ else if (r > 0) {
+ if (np == 0 || (direction == DIRECTION_DOWN ? np > cp : np < cp))
+ np = cp;
+ }
+ }
+
+ } else if (m->type == MATCH_AND_TERM) {
+ Match *i;
+ bool continue_looking;
+
+ /* Always jump to the next matching entry and repeat
+ * this until we fine and offset that matches for all
+ * matches. */
+
+ if (!m->matches)
+ return 0;
+
+ np = 0;
+ do {
+ continue_looking = false;
+
+ LIST_FOREACH(matches, i, m->matches) {
+ uint64_t cp, limit;
+
+ if (np == 0)
+ limit = after_offset;
+ else if (direction == DIRECTION_DOWN)
+ limit = MAX(np, after_offset);
+ else
+ limit = MIN(np, after_offset);
+
+ r = next_for_match(j, i, f, limit, 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 : np < cp))) {
+ np = cp;
+ continue_looking = true;
+ }
+ }
+
+ } while (continue_looking);
+ }
+
+ if (np == 0)
+ return 0;
+
+ r = journal_file_move_to_object(f, OBJECT_ENTRY, np, &n);
+ if (r < 0)
+ return r;
+
+ if (ret)
+ *ret = n;
+ if (offset)
+ *offset = np;
+
+ return 1;
+}
+
+static int find_location_for_match(
+ sd_journal *j,
+ Match *m,
+ JournalFile *f,
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset) {
+
+ int r;
+
+ assert(j);
+ assert(m);
+ assert(f);
+
+ if (m->type == MATCH_DISCRETE) {
+ uint64_t dp;
+
+ r = journal_file_find_data_object_with_hash(f, m->data, m->size, le64toh(m->le_hash), NULL, &dp);
+ if (r <= 0)
+ return r;
+
+ /* FIXME: missing: find by monotonic */
+
+ if (j->current_location.type == LOCATION_HEAD)
+ return journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_DOWN, ret, offset);
+ if (j->current_location.type == LOCATION_TAIL)
+ return journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_UP, ret, offset);
+ if (j->current_location.seqnum_set && sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
+ return journal_file_move_to_entry_by_seqnum_for_data(f, dp, j->current_location.seqnum, direction, ret, offset);
+ if (j->current_location.monotonic_set) {
+ r = journal_file_move_to_entry_by_monotonic_for_data(f, dp, j->current_location.boot_id, j->current_location.monotonic, direction, ret, offset);
+ if (r != -ENOENT)
+ return r;
+ }
+ if (j->current_location.realtime_set)
+ return journal_file_move_to_entry_by_realtime_for_data(f, dp, j->current_location.realtime, direction, ret, offset);
+
+ return journal_file_next_entry_for_data(f, NULL, 0, dp, direction, ret, offset);
+
+ } else if (m->type == MATCH_OR_TERM) {
+ uint64_t np = 0;
+ Object *n;
+ Match *i;
+
+ /* Find the earliest match */
+
+ LIST_FOREACH(matches, i, m->matches) {
+ uint64_t cp;
+
+ r = find_location_for_match(j, i, f, direction, NULL, &cp);
+ if (r < 0)
+ return r;
+ else if (r > 0) {
+ if (np == 0 || (direction == DIRECTION_DOWN ? np > cp : np < cp))
+ np = cp;
+ }
+ }
+
+ if (np == 0)
+ return 0;
+
+ r = journal_file_move_to_object(f, OBJECT_ENTRY, np, &n);
+ if (r < 0)
+ return r;
+
+ if (ret)
+ *ret = n;
+ if (offset)
+ *offset = np;
+
+ return 1;
+
+ } else {
+ Match *i;
+ uint64_t np = 0;
+
+ assert(m->type == MATCH_AND_TERM);
+
+ /* First jump to the last match, and then find the
+ * next one where all matches match */
+
+ if (!m->matches)
+ return 0;
+
+ LIST_FOREACH(matches, i, m->matches) {
+ uint64_t cp;
+
+ r = find_location_for_match(j, i, f, direction, NULL, &cp);
+ if (r <= 0)
+ return r;
+
+ if (np == 0 || (direction == DIRECTION_DOWN ? np < cp : np > cp))
+ np = cp;
+ }
+
+ return next_for_match(j, m, f, np, direction, ret, offset);
+ }
+}
+
+static int find_location_with_matches(
+ sd_journal *j,
+ JournalFile *f,
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset) {
+
+ int r;
+
+ assert(j);
+ assert(f);
+ assert(ret);
+ assert(offset);
+
+ if (!j->level0) {
+ /* No matches is simple */
+
+ if (j->current_location.type == LOCATION_HEAD)
+ return journal_file_next_entry(f, NULL, 0, DIRECTION_DOWN, ret, offset);
+ if (j->current_location.type == LOCATION_TAIL)
+ return journal_file_next_entry(f, NULL, 0, DIRECTION_UP, ret, offset);
+ if (j->current_location.seqnum_set && sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
+ return journal_file_move_to_entry_by_seqnum(f, j->current_location.seqnum, direction, ret, offset);
+ if (j->current_location.monotonic_set) {
+ r = journal_file_move_to_entry_by_monotonic(f, j->current_location.boot_id, j->current_location.monotonic, direction, ret, offset);
+ if (r != -ENOENT)
+ return r;
+ }
+ if (j->current_location.realtime_set)
+ return journal_file_move_to_entry_by_realtime(f, j->current_location.realtime, direction, ret, offset);
+
+ return journal_file_next_entry(f, NULL, 0, direction, ret, offset);
+ } else
+ return find_location_for_match(j, j->level0, f, direction, ret, offset);
+}
+
+static int next_with_matches(
+ sd_journal *j,
+ JournalFile *f,
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset) {
+
+ Object *c;
+ uint64_t cp;
+
+ assert(j);
+ assert(f);
+ assert(ret);
+ assert(offset);
+
+ c = *ret;
+ cp = *offset;
+
+ /* No matches is easy. We simple advance the file
+ * pointer by one. */
+ if (!j->level0)
+ return journal_file_next_entry(f, c, cp, direction, ret, offset);
+
+ /* If we have a match then we look for the next matching entry
+ * with an offset at least one step larger */
+ return next_for_match(j, j->level0, f, direction == DIRECTION_DOWN ? cp+1 : cp-1, direction, ret, offset);
+}
+
+static int next_beyond_location(sd_journal *j, JournalFile *f, direction_t direction, Object **ret, uint64_t *offset) {
+ Object *c;
+ uint64_t cp;
+ int r;
+
+ assert(j);
+ assert(f);
+
+ if (f->current_offset > 0) {
+ cp = f->current_offset;
+
+ r = journal_file_move_to_object(f, OBJECT_ENTRY, cp, &c);
+ if (r < 0)
+ return r;
+
+ r = next_with_matches(j, f, direction, &c, &cp);
+ if (r <= 0)
+ return r;
+ } else {
+ r = find_location_with_matches(j, f, direction, &c, &cp);
+ if (r <= 0)
+ return r;
+ }
+
+ /* OK, we found the spot, now let's advance until to an entry
+ * that is actually different from what we were previously
+ * looking at. This is necessary to handle entries which exist
+ * in two (or more) journal files, and which shall all be
+ * suppressed but one. */
+
+ for (;;) {
+ bool found;
+
+ if (j->current_location.type == LOCATION_DISCRETE) {
+ int k;
+
+ k = compare_with_location(f, c, &j->current_location);
+ if (direction == DIRECTION_DOWN)
+ found = k > 0;
+ else
+ found = k < 0;
+ } else
+ found = true;
+
+ if (found) {
+ if (ret)
+ *ret = c;
+ if (offset)
+ *offset = cp;
+ return 1;
+ }
+
+ r = next_with_matches(j, f, direction, &c, &cp);
+ if (r <= 0)
+ return r;
+ }
+}
+
+static int real_journal_next(sd_journal *j, direction_t direction) {
+ JournalFile *f, *new_file = NULL;
+ uint64_t new_offset = 0;
+ Object *o;
+ uint64_t p;
+ Iterator i;
+ int r;
+
+ if (!j)
+ return -EINVAL;
+
+ HASHMAP_FOREACH(f, j->files, i) {
+ bool found;
+
+ r = next_beyond_location(j, f, direction, &o, &p);
+ if (r < 0) {
+ log_debug("Can't iterate through %s, ignoring: %s", f->path, strerror(-r));
+ continue;
+ } else if (r == 0)
+ continue;
+
+ if (!new_file)
+ found = true;
+ else {
+ int k;
+
+ k = compare_entry_order(f, o, new_file, new_offset);
+
+ if (direction == DIRECTION_DOWN)
+ found = k < 0;
+ else
+ found = k > 0;
+ }
+
+ if (found) {
+ new_file = f;
+ new_offset = p;
+ }
+ }
+
+ if (!new_file)
+ return 0;
+
+ r = journal_file_move_to_object(new_file, OBJECT_ENTRY, new_offset, &o);
+ if (r < 0)
+ return r;
+
+ set_location(j, new_file, o, new_offset);
+
+ return 1;
+}
+
+_public_ int sd_journal_next(sd_journal *j) {
+ return real_journal_next(j, DIRECTION_DOWN);
+}
+
+_public_ int sd_journal_previous(sd_journal *j) {
+ return real_journal_next(j, DIRECTION_UP);
+}
+
+static int real_journal_next_skip(sd_journal *j, direction_t direction, uint64_t skip) {
+ int c = 0, r;
+
+ if (!j)
+ return -EINVAL;
+
+ if (skip == 0) {
+ /* If this is not a discrete skip, then at least
+ * resolve the current location */
+ if (j->current_location.type != LOCATION_DISCRETE)
+ return real_journal_next(j, direction);
+
+ return 0;
+ }
+
+ do {
+ r = real_journal_next(j, direction);
+ if (r < 0)
+ return r;
+
+ if (r == 0)
+ return c;
+
+ skip--;
+ c++;
+ } while (skip > 0);
+
+ return c;
+}
+
+_public_ int sd_journal_next_skip(sd_journal *j, uint64_t skip) {
+ return real_journal_next_skip(j, DIRECTION_DOWN, skip);
+}
+
+_public_ int sd_journal_previous_skip(sd_journal *j, uint64_t skip) {
+ return real_journal_next_skip(j, DIRECTION_UP, skip);
+}
+
+_public_ int sd_journal_get_cursor(sd_journal *j, char **cursor) {
+ Object *o;
+ int r;
+ char bid[33], sid[33];
+
+ if (!j)
+ return -EINVAL;
+ if (!cursor)
+ return -EINVAL;
+
+ if (!j->current_file || j->current_file->current_offset <= 0)
+ return -EADDRNOTAVAIL;
+
+ r = journal_file_move_to_object(j->current_file, OBJECT_ENTRY, j->current_file->current_offset, &o);
+ if (r < 0)
+ return r;
+
+ sd_id128_to_string(j->current_file->header->seqnum_id, sid);
+ sd_id128_to_string(o->entry.boot_id, bid);
+
+ if (asprintf(cursor,
+ "s=%s;i=%llx;b=%s;m=%llx;t=%llx;x=%llx;p=%s",
+ sid, (unsigned long long) le64toh(o->entry.seqnum),
+ bid, (unsigned long long) le64toh(o->entry.monotonic),
+ (unsigned long long) le64toh(o->entry.realtime),
+ (unsigned long long) le64toh(o->entry.xor_hash),
+ path_get_file_name(j->current_file->path)) < 0)