LCOV - code coverage report
Current view: top level - src/backend/nodes - multibitmapset.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 34 42 81.0 %
Date: 2024-07-19 16:11:31 Functions: 4 5 80.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * multibitmapset.c
       4             :  *    Lists of Bitmapsets
       5             :  *
       6             :  * A multibitmapset is useful in situations where members of a set can
       7             :  * be identified by two small integers; for example, varno and varattno
       8             :  * of a group of Vars within a query.  The implementation is a List of
       9             :  * Bitmapsets, so that the empty set can be represented by NIL.  (But,
      10             :  * as with Bitmapsets, that's not the only allowed representation.)
      11             :  * The zero-based index of a List element is the first identifying value,
      12             :  * and the (also zero-based) index of a bit within that Bitmapset is
      13             :  * the second identifying value.  There is no expectation that the
      14             :  * Bitmapsets should all be the same size.
      15             :  *
      16             :  * The available operations on multibitmapsets are intended to parallel
      17             :  * those on bitmapsets, for example union and intersection.  So far only
      18             :  * a small fraction of that has been built out; we'll add more as needed.
      19             :  *
      20             :  *
      21             :  * Copyright (c) 2022-2024, PostgreSQL Global Development Group
      22             :  *
      23             :  * IDENTIFICATION
      24             :  *    src/backend/nodes/multibitmapset.c
      25             :  *
      26             :  *-------------------------------------------------------------------------
      27             :  */
      28             : #include "postgres.h"
      29             : 
      30             : #include "nodes/multibitmapset.h"
      31             : 
      32             : 
      33             : /*
      34             :  * mbms_add_member
      35             :  *      Add a new member to a multibitmapset.
      36             :  *
      37             :  * The new member is identified by "listidx", the zero-based index of the
      38             :  * List element it should go into, and "bitidx", which specifies the bit
      39             :  * number to be set therein.
      40             :  *
      41             :  * This is like bms_add_member, but for multibitmapsets.
      42             :  */
      43             : List *
      44       88314 : mbms_add_member(List *a, int listidx, int bitidx)
      45             : {
      46             :     Bitmapset  *bms;
      47             :     ListCell   *lc;
      48             : 
      49       88314 :     if (listidx < 0 || bitidx < 0)
      50           0 :         elog(ERROR, "negative multibitmapset member index not allowed");
      51             :     /* Add empty elements as needed */
      52      429764 :     while (list_length(a) <= listidx)
      53      341450 :         a = lappend(a, NULL);
      54             :     /* Update the target element */
      55       88314 :     lc = list_nth_cell(a, listidx);
      56       88314 :     bms = lfirst_node(Bitmapset, lc);
      57       88314 :     bms = bms_add_member(bms, bitidx);
      58       88314 :     lfirst(lc) = bms;
      59       88314 :     return a;
      60             : }
      61             : 
      62             : /*
      63             :  * mbms_add_members
      64             :  *      Add all members of set b to set a.
      65             :  *
      66             :  * This is a UNION operation, but the left input is modified in-place.
      67             :  *
      68             :  * This is like bms_add_members, but for multibitmapsets.
      69             :  */
      70             : List *
      71      234592 : mbms_add_members(List *a, const List *b)
      72             : {
      73             :     ListCell   *lca,
      74             :                *lcb;
      75             : 
      76             :     /* Add empty elements to a, as needed */
      77      646636 :     while (list_length(a) < list_length(b))
      78      412044 :         a = lappend(a, NULL);
      79             :     /* forboth will stop at the end of the shorter list, which is fine */
      80      806962 :     forboth(lca, a, lcb, b)
      81             :     {
      82      572370 :         Bitmapset  *bmsa = lfirst_node(Bitmapset, lca);
      83      572370 :         const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
      84             : 
      85      572370 :         bmsa = bms_add_members(bmsa, bmsb);
      86      572370 :         lfirst(lca) = bmsa;
      87             :     }
      88      234592 :     return a;
      89             : }
      90             : 
      91             : /*
      92             :  * mbms_int_members
      93             :  *      Reduce set a to its intersection with set b.
      94             :  *
      95             :  * This is an INTERSECT operation, but the left input is modified in-place.
      96             :  *
      97             :  * This is like bms_int_members, but for multibitmapsets.
      98             :  */
      99             : List *
     100         328 : mbms_int_members(List *a, const List *b)
     101             : {
     102             :     ListCell   *lca,
     103             :                *lcb;
     104             : 
     105             :     /* Remove any elements of a that are no longer of use */
     106         328 :     a = list_truncate(a, list_length(b));
     107             :     /* forboth will stop at the end of the shorter list, which is fine */
     108        2556 :     forboth(lca, a, lcb, b)
     109             :     {
     110        2228 :         Bitmapset  *bmsa = lfirst_node(Bitmapset, lca);
     111        2228 :         const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
     112             : 
     113        2228 :         bmsa = bms_int_members(bmsa, bmsb);
     114        2228 :         lfirst(lca) = bmsa;
     115             :     }
     116         328 :     return a;
     117             : }
     118             : 
     119             : /*
     120             :  * mbms_is_member
     121             :  *      Is listidx/bitidx a member of A?
     122             :  *
     123             :  * This is like bms_is_member, but for multibitmapsets.
     124             :  */
     125             : bool
     126           0 : mbms_is_member(int listidx, int bitidx, const List *a)
     127             : {
     128             :     const Bitmapset *bms;
     129             : 
     130             :     /* XXX better to just return false for negative indexes? */
     131           0 :     if (listidx < 0 || bitidx < 0)
     132           0 :         elog(ERROR, "negative multibitmapset member index not allowed");
     133           0 :     if (listidx >= list_length(a))
     134           0 :         return false;
     135           0 :     bms = list_nth_node(Bitmapset, a, listidx);
     136           0 :     return bms_is_member(bitidx, bms);
     137             : }
     138             : 
     139             : /*
     140             :  * mbms_overlap_sets
     141             :  *      Identify the bitmapsets having common members in a and b.
     142             :  *
     143             :  * The result is a bitmapset of the list indexes of bitmapsets that overlap.
     144             :  */
     145             : Bitmapset *
     146       37198 : mbms_overlap_sets(const List *a, const List *b)
     147             : {
     148       37198 :     Bitmapset  *result = NULL;
     149             :     ListCell   *lca,
     150             :                *lcb;
     151             : 
     152             :     /* forboth will stop at the end of the shorter list, which is fine */
     153       41202 :     forboth(lca, a, lcb, b)
     154             :     {
     155        4004 :         const Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
     156        4004 :         const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
     157             : 
     158        4004 :         if (bms_overlap(bmsa, bmsb))
     159        1026 :             result = bms_add_member(result, foreach_current_index(lca));
     160             :     }
     161       37198 :     return result;
     162             : }

Generated by: LCOV version 1.14