File query_bitset.c¶
File List > cubrid > src > optimizer > query_bitset.c
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* query_bitset.c - Bitset operations for sets implemented as machine words
*/
#ident "$Id$"
#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "query_bitset.h"
#include "error_manager.h"
#include "memory_alloc.h"
#define NBYTES(n) ((n) * sizeof(BITSET_CARRIER))
#define NELEMS(n) ((n) * _WORDSIZE)
#define bitset_malloc(env, size) malloc(size)
#define bitset_free(ptr) free_and_init(ptr)
/*
* The number of one bits in a four-bit nibble.
*/
static const char nbits[] = {
0, /* 0000 */
1, /* 0001 */
1, /* 0010 */
2, /* 0011 */
1, /* 0100 */
2, /* 0101 */
2, /* 0110 */
3, /* 0111 */
1, /* 1000 */
2, /* 1001 */
2, /* 1010 */
3, /* 1011 */
2, /* 1100 */
3, /* 1101 */
3, /* 1110 */
4, /* 1111 */
};
static BITSET_CARRIER empty_set_words[NWORDS] = { 0 };
BITSET EMPTY_SET = { NULL, empty_set_words, NWORDS, {{0}} };
#if defined (CUBRID_DEBUG)
/*
* set_stats () - Print stats about set usage
* return: nothing
* fp(in): the stream on which to print the statistics
*/
void
set_stats (FILE * fp)
{
fprintf (fp, "Set statistics no longer collected\n");
}
#endif
/******************************************************************************
* *
* BITSET FUNCTIONS *
* *
*****************************************************************************/
/*
* bitset_extend () -
* return:
* dst(in):
* nwords(in):
*/
void
bitset_extend (BITSET * dst, int nwords)
{
BITSET_CARRIER *words;
assert (BITSET_IS_VALID (dst));
words = (BITSET_CARRIER *) malloc (NBYTES (nwords));
if (words == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, NBYTES (nwords));
return;
}
memcpy (words, dst->setp, NBYTES (dst->nwords));
memset (words + dst->nwords, 0, NBYTES (nwords - dst->nwords));
dst->nwords = nwords;
if (dst->setp != dst->set.word)
{
bitset_free (dst->setp);
}
dst->setp = words;
}
/*
* bitset_assign () -
* return:
* dst(in):
* src(in):
*/
void
bitset_assign (BITSET * dst, const BITSET * src)
{
assert (BITSET_IS_VALID (dst));
assert (BITSET_IS_VALID (src));
if (dst->nwords < src->nwords)
{
bitset_extend (dst, src->nwords);
}
memcpy (dst->setp, src->setp, NBYTES (src->nwords));
memset (dst->setp + src->nwords, 0, NBYTES (dst->nwords - src->nwords));
}
void
bitset_exchange (BITSET * v1, BITSET * v2)
{
BITSET tmp;
assert (BITSET_IS_VALID (v1));
assert (BITSET_IS_VALID (v2));
tmp = *v1;
if (v1->setp == v1->set.word)
{
tmp.setp = tmp.set.word;
}
*v1 = *v2;
if (v2->setp == v2->set.word)
{
v1->setp = v1->set.word;
}
*v2 = tmp;
if (tmp.setp == tmp.set.word)
{
v2->setp = v2->set.word;
}
}
/*
* bitset_add () -
* return:
* dst(in):
* x(in):
*/
void
bitset_add (BITSET * dst, int x)
{
int n;
assert (BITSET_IS_VALID (dst));
n = _WORD (x);
if (n >= dst->nwords)
{
bitset_extend (dst, n + 1);
}
dst->setp[n] |= (1L << _BIT (x));
}
/*
* bitset_remove () -
* return:
* dst(in):
* x(in):
*/
void
bitset_remove (BITSET * dst, int x)
{
int n;
assert (BITSET_IS_VALID (dst));
n = _WORD (x);
if (n < dst->nwords)
{
dst->setp[n] &= ~(1L << _BIT (x));
}
}
/*
* bitset_union () -
* return:
* dst(in):
* src(in):
*/
void
bitset_union (BITSET * dst, const BITSET * src)
{
int nwords;
assert (BITSET_IS_VALID (dst));
assert (BITSET_IS_VALID (src));
if (dst->nwords < src->nwords)
{
bitset_extend (dst, src->nwords);
}
nwords = src->nwords;
while (nwords)
{
nwords -= 1;
dst->setp[nwords] |= src->setp[nwords];
}
}
/*
* bitset_intersect () -
* return:
* dst(in):
* src(in):
*/
void
bitset_intersect (BITSET * dst, const BITSET * src)
{
int nwords;
assert (BITSET_IS_VALID (dst));
assert (BITSET_IS_VALID (src));
nwords = dst->nwords;
while (nwords > src->nwords)
{
nwords -= 1;
dst->setp[nwords] = 0;
}
while (nwords > 0)
{
nwords -= 1;
dst->setp[nwords] &= src->setp[nwords];
}
}
/*
* bitset_difference () -
* return:
* dst(in):
* src(in):
*/
void
bitset_difference (BITSET * dst, const BITSET * src)
{
int nwords;
assert (BITSET_IS_VALID (dst));
assert (BITSET_IS_VALID (src));
nwords = MIN (dst->nwords, src->nwords);
while (nwords)
{
nwords -= 1;
dst->setp[nwords] &= ~src->setp[nwords];
}
}
#if defined (ENABLE_UNUSED_FUNCTION)
/*
* bitset_invert () -
* return:
* dst(in):
*/
void
bitset_invert (BITSET * dst)
{
int nwords;
nwords = dst->nwords;
while (nwords)
{
nwords -= 1;
dst->setp[nwords] = ~dst->setp[nwords];
}
}
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* bitset_subset () -
* return:
* r(in):
* s(in):
*/
int
bitset_subset (const BITSET * r, const BITSET * s)
{
int nwords;
assert (BITSET_IS_VALID (s));
assert (BITSET_IS_VALID (r));
nwords = s->nwords;
while (nwords > r->nwords)
{
nwords -= 1;
if (s->setp[nwords])
{
return 0;
}
}
while (nwords)
{
nwords -= 1;
if ((r->setp[nwords] & s->setp[nwords]) != s->setp[nwords])
{
return 0;
}
}
return 1;
}
/*
* bitset_intersects () -
* return:
* r(in):
* s(in):
*/
int
bitset_intersects (const BITSET * r, const BITSET * s)
{
int nwords;
assert (BITSET_IS_VALID (s));
assert (BITSET_IS_VALID (r));
nwords = MIN (r->nwords, s->nwords);
while (nwords)
{
nwords -= 1;
if (r->setp[nwords] & s->setp[nwords])
{
return 1;
}
}
return 0;
}
/*
* bitset_is_empty () -
* return:
* s(in):
*/
int
bitset_is_empty (const BITSET * s)
{
int nwords;
assert (BITSET_IS_VALID (s));
nwords = s->nwords;
while (nwords)
{
nwords -= 1;
if (s->setp[nwords])
{
return 0;
}
}
return 1;
}
/*
* bitset_is_equivalent () -
* return:
* r(in):
* s(in):
*/
int
bitset_is_equivalent (const BITSET * r, const BITSET * s)
{
int nwords;
assert (BITSET_IS_VALID (s));
assert (BITSET_IS_VALID (r));
if (r->nwords < s->nwords)
{
nwords = s->nwords;
while (nwords > r->nwords)
{
nwords -= 1;
if (s->setp[nwords])
{
return 0;
}
}
}
else if (r->nwords > s->nwords)
{
nwords = r->nwords;
while (nwords > s->nwords)
{
nwords -= 1;
if (r->setp[nwords])
{
return 0;
}
}
}
else
{
nwords = r->nwords;
}
while (nwords)
{
nwords -= 1;
if (r->setp[nwords] != s->setp[nwords])
{
return 0;
}
}
return 1;
}
/*
* bitset_cardinality () -
* return:
* s(in):
*/
int
bitset_cardinality (const BITSET * s)
{
int nwords, card;
assert (BITSET_IS_VALID (s));
nwords = s->nwords;
card = 0;
while (nwords)
{
BITSET_CARRIER word;
nwords -= 1;
word = s->setp[nwords];
while (word)
{
card += nbits[word & 0xf];
word >>= 4;
}
}
return card;
}
#if defined (ENABLE_UNUSED_FUNCTION)
/*
* bitset_position () -
* return:
* s(in):
* x(in):
*/
int
bitset_position (const BITSET * s, int x)
{
int pos;
if (BITSET_MEMBER (*s, x))
{
int i, m;
BITSET_CARRIER mask, word;
pos = 0;
for (i = 0, m = _WORD (x); i < m; i++)
{
for (word = s->setp[i]; word; word >>= 4)
{
pos += nbits[word & 0xf];
}
}
mask = (1L << x) - 1;
for (word = s->setp[m] & mask; word; word >>= 4)
{
pos += nbits[word & 0xf];
}
}
else
{
pos = -1;
}
return pos;
}
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* bitset_iterate () -
* return:
* s(in):
* si(in):
*/
int
bitset_iterate (const BITSET * s, BITSET_ITERATOR * si)
{
si->set = s;
si->next = 0;
return bitset_next_member (si);
}
/*
* bitset_next_member () -
* return:
* si(in):
*/
int
bitset_next_member (BITSET_ITERATOR * si)
{
int nwords;
BITSET_CARRIER word;
int current, m;
current = si->next;
if (current < 0)
{
return -1;
}
assert (BITSET_IS_VALID (si->set));
nwords = si->set->nwords;
for (m = _WORD (current); m < nwords; current = _WORDSIZE * ++m)
{
for (word = si->set->setp[m] >> _BIT (current); word; current++, word >>= 1)
{
if (word & 0x1)
{
si->next = current + 1;
return current;
}
}
}
si->next = -1;
return -1;
}
/*
* bitset_first_member () -
* return:
* s(in):
*/
int
bitset_first_member (const BITSET * s)
{
BITSET_ITERATOR si;
return bitset_iterate (s, &si);
}
/*
* bitset_print () -
* return:
* s(in):
* fp(in):
*/
void
bitset_print (const BITSET * s, FILE * fp)
{
if (bitset_is_empty (s))
{
(void) fprintf (fp, "empty");
}
else
{
int i;
BITSET_ITERATOR si;
i = bitset_iterate (s, &si);
if (i != -1)
{
(void) fprintf (fp, "%d", i);
while ((i = bitset_next_member (&si)) != -1)
{
(void) fprintf (fp, " %d", i);
}
}
}
}
/*
* bitset_init () -
* return:
* s(in):
* env(in):
*/
void
bitset_init (BITSET * s, QO_ENV * env)
{
s->env = env;
s->setp = s->set.word;
s->nwords = NWORDS;
BITSET_CLEAR (*s);
}
/*
* bitset_delset () -
* return:
* s(in):
*/
void
bitset_delset (BITSET * s)
{
if (s->setp != s->set.word)
{
if (s->setp)
{
bitset_free (s->setp);
assert (s->setp == NULL);
}
}
#if !defined(NDEBUG)
s->nwords = 0;
assert (BITSET_IS_VALID (s) == false);
#endif
}