/*-------------------------------------------------------------------------

 *

 * multibitmapset.c

 *    Lists of Bitmapsets

 *

 * A multibitmapset is useful in situations where members of a set can

 * be identified by two small integers; for example, varno and varattno

 * of a group of Vars within a query.  The implementation is a List of

 * Bitmapsets, so that the empty set can be represented by NIL.  (But,

 * as with Bitmapsets, that's not the only allowed representation.)

 * The zero-based index of a List element is the first identifying value,

 * and the (also zero-based) index of a bit within that Bitmapset is

 * the second identifying value.  There is no expectation that the

 * Bitmapsets should all be the same size.

 *

 * The available operations on multibitmapsets are intended to parallel

 * those on bitmapsets, for example union and intersection.  So far only

 * a small fraction of that has been built out; we'll add more as needed.

 *

 *

 * Copyright (c) 2022-2025, PostgreSQL Global Development Group

 *

 * IDENTIFICATION

 *    src/backend/nodes/multibitmapset.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "nodes/multibitmapset.h"

/*

 * mbms_add_member

 *    Add a new member to a multibitmapset.

 *

 * The new member is identified by "listidx", the zero-based index of the

 * List element it should go into, and "bitidx", which specifies the bit

 * number to be set therein.

 *

 * This is like bms_add_member, but for multibitmapsets.

 */

List *

mbms_add_member(List *a, int listidx, int bitidx)

{

  Bitmapset  *bms;

  ListCell   *lc;

  if (listidx < 0 || bitidx < 0)

    elog(ERROR, "negative multibitmapset member index not allowed");

  /* Add empty elements as needed */

  while (list_length(a) <= listidx)

    a = lappend(a, NULL);

  /* Update the target element */

  lc = list_nth_cell(a, listidx);

  bms = lfirst_node(Bitmapset, lc);

  bms = bms_add_member(bms, bitidx);

  lfirst(lc) = bms;

  return a;

}

/*

 * mbms_add_members

 *    Add all members of set b to set a.

 *

 * This is a UNION operation, but the left input is modified in-place.

 *

 * This is like bms_add_members, but for multibitmapsets.

 */

List *

mbms_add_members(List *a, const List *b)

{

  ListCell   *lca,

         *lcb;

  /* Add empty elements to a, as needed */

  while (list_length(a) < list_length(b))

    a = lappend(a, NULL);

  /* forboth will stop at the end of the shorter list, which is fine */

  forboth(lca, a, lcb, b)

  {

    Bitmapset  *bmsa = lfirst_node(Bitmapset, lca);

    const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);

    bmsa = bms_add_members(bmsa, bmsb);

    lfirst(lca) = bmsa;

  }

  return a;

}

/*

 * mbms_int_members

 *    Reduce set a to its intersection with set b.

 *

 * This is an INTERSECT operation, but the left input is modified in-place.

 *

 * This is like bms_int_members, but for multibitmapsets.

 */

List *

mbms_int_members(List *a, const List *b)

{

  ListCell   *lca,

         *lcb;

  /* Remove any elements of a that are no longer of use */

  a = list_truncate(a, list_length(b));

  /* forboth will stop at the end of the shorter list, which is fine */

  forboth(lca, a, lcb, b)

  {

    Bitmapset  *bmsa = lfirst_node(Bitmapset, lca);

    const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);

    bmsa = bms_int_members(bmsa, bmsb);

    lfirst(lca) = bmsa;

  }

  return a;

}

/*

 * mbms_is_member

 *    Is listidx/bitidx a member of A?

 *

 * This is like bms_is_member, but for multibitmapsets.

 */

bool

mbms_is_member(int listidx, int bitidx, const List *a)

{

  const Bitmapset *bms;

  /* XXX better to just return false for negative indexes? */

  if (listidx < 0 || bitidx < 0)

    elog(ERROR, "negative multibitmapset member index not allowed");

  if (listidx >= list_length(a))

    return false;

  bms = list_nth_node(Bitmapset, a, listidx);

  return bms_is_member(bitidx, bms);

}

/*

 * mbms_overlap_sets

 *    Identify the bitmapsets having common members in a and b.

 *

 * The result is a bitmapset of the list indexes of bitmapsets that overlap.

 */

Bitmapset *

mbms_overlap_sets(const List *a, const List *b)

{

  Bitmapset  *result = NULL;

  ListCell   *lca,

         *lcb;

  /* forboth will stop at the end of the shorter list, which is fine */

  forboth(lca, a, lcb, b)

  {

    const Bitmapset *bmsa = lfirst_node(Bitmapset, lca);

    const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);

    if (bms_overlap(bmsa, bmsb))

      result = bms_add_member(result, foreach_current_index(lca));

  }

  return result;

}