+ return res != NULL || cur;
+}
+
+/*
+ * Merge the results for the expression tree rooted at e
+ * into the the result list htab.
+ */
+static struct ohash *
+manmerge(struct expr *e, struct ohash *htab)
+{
+ switch (e->type) {
+ case EXPR_TERM:
+ return manmerge_term(e, htab);
+ case EXPR_OR:
+ return manmerge_or(e->child, htab);
+ case EXPR_AND:
+ return manmerge_and(e->child, htab);
+ default:
+ abort();
+ }
+}
+
+static struct ohash *
+manmerge_term(struct expr *e, struct ohash *htab)
+{
+ struct dbm_res res, *rp;
+ uint64_t ib;
+ unsigned int slot;
+ int im;
+
+ if (htab == NULL) {
+ htab = mandoc_malloc(sizeof(*htab));
+ mandoc_ohash_init(htab, 4, offsetof(struct dbm_res, page));
+ }
+
+ for (im = 0, ib = 1; im < KEY_MAX; im++, ib <<= 1) {
+ if ((e->bits & ib) == 0)
+ continue;
+
+ switch (ib) {
+ case TYPE_arch:
+ dbm_page_byarch(&e->match);
+ break;
+ case TYPE_sec:
+ dbm_page_bysect(&e->match);
+ break;
+ case TYPE_Nm:
+ dbm_page_byname(&e->match);
+ break;
+ case TYPE_Nd:
+ dbm_page_bydesc(&e->match);
+ break;
+ default:
+ dbm_page_bymacro(im - 2, &e->match);
+ break;
+ }
+
+ /*
+ * When hashing for deduplication, use the unique
+ * page ID itself instead of a hash function;
+ * that is quite efficient.
+ */
+
+ for (;;) {
+ res = dbm_page_next();
+ if (res.page == -1)
+ break;
+ slot = ohash_lookup_memory(htab,
+ (char *)&res, sizeof(res.page), res.page);
+ if ((rp = ohash_find(htab, slot)) != NULL) {
+ rp->bits |= res.bits;
+ continue;
+ }
+ rp = mandoc_malloc(sizeof(*rp));
+ *rp = res;
+ ohash_insert(htab, slot, rp);
+ }
+ }
+ return htab;
+}
+
+static struct ohash *
+manmerge_or(struct expr *e, struct ohash *htab)
+{
+ while (e != NULL) {
+ htab = manmerge(e, htab);
+ e = e->next;
+ }
+ return htab;
+}
+
+static struct ohash *
+manmerge_and(struct expr *e, struct ohash *htab)
+{
+ struct ohash *hand, *h1, *h2;
+ struct dbm_res *res;
+ unsigned int slot1, slot2;
+
+ /* Evaluate the first term of the AND clause. */
+
+ hand = manmerge(e, NULL);
+
+ while ((e = e->next) != NULL) {
+
+ /* Evaluate the next term and prepare for ANDing. */
+
+ h2 = manmerge(e, NULL);
+ if (ohash_entries(h2) < ohash_entries(hand)) {
+ h1 = h2;
+ h2 = hand;
+ } else
+ h1 = hand;
+ hand = mandoc_malloc(sizeof(*hand));
+ mandoc_ohash_init(hand, 4, offsetof(struct dbm_res, page));
+
+ /* Keep all pages that are in both result sets. */
+
+ for (res = ohash_first(h1, &slot1); res != NULL;
+ res = ohash_next(h1, &slot1)) {
+ if (ohash_find(h2, ohash_lookup_memory(h2,
+ (char *)res, sizeof(res->page),
+ res->page)) == NULL)
+ free(res);
+ else
+ ohash_insert(hand, ohash_lookup_memory(hand,
+ (char *)res, sizeof(res->page),
+ res->page), res);
+ }
+
+ /* Discard the merged results. */
+
+ for (res = ohash_first(h2, &slot2); res != NULL;
+ res = ohash_next(h2, &slot2))
+ free(res);
+ ohash_delete(h2);
+ free(h2);
+ ohash_delete(h1);
+ free(h1);
+ }
+
+ /* Merge the result of the AND into htab. */
+
+ if (htab == NULL)
+ return hand;
+
+ for (res = ohash_first(hand, &slot1); res != NULL;
+ res = ohash_next(hand, &slot1)) {
+ slot2 = ohash_lookup_memory(htab,
+ (char *)res, sizeof(res->page), res->page);
+ if (ohash_find(htab, slot2) == NULL)
+ ohash_insert(htab, slot2, res);
+ else
+ free(res);
+ }
+
+ /* Discard the merged result. */
+
+ ohash_delete(hand);
+ free(hand);
+ return htab;
git.ckatri.com / mandoc.git / blobdiff