LCOV - code coverage report
Current view: top level - gdk - gdk.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 215 249 86.3 %
Date: 2021-09-14 19:48:19 Functions: 19 19 100.0 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : /*
      10             :  * @t The Goblin Database Kernel
      11             :  * @v Version 3.05
      12             :  * @a Martin L. Kersten, Peter Boncz, Niels Nes, Sjoerd Mullender
      13             :  *
      14             :  * @+ The Inner Core
      15             :  * The innermost library of the MonetDB database system is formed by
      16             :  * the library called GDK, an abbreviation of Goblin Database Kernel.
      17             :  * Its development was originally rooted in the design of a pure
      18             :  * active-object-oriented programming language, before development
      19             :  * was shifted towards a re-usable database kernel engine.
      20             :  *
      21             :  * GDK is a C library that provides ACID properties on a DSM model
      22             :  * @tex
      23             :  * [@cite{Copeland85}]
      24             :  * @end tex
      25             :  * , using main-memory
      26             :  * database algorithms
      27             :  * @tex
      28             :  * [@cite{Garcia-Molina92}]
      29             :  * @end tex
      30             :  *  built on virtual-memory
      31             :  * OS primitives and multi-threaded parallelism.
      32             :  * Its implementation has undergone various changes over its decade
      33             :  * of development, many of which were driven by external needs to
      34             :  * obtain a robust and fast database system.
      35             :  *
      36             :  * The coding scheme explored in GDK has also laid a foundation to
      37             :  * communicate over time experiences and to provide (hopefully)
      38             :  * helpful advice near to the place where the code-reader needs it.
      39             :  * Of course, over such a long time the documentation diverges from
      40             :  * reality. Especially in areas where the environment of this package
      41             :  * is being described.
      42             :  * Consider such deviations as historic landmarks, e.g. crystallization
      43             :  * of brave ideas and mistakes rectified at a later stage.
      44             :  *
      45             :  * @+ Short Outline
      46             :  * The facilities provided in this implementation are:
      47             :  * @itemize
      48             :  * @item
      49             :  * GDK or Goblin Database Kernel routines for session management
      50             :  * @item
      51             :  *  BAT routines that define the primitive operations on the
      52             :  * database tables (BATs).
      53             :  * @item
      54             :  *  BBP routines to manage the BAT Buffer Pool (BBP).
      55             :  * @item
      56             :  *  ATOM routines to manipulate primitive types, define new types
      57             :  * using an ADT interface.
      58             :  * @item
      59             :  *  HEAP routines for manipulating heaps: linear spaces of memory
      60             :  * that are GDK's vehicle of mass storage (on which BATs are built).
      61             :  * @item
      62             :  *  DELTA routines to access inserted/deleted elements within a
      63             :  * transaction.
      64             :  * @item
      65             :  *  HASH routines for manipulating GDK's built-in linear-chained
      66             :  * hash tables, for accelerating lookup searches on BATs.
      67             :  * @item
      68             :  *  TM routines that provide basic transaction management primitives.
      69             :  * @item
      70             :  *  TRG routines that provided active database support. [DEPRECATED]
      71             :  * @item
      72             :  *  ALIGN routines that implement BAT alignment management.
      73             :  * @end itemize
      74             :  *
      75             :  * The Binary Association Table (BAT) is the lowest level of storage
      76             :  * considered in the Goblin runtime system
      77             :  * @tex
      78             :  * [@cite{Goblin}]
      79             :  * @end tex
      80             :  * .  A BAT is a
      81             :  * self-descriptive main-memory structure that represents the
      82             :  * @strong{binary relationship} between two atomic types.  The
      83             :  * association can be defined over:
      84             :  * @table @code
      85             :  * @item void:
      86             :  *  virtual-OIDs: a densely ascending column of OIDs (takes zero-storage).
      87             :  * @item bit:
      88             :  *  Booleans, implemented as one byte values.
      89             :  * @item bte:
      90             :  *  Tiny (1-byte) integers (8-bit @strong{integer}s).
      91             :  * @item sht:
      92             :  *  Short integers (16-bit @strong{integer}s).
      93             :  * @item int:
      94             :  *  This is the C @strong{int} type (32-bit).
      95             :  * @item oid:
      96             :  *  Unique @strong{long int} values uses as object identifier. Highest
      97             :  *          bit cleared always.  Thus, oids-s are 31-bit numbers on
      98             :  *          32-bit systems, and 63-bit numbers on 64-bit systems.
      99             :  * @item ptr:
     100             :  * Memory pointer values. DEPRECATED.  Can only be stored in transient
     101             :  * BATs.
     102             :  * @item flt:
     103             :  *  The IEEE @strong{float} type.
     104             :  * @item dbl:
     105             :  *  The IEEE @strong{double} type.
     106             :  * @item lng:
     107             :  *  Longs: the C @strong{long long} type (64-bit integers).
     108             :  * @item hge:
     109             :  *  "huge" integers: the GCC @strong{__int128} type (128-bit integers).
     110             :  * @item str:
     111             :  *  UTF-8 strings (Unicode). A zero-terminated byte sequence.
     112             :  * @item bat:
     113             :  *  Bat descriptor. This allows for recursive administered tables, but
     114             :  *  severely complicates transaction management. Therefore, they CAN
     115             :  *  ONLY BE STORED IN TRANSIENT BATs.
     116             :  * @end table
     117             :  *
     118             :  * This model can be used as a back-end model underlying other -higher
     119             :  * level- models, in order to achieve @strong{better performance} and
     120             :  * @strong{data independence} in one go. The relational model and the
     121             :  * object-oriented model can be mapped on BATs by vertically splitting
     122             :  * every table (or class) for each attribute. Each such a column is
     123             :  * then stored in a BAT with type @strong{bat[oid,attribute]}, where
     124             :  * the unique object identifiers link tuples in the different BATs.
     125             :  * Relationship attributes in the object-oriented model hence are
     126             :  * mapped to @strong{bat[oid,oid]} tables, being equivalent to the
     127             :  * concept of @emph{join indexes} @tex [@cite{Valduriez87}] @end tex .
     128             :  *
     129             :  * The set of built-in types can be extended with user-defined types
     130             :  * through an ADT interface.  They are linked with the kernel to
     131             :  * obtain an enhanced library, or they are dynamically loaded upon
     132             :  * request.
     133             :  *
     134             :  * Types can be derived from other types. They represent something
     135             :  * different than that from which they are derived, but their internal
     136             :  * storage management is equal. This feature facilitates the work of
     137             :  * extension programmers, by enabling reuse of implementation code,
     138             :  * but is also used to keep the GDK code portable from 32-bits to
     139             :  * 64-bits machines: the @strong{oid} and @strong{ptr} types are
     140             :  * derived from @strong{int} on 32-bits machines, but is derived from
     141             :  * @strong{lng} on 64 bits machines. This requires changes in only two
     142             :  * lines of code each.
     143             :  *
     144             :  * To accelerate lookup and search in BATs, GDK supports one built-in
     145             :  * search accelerator: hash tables. We choose an implementation
     146             :  * efficient for main-memory: bucket chained hash
     147             :  * @tex
     148             :  * [@cite{LehCar86,Analyti92}]
     149             :  * @end tex
     150             :  * . Alternatively, when the table is sorted, it will resort to
     151             :  * merge-scan operations or binary lookups.
     152             :  *
     153             :  * BATs are built on the concept of heaps, which are large pieces of
     154             :  * main memory. They can also consist of virtual memory, in case the
     155             :  * working set exceeds main-memory. In this case, GDK supports
     156             :  * operations that cluster the heaps of a BAT, in order to improve
     157             :  * performance of its main-memory.
     158             :  *
     159             :  *
     160             :  * @- Rationale
     161             :  * The rationale for choosing a BAT as the building block for both
     162             :  * relational and object-oriented system is based on the following
     163             :  * observations:
     164             :  *
     165             :  * @itemize
     166             :  * @item -
     167             :  * Given the fact that CPU speed and main-memory increase in current
     168             :  * workstation hardware for the last years has been exceeding IO
     169             :  * access speed increase, traditional disk-page oriented algorithms do
     170             :  * no longer take best advantage of hardware, in most database
     171             :  * operations.
     172             :  *
     173             :  * Instead of having a disk-block oriented kernel with a large memory
     174             :  * cache, we choose to build a main-memory kernel, that only under
     175             :  * large data volumes slowly degrades to IO-bound performance,
     176             :  * comparable to traditional systems
     177             :  * @tex
     178             :  * [@cite{boncz95,boncz96}]
     179             :  * @end tex
     180             :  * .
     181             :  *
     182             :  * @item -
     183             :  * Traditional (disk-based) relational systems move too much data
     184             :  * around to save on (main-memory) join operations.
     185             :  *
     186             :  * The fully decomposed store (DSM
     187             :  * @tex
     188             :  * [@cite{Copeland85})]
     189             :  * @end tex
     190             :  * assures that only those attributes of a relation that are needed,
     191             :  * will have to be accessed.
     192             :  *
     193             :  * @item -
     194             :  * The data management issues for a binary association is much
     195             :  * easier to deal with than traditional @emph{struct}-based approaches
     196             :  * encountered in relational systems.
     197             :  *
     198             :  * @item -
     199             :  * Object-oriented systems often maintain a double cache, one with the
     200             :  * disk-based representation and a C pointer-based main-memory
     201             :  * structure.  This causes expensive conversions and replicated
     202             :  * storage management.  GDK does not do such `pointer swizzling'. It
     203             :  * used virtual-memory (@strong{mmap()}) and buffer management advice
     204             :  * (@strong{madvise()}) OS primitives to cache only once. Tables take
     205             :  * the same form in memory as on disk, making the use of this
     206             :  * technique transparent
     207             :  * @tex
     208             :  * [@cite{oo7}]
     209             :  * @end tex
     210             :  * .
     211             :  * @end itemize
     212             :  *
     213             :  * A RDBMS or OODBMS based on BATs strongly depends on our ability to
     214             :  * efficiently support tuples and to handle small joins, respectively.
     215             :  *
     216             :  * The remainder of this document describes the Goblin Database kernel
     217             :  * implementation at greater detail. It is organized as follows:
     218             :  * @table @code
     219             :  * @item @strong{GDK Interface}:
     220             :  *
     221             :  * It describes the global interface with which GDK sessions can be
     222             :  * started and ended, and environment variables used.
     223             :  *
     224             :  * @item @strong{Binary Association Tables}:
     225             :  *
     226             :  * As already mentioned, these are the primary data structure of GDK.
     227             :  * This chapter describes the kernel operations for creation,
     228             :  * destruction and basic manipulation of BATs and BUNs (i.e. tuples:
     229             :  * Binary UNits).
     230             :  *
     231             :  * @item @strong{BAT Buffer Pool:}
     232             :  *
     233             :  * All BATs are registered in the BAT Buffer Pool. This directory is
     234             :  * used to guide swapping in and out of BATs. Here we find routines
     235             :  * that guide this swapping process.
     236             :  *
     237             :  * @item @strong{GDK Extensibility:}
     238             :  *
     239             :  * Atoms can be defined using a unified ADT interface.  There is also
     240             :  * an interface to extend the GDK library with dynamically linked
     241             :  * object code.
     242             :  *
     243             :  * @item @strong{GDK Utilities:}
     244             :  *
     245             :  * Memory allocation and error handling primitives are
     246             :  * provided. Layers built on top of GDK should use them, for proper
     247             :  * system monitoring.  Thread management is also included here.
     248             :  *
     249             :  * @item @strong{Transaction Management:}
     250             :  *
     251             :  * For the time being, we just provide BAT-grained concurrency and
     252             :  * global transactions. Work is needed here.
     253             :  *
     254             :  * @item @strong{BAT Alignment:}
     255             :  * Due to the mapping of multi-ary datamodels onto the BAT model, we
     256             :  * expect many correspondences among BATs, e.g.
     257             :  * @emph{bat(oid,attr1),..  bat(oid,attrN)} vertical
     258             :  * decompositions. Frequent activities will be to jump from one
     259             :  * attribute to the other (`bunhopping'). If the head columns are
     260             :  * equal lists in two BATs, merge or even array lookups can be used
     261             :  * instead of hash lookups. The alignment interface makes these
     262             :  * relations explicitly manageable.
     263             :  *
     264             :  * In GDK, complex data models are mapped with DSM on binary tables.
     265             :  * Usually, one decomposes @emph{N}-ary relations into @emph{N} BATs
     266             :  * with an @strong{oid} in the head column, and the attribute in the
     267             :  * tail column.  There may well be groups of tables that have the same
     268             :  * sets of @strong{oid}s, equally ordered. The alignment interface is
     269             :  * intended to make this explicit.  Implementations can use this
     270             :  * interface to detect this situation, and use cheaper algorithms
     271             :  * (like merge-join, or even array lookup) instead.
     272             :  *
     273             :  * @item @strong{BAT Iterators:}
     274             :  *
     275             :  * Iterators are C macros that generally encapsulate a complex
     276             :  * for-loop.  They would be the equivalent of cursors in the SQL
     277             :  * model. The macro interface (instead of a function call interface)
     278             :  * is chosen to achieve speed when iterating main-memory tables.
     279             :  *
     280             :  * @item @strong{Common BAT Operations:}
     281             :  *
     282             :  * These are much used operations on BATs, such as aggregate functions
     283             :  * and relational operators. They are implemented in terms of BAT- and
     284             :  * BUN-manipulation GDK primitives.
     285             :  * @end table
     286             :  *
     287             :  * @+ Interface Files
     288             :  * In this section we summarize the user interface to the GDK library.
     289             :  * It consist of a header file (gdk.h) and an object library
     290             :  * (gdklib.a), which implements the required functionality. The header
     291             :  * file must be included in any program that uses the library. The
     292             :  * library must be linked with such a program.
     293             :  *
     294             :  * @- Database Context
     295             :  *
     296             :  * The MonetDB environment settings are collected in a configuration
     297             :  * file. Amongst others it contains the location of the database
     298             :  * directory.  First, the database directory is closed for other
     299             :  * servers running at the same time.  Second, performance enhancements
     300             :  * may take effect, such as locking the code into memory (if the OS
     301             :  * permits) and preloading the data dictionary.  An error at this
     302             :  * stage normally lead to an abort.
     303             :  */
     304             : 
     305             : #ifndef _GDK_H_
     306             : #define _GDK_H_
     307             : 
     308             : /* standard includes upon which all configure tests depend */
     309             : #ifdef HAVE_SYS_TYPES_H
     310             : # include <sys/types.h>
     311             : #endif
     312             : #ifdef HAVE_SYS_STAT_H
     313             : # include <sys/stat.h>
     314             : #endif
     315             : #include <stddef.h>
     316             : #include <string.h>
     317             : #ifdef HAVE_UNISTD_H
     318             : # include <unistd.h>
     319             : #endif
     320             : 
     321             : #include <ctype.h>                /* isspace etc. */
     322             : 
     323             : #ifdef HAVE_SYS_FILE_H
     324             : # include <sys/file.h>
     325             : #endif
     326             : 
     327             : #ifdef HAVE_DIRENT_H
     328             : # include <dirent.h>
     329             : #endif
     330             : 
     331             : #include <limits.h>               /* for *_MIN and *_MAX */
     332             : #include <float.h>                /* for FLT_MAX and DBL_MAX */
     333             : 
     334             : typedef enum { GDK_FAIL, GDK_SUCCEED } gdk_return;
     335             : 
     336             : #include "gdk_system.h"
     337             : #include "gdk_posix.h"
     338             : #include "stream.h"
     339             : #include "mstring.h"
     340             : 
     341             : #undef MIN
     342             : #undef MAX
     343             : #define MAX(A,B)        ((A)<(B)?(B):(A))
     344             : #define MIN(A,B)        ((A)>(B)?(B):(A))
     345             : 
     346             : /* defines from ctype with casts that allow passing char values */
     347             : #define GDKisspace(c)   isspace((unsigned char) (c))
     348             : #define GDKisalnum(c)   isalnum((unsigned char) (c))
     349             : #define GDKisdigit(c)   isdigit((unsigned char) (c))
     350             : 
     351             : #define BATDIR          "bat"
     352             : #define TEMPDIR_NAME    "TEMP_DATA"
     353             : 
     354             : #define DELDIR          BATDIR DIR_SEP_STR "DELETE_ME"
     355             : #define BAKDIR          BATDIR DIR_SEP_STR "BACKUP"
     356             : #define SUBDIR          BAKDIR DIR_SEP_STR "SUBCOMMIT" /* note K, not T */
     357             : #define LEFTDIR         BATDIR DIR_SEP_STR "LEFTOVERS"
     358             : #define TEMPDIR         BATDIR DIR_SEP_STR TEMPDIR_NAME
     359             : 
     360             : /*
     361             :    See `man mserver5` or tools/mserver/mserver5.1
     362             :    for a documentation of the following debug options.
     363             : */
     364             : 
     365             : #define THRDMASK        (1)
     366             : #define CHECKMASK       (1<<1)
     367             : #define CHECKDEBUG      if (GDKdebug & CHECKMASK)
     368             : #define PROPMASK        (1<<3)
     369             : #define PROPDEBUG       if (GDKdebug & PROPMASK)
     370             : #define IOMASK          (1<<4)
     371             : #define BATMASK         (1<<5)
     372             : #define PARMASK         (1<<7)
     373             : #define TMMASK          (1<<9)
     374             : #define TEMMASK         (1<<10)
     375             : #define PERFMASK        (1<<12)
     376             : #define DELTAMASK       (1<<13)
     377             : #define LOADMASK        (1<<14)
     378             : #define ACCELMASK       (1<<20)
     379             : #define ALGOMASK        (1<<21)
     380             : 
     381             : #define NOSYNCMASK      (1<<24)
     382             : 
     383             : #define DEADBEEFMASK    (1<<25)
     384             : #define DEADBEEFCHK     if (!(GDKdebug & DEADBEEFMASK))
     385             : 
     386             : #define ALLOCMASK       (1<<26)
     387             : 
     388             : /* M5, only; cf.,
     389             :  * monetdb5/mal/mal.h
     390             :  */
     391             : #define OPTMASK         (1<<27)
     392             : 
     393             : #define HEAPMASK        (1<<28)
     394             : 
     395             : #define FORCEMITOMASK   (1<<29)
     396             : #define FORCEMITODEBUG  if (GDKdebug & FORCEMITOMASK)
     397             : 
     398             : /*
     399             :  * @- GDK session handling
     400             :  * @multitable @columnfractions 0.08 0.7
     401             :  * @item int
     402             :  * @tab GDKinit (char *db, char *dbpath, int allocmap)
     403             :  * @item int
     404             :  * @tab GDKexit (int status)
     405             :  * @end multitable
     406             :  *
     407             :  * The session is bracketed by GDKinit and GDKexit. Initialization
     408             :  * involves setting up the administration for database access, such as
     409             :  * memory allocation for the database buffer pool.  During the exit
     410             :  * phase any pending transaction is aborted and the database is freed
     411             :  * for access by other users.  A zero is returned upon encountering an
     412             :  * erroneous situation.
     413             :  *
     414             :  * @- Definitions
     415             :  * The interface definitions for the application programs are shown
     416             :  * below.  The global variables should not be modified directly.
     417             :  */
     418             : #ifndef TRUE
     419             : #define TRUE            true
     420             : #define FALSE           false
     421             : #endif
     422             : 
     423             : #define BATMARGIN       1.2     /* extra free margin for new heaps */
     424             : #define BATTINY_BITS    8
     425             : #define BATTINY         ((BUN)1<<BATTINY_BITS)    /* minimum allocation buncnt for a BAT */
     426             : 
     427             : enum {
     428             :         TYPE_void = 0,
     429             :         TYPE_msk,               /* bit mask */
     430             :         TYPE_bit,               /* TRUE, FALSE, or nil */
     431             :         TYPE_bte,
     432             :         TYPE_sht,
     433             :         TYPE_bat,               /* BAT id: index in BBPcache */
     434             :         TYPE_int,
     435             :         TYPE_oid,
     436             :         TYPE_ptr,               /* C pointer! */
     437             :         TYPE_flt,
     438             :         TYPE_dbl,
     439             :         TYPE_lng,
     440             : #ifdef HAVE_HGE
     441             :         TYPE_hge,
     442             : #endif
     443             :         TYPE_date,
     444             :         TYPE_daytime,
     445             :         TYPE_timestamp,
     446             :         TYPE_uuid,
     447             :         TYPE_str,
     448             :         TYPE_any = 255,         /* limit types to <255! */
     449             : };
     450             : 
     451             : typedef bool msk;
     452             : typedef int8_t bit;
     453             : typedef int8_t bte;
     454             : typedef int16_t sht;
     455             : typedef int64_t lng;
     456             : typedef uint64_t ulng;
     457             : 
     458             : #define SIZEOF_OID      SIZEOF_SIZE_T
     459             : typedef size_t oid;
     460             : #define OIDFMT          "%zu"
     461             : 
     462             : typedef int bat;                /* Index into BBP */
     463             : typedef void *ptr;              /* Internal coding of types */
     464             : 
     465             : #define SIZEOF_PTR      SIZEOF_VOID_P
     466             : typedef float flt;
     467             : typedef double dbl;
     468             : typedef char *str;
     469             : 
     470             : #ifdef HAVE_UUID_UUID_H
     471             : #include <uuid/uuid.h>
     472             : #endif
     473             : 
     474             : #ifdef HAVE_UUID
     475             : #define UUID_SIZE       ((int) sizeof(uuid_t)) /* size of a UUID */
     476             : #else
     477             : #define UUID_SIZE       16      /* size of a UUID */
     478             : #endif
     479             : #define UUID_STRLEN     36      /* length of string representation */
     480             : 
     481             : typedef union {
     482             : #ifdef HAVE_HGE
     483             :         hge h;                  /* force alignment, not otherwise used */
     484             : #else
     485             :         lng l[2];               /* force alignment, not otherwise used */
     486             : #endif
     487             : #ifdef HAVE_UUID
     488             :         uuid_t u;
     489             : #else
     490             :         uint8_t u[UUID_SIZE];
     491             : #endif
     492             : } uuid;
     493             : 
     494             : #define SIZEOF_LNG              8
     495             : #define LL_CONSTANT(val)        INT64_C(val)
     496             : #define LLFMT                   "%" PRId64
     497             : #define ULLFMT                  "%" PRIu64
     498             : #define LLSCN                   "%" SCNd64
     499             : #define ULLSCN                  "%" SCNu64
     500             : 
     501             : typedef oid var_t;              /* type used for heap index of var-sized BAT */
     502             : #define SIZEOF_VAR_T    SIZEOF_OID
     503             : #define VARFMT          OIDFMT
     504             : 
     505             : #if SIZEOF_VAR_T == SIZEOF_INT
     506             : #define VAR_MAX         ((var_t) INT_MAX)
     507             : #else
     508             : #define VAR_MAX         ((var_t) INT64_MAX)
     509             : #endif
     510             : 
     511             : typedef oid BUN;                /* BUN position */
     512             : #define SIZEOF_BUN      SIZEOF_OID
     513             : #define BUNFMT          OIDFMT
     514             : /* alternatively:
     515             : typedef size_t BUN;
     516             : #define SIZEOF_BUN      SIZEOF_SIZE_T
     517             : #define BUNFMT          "%zu"
     518             : */
     519             : #if SIZEOF_BUN == SIZEOF_INT
     520             : #define BUN_NONE ((BUN) INT_MAX)
     521             : #else
     522             : #define BUN_NONE ((BUN) INT64_MAX)
     523             : #endif
     524             : #define BUN_MAX (BUN_NONE - 1)  /* maximum allowed size of a BAT */
     525             : 
     526             : /*
     527             :  * @- Checking and Error definitions:
     528             :  */
     529             : #define ATOMextern(t)   (ATOMstorage(t) >= TYPE_str)
     530             : 
     531             : typedef enum {
     532             :         PERSISTENT = 0,
     533             :         TRANSIENT,
     534             : } role_t;
     535             : 
     536             : /* Heap storage modes */
     537             : typedef enum {
     538             :         STORE_INVALID = 0,      /* invalid value, used to indicate error */
     539             :         STORE_MEM,              /* load into GDKmalloced memory */
     540             :         STORE_MMAP,             /* mmap() into virtual memory */
     541             :         STORE_PRIV,             /* BAT copy of copy-on-write mmap */
     542             :         STORE_CMEM,             /* load into malloc (not GDKmalloc) memory*/
     543             :         STORE_NOWN,             /* memory not owned by the BAT */
     544             :         STORE_MMAPABS,          /* mmap() into virtual memory from an
     545             :                                  * absolute path (not part of dbfarm) */
     546             : } storage_t;
     547             : 
     548             : typedef struct {
     549             :         size_t free;            /* index where free area starts. */
     550             :         size_t size;            /* size of the heap (bytes) */
     551             :         char *base;             /* base pointer in memory. */
     552             : #if SIZEOF_VOID_P == 4
     553             :         char filename[32];      /* file containing image of the heap */
     554             : #else
     555             :         char filename[40];      /* file containing image of the heap */
     556             : #endif
     557             : 
     558             :         ATOMIC_TYPE refs;       /* reference count for this heap */
     559             :         bte farmid;             /* id of farm where heap is located */
     560             :         bool hashash:1,         /* the string heap contains hash values */
     561             :                 cleanhash:1,    /* string heaps must clean hash */
     562             :                 dirty:1,        /* specific heap dirty marker */
     563             :                 remove:1,       /* remove storage file when freeing */
     564             :                 wasempty:1;     /* heap was empty when last saved/created */
     565             :         storage_t storage;      /* storage mode (mmap/malloc). */
     566             :         storage_t newstorage;   /* new desired storage mode at re-allocation. */
     567             :         bat parentid;           /* cache id of VIEW parent bat */
     568             : } Heap;
     569             : 
     570             : typedef struct Hash Hash;
     571             : typedef struct Imprints Imprints;
     572             : 
     573             : /*
     574             :  * @+ Binary Association Tables
     575             :  * Having gone to the previous preliminary definitions, we will now
     576             :  * introduce the structure of Binary Association Tables (BATs) in
     577             :  * detail. They are the basic storage unit on which GDK is modeled.
     578             :  *
     579             :  * The BAT holds an unlimited number of binary associations, called
     580             :  * BUNs (@strong{Binary UNits}).  The two attributes of a BUN are
     581             :  * called @strong{head} (left) and @strong{tail} (right) in the
     582             :  * remainder of this document.
     583             :  *
     584             :  *  @c image{http://monetdb.cwi.nl/projects/monetdb-mk/imgs/bat1,,,,feps}
     585             :  *
     586             :  * The above figure shows what a BAT looks like. It consists of two
     587             :  * columns, called head and tail, such that we have always binary
     588             :  * tuples (BUNs). The overlooking structure is the @strong{BAT
     589             :  * record}.  It points to a heap structure called the @strong{BUN
     590             :  * heap}.  This heap contains the atomic values inside the two
     591             :  * columns. If they are fixed-sized atoms, these atoms reside directly
     592             :  * in the BUN heap. If they are variable-sized atoms (such as string
     593             :  * or polygon), however, the columns has an extra heap for storing
     594             :  * those (such @strong{variable-sized atom heaps} are then referred to
     595             :  * as @strong{Head Heap}s and @strong{Tail Heap}s). The BUN heap then
     596             :  * contains integer byte-offsets (fixed-sized, of course) into a head-
     597             :  * or tail-heap.
     598             :  *
     599             :  * The BUN heap contains a contiguous range of BUNs. It starts after
     600             :  * the @strong{first} pointer, and finishes at the end in the
     601             :  * @strong{free} area of the BUN. All BUNs after the @strong{inserted}
     602             :  * pointer have been added in the last transaction (and will be
     603             :  * deleted on a transaction abort). All BUNs between the
     604             :  * @strong{deleted} pointer and the @strong{first} have been deleted
     605             :  * in this transaction (and will be reinserted at a transaction
     606             :  * abort).
     607             :  *
     608             :  * The location of a certain BUN in a BAT may change between
     609             :  * successive library routine invocations.  Therefore, one should
     610             :  * avoid keeping references into the BAT storage area for long
     611             :  * periods.
     612             :  *
     613             :  * Passing values between the library routines and the enclosing C
     614             :  * program is primarily through value pointers of type ptr. Pointers
     615             :  * into the BAT storage area should only be used for retrieval. Direct
     616             :  * updates of data stored in a BAT is forbidden. The user should
     617             :  * adhere to the interface conventions to guarantee the integrity
     618             :  * rules and to maintain the (hidden) auxiliary search structures.
     619             :  *
     620             :  * @- GDK variant record type
     621             :  * When manipulating values, MonetDB puts them into value records.
     622             :  * The built-in types have a direct entry in the union. Others should
     623             :  * be represented as a pointer of memory in pval or as a string, which
     624             :  * is basically the same. In such cases the len field indicates the
     625             :  * size of this piece of memory.
     626             :  */
     627             : typedef struct {
     628             :         union {                 /* storage is first in the record */
     629             :                 int ival;
     630             :                 oid oval;
     631             :                 sht shval;
     632             :                 bte btval;
     633             :                 msk mval;
     634             :                 flt fval;
     635             :                 ptr pval;
     636             :                 bat bval;
     637             :                 str sval;
     638             :                 dbl dval;
     639             :                 lng lval;
     640             : #ifdef HAVE_HGE
     641             :                 hge hval;
     642             : #endif
     643             :                 uuid uval;
     644             :         } val;
     645             :         size_t len;
     646             :         int vtype;
     647             : } *ValPtr, ValRecord;
     648             : 
     649             : /* interface definitions */
     650             : gdk_export void *VALconvert(int typ, ValPtr t);
     651             : gdk_export char *VALformat(const ValRecord *res);
     652             : gdk_export ValPtr VALcopy(ValPtr dst, const ValRecord *src);
     653             : gdk_export ValPtr VALinit(ValPtr d, int tpe, const void *s);
     654             : gdk_export void VALempty(ValPtr v);
     655             : gdk_export void VALclear(ValPtr v);
     656             : gdk_export ValPtr VALset(ValPtr v, int t, void *p);
     657             : gdk_export void *VALget(ValPtr v);
     658             : gdk_export int VALcmp(const ValRecord *p, const ValRecord *q);
     659             : gdk_export bool VALisnil(const ValRecord *v);
     660             : 
     661             : /*
     662             :  * @- The BAT record
     663             :  * The elements of the BAT structure are introduced in the remainder.
     664             :  * Instead of using the underlying types hidden beneath it, one should
     665             :  * use a @emph{BAT} type that is supposed to look like this:
     666             :  * @verbatim
     667             :  * typedef struct {
     668             :  *           // static BAT properties
     669             :  *           bat    batCacheid;       // bat id: index in BBPcache
     670             :  *           bool   batTransient;     // persistence mode
     671             :  *           bool   batCopiedtodisk;  // BAT is saved on disk?
     672             :  *           // dynamic BAT properties
     673             :  *           int    batHeat;          // heat of BAT in the BBP
     674             :  *           bool   batDirtydesc;     // BAT descriptor specific dirty flag
     675             :  *           Heap*  batBuns;          // Heap where the buns are stored
     676             :  *           // DELTA status
     677             :  *           BUN    batInserted;      // first inserted BUN
     678             :  *           BUN    batCount;         // Tuple count
     679             :  *           // Tail properties
     680             :  *           int    ttype;            // Tail type number
     681             :  *           str    tident;           // name for tail column
     682             :  *           bool   tkey;             // tail values are unique
     683             :  *           bool   tnonil;           // tail has no nils
     684             :  *           bool   tsorted;          // are tail values currently ordered?
     685             :  *           bool   tvarsized;        // for speed: tail type is varsized?
     686             :  *           // Tail storage
     687             :  *           int    tloc;             // byte-offset in BUN for tail elements
     688             :  *           Heap   *theap;           // heap for varsized tail values
     689             :  *           Hash   *thash;           // linear chained hash table on tail
     690             :  *           Imprints *timprints;     // column imprints index on tail
     691             :  *           orderidx torderidx;      // order oid index on tail
     692             :  *  } BAT;
     693             :  * @end verbatim
     694             :  *
     695             :  * The internal structure of the @strong{BAT} record is in fact much
     696             :  * more complex, but GDK programmers should refrain of making use of
     697             :  * that.
     698             :  *
     699             :  * Since we don't want to pay cost to keep both views in line with
     700             :  * each other under BAT updates, we work with shared pieces of memory
     701             :  * between the two views. An update to one will thus automatically
     702             :  * update the other.  In the same line, we allow @strong{synchronized
     703             :  * BATs} (BATs with identical head columns, and marked as such in the
     704             :  * @strong{BAT Alignment} interface) now to be clustered horizontally.
     705             :  *
     706             :  *  @c image{http://monetdb.cwi.nl/projects/monetdb-mk/imgs/bat2,,,,feps}
     707             :  */
     708             : 
     709             : typedef struct PROPrec PROPrec;
     710             : 
     711             : /* see also comment near BATassertProps() for more information about
     712             :  * the properties */
     713             : typedef struct {
     714             :         str id;                 /* label for column */
     715             : 
     716             :         uint16_t width;         /* byte-width of the atom array */
     717             :         int8_t type;            /* type id. */
     718             :         uint8_t shift;          /* log2 of bun width */
     719             :         bool varsized:1,        /* varsized/void (true) or fixedsized (false) */
     720             :                 key:1,          /* no duplicate values present */
     721             :                 nonil:1,        /* there are no nils in the column */
     722             :                 nil:1,          /* there is a nil in the column */
     723             :                 sorted:1,       /* column is sorted in ascending order */
     724             :                 revsorted:1;    /* column is sorted in descending order */
     725             :         BUN nokey[2];           /* positions that prove key==FALSE */
     726             :         BUN nosorted;           /* position that proves sorted==FALSE */
     727             :         BUN norevsorted;        /* position that proves revsorted==FALSE */
     728             :         oid seq;                /* start of dense sequence */
     729             : 
     730             :         Heap *heap;             /* space for the column. */
     731             :         BUN baseoff;            /* offset in heap->base (in whole items) */
     732             :         Heap *vheap;            /* space for the varsized data. */
     733             :         Hash *hash;             /* hash table */
     734             :         Imprints *imprints;     /* column imprints index */
     735             :         Heap *orderidx;         /* order oid index */
     736             : 
     737             :         PROPrec *props;         /* list of dynamic properties stored in the bat descriptor */
     738             : } COLrec;
     739             : 
     740             : #define ORDERIDXOFF             3
     741             : 
     742             : /* assert that atom width is power of 2, i.e., width == 1<<shift */
     743             : #define assert_shift_width(shift,width) assert(((shift) == 0 && (width) == 0) || ((unsigned)1<<(shift)) == (unsigned)(width))
     744             : 
     745             : #define GDKLIBRARY_MINMAX_POS   061042U /* first in Nov2019: no min/max position; no BBPinfo value */
     746             : #define GDKLIBRARY_TAILN        061043U /* first after Oct2020: str offset heaps names don't take width into account */
     747             : /* if the version number is updated, also fix snapshot_bats() in bat_logger.c */
     748             : #define GDKLIBRARY              061044U /* first after Oct2020 */
     749             : 
     750             : typedef struct BAT {
     751             :         /* static bat properties */
     752             :         bat batCacheid;         /* index into BBP */
     753             :         oid hseqbase;           /* head seq base */
     754             : 
     755             :         /* dynamic bat properties */
     756             :         MT_Id creator_tid;      /* which thread created it */
     757             :         bool
     758             :          batCopiedtodisk:1,     /* once written */
     759             :          batDirtyflushed:1,     /* was dirty before commit started? */
     760             :          batDirtydesc:1,        /* bat descriptor dirty marker */
     761             :          batTransient:1;        /* should the BAT persist on disk? */
     762             :         uint8_t /* adjacent bit fields are packed together (if they fit) */
     763             :          batRestricted:2;       /* access privileges */
     764             :         role_t batRole;         /* role of the bat */
     765             :         uint16_t unused;        /* value=0 for now (sneakily used by mat.c) */
     766             :         int batSharecnt;        /* incoming view count */
     767             : 
     768             :         /* delta status administration */
     769             :         BUN batInserted;        /* start of inserted elements */
     770             :         BUN batCount;           /* tuple count */
     771             :         BUN batCapacity;        /* tuple capacity */
     772             : 
     773             :         /* dynamic column properties */
     774             :         COLrec T;               /* column info */
     775             :         MT_Lock theaplock;      /* lock protecting heap reference changes */
     776             :         MT_RWLock thashlock;    /* lock specifically for hash management */
     777             :         MT_Lock batIdxLock;     /* lock to manipulate other indexes/properties */
     778             : } BAT;
     779             : 
     780             : /* macros to hide complexity of the BAT structure */
     781             : #define ttype           T.type
     782             : #define tkey            T.key
     783             : #define tvarsized       T.varsized
     784             : #define tseqbase        T.seq
     785             : #define tsorted         T.sorted
     786             : #define trevsorted      T.revsorted
     787             : #define tident          T.id
     788             : #define torderidx       T.orderidx
     789             : #define twidth          T.width
     790             : #define tshift          T.shift
     791             : #define tnonil          T.nonil
     792             : #define tnil            T.nil
     793             : #define tnokey          T.nokey
     794             : #define tnosorted       T.nosorted
     795             : #define tnorevsorted    T.norevsorted
     796             : #define theap           T.heap
     797             : #define tbaseoff        T.baseoff
     798             : #define tvheap          T.vheap
     799             : #define thash           T.hash
     800             : #define timprints       T.imprints
     801             : #define tprops          T.props
     802             : 
     803             : 
     804             : /* some access functions for the bitmask type */
     805             : static inline void
     806       62737 : mskSet(BAT *b, BUN p)
     807             : {
     808       62737 :         ((uint32_t *) b->theap->base)[p / 32] |= 1U << (p % 32);
     809       62737 : }
     810             : 
     811             : static inline void
     812        9377 : mskClr(BAT *b, BUN p)
     813             : {
     814        9377 :         ((uint32_t *) b->theap->base)[p / 32] &= ~(1U << (p % 32));
     815        9377 : }
     816             : 
     817             : static inline void
     818       12303 : mskSetVal(BAT *b, BUN p, msk v)
     819             : {
     820       12303 :         if (v)
     821       62737 :                 mskSet(b, p);
     822             :         else
     823        9377 :                 mskClr(b, p);
     824       12303 : }
     825             : 
     826             : static inline msk
     827             : mskGetVal(BAT *b, BUN p)
     828             : {
     829           0 :         return ((uint32_t *) b->theap->base)[p / 32] & (1U << (p % 32));
     830             : }
     831             : 
     832             : /*
     833             :  * @- Heap Management
     834             :  * Heaps are the low-level entities of mass storage in
     835             :  * BATs. Currently, they can either be stored on disk, loaded into
     836             :  * memory, or memory mapped.
     837             :  * @multitable @columnfractions 0.08 0.7
     838             :  * @item int
     839             :  * @tab
     840             :  *  HEAPalloc (Heap *h, size_t nitems, size_t itemsize);
     841             :  * @item int
     842             :  * @tab
     843             :  *  HEAPfree (Heap *h, bool remove);
     844             :  * @item int
     845             :  * @tab
     846             :  *  HEAPextend (Heap *h, size_t size, bool mayshare);
     847             :  * @item int
     848             :  * @tab
     849             :  *  HEAPload (Heap *h, str nme,ext, bool trunc);
     850             :  * @item int
     851             :  * @tab
     852             :  *  HEAPsave (Heap *h, str nme,ext, bool dosync);
     853             :  * @item int
     854             :  * @tab
     855             :  *  HEAPcopy (Heap *dst,*src);
     856             :  * @item int
     857             :  * @tab
     858             :  *  HEAPwarm (Heap *h);
     859             :  * @end multitable
     860             :  *
     861             :  *
     862             :  * These routines should be used to alloc free or extend heaps; they
     863             :  * isolate you from the different ways heaps can be accessed.
     864             :  */
     865             : gdk_export gdk_return HEAPextend(Heap *h, size_t size, bool mayshare)
     866             :         __attribute__((__warn_unused_result__));
     867             : gdk_export size_t HEAPvmsize(Heap *h);
     868             : gdk_export size_t HEAPmemsize(Heap *h);
     869             : gdk_export void HEAPdecref(Heap *h, bool remove);
     870             : gdk_export void HEAPincref(Heap *h);
     871             : 
     872             : /* BAT iterator, also protects use of BAT heaps with reference counts.
     873             :  *
     874             :  * A BAT iterator has to be used with caution, but it does have to be
     875             :  * used in many place.
     876             :  *
     877             :  * An iterator is initialized by assigning it the result of a call to
     878             :  * either bat_iterator or bat_iterator_nolock.  The former must be
     879             :  * accompanied by a call to bat_iterator_end to release resources.
     880             :  *
     881             :  * bat_iterator should be used for BATs that could possibly be modified
     882             :  * in another thread while we're reading the contents of the BAT.
     883             :  * Alternatively, but only for very quick access, the theaplock can be
     884             :  * taken, the data read, and the lock released.  For longer duration
     885             :  * accesses, it is better to use the iterator, even without the BUNt*
     886             :  * macros, since the theaplock is only held very briefly.
     887             :  *
     888             :  * Note, bat_iterator must only be used for read-only access.
     889             :  *
     890             :  * If BATs are to be modified, higher level code must assure that no
     891             :  * other thread is going to modify the same BAT at the same time.  A
     892             :  * to-be-modified BAT should not use bat_iterator.  It can use
     893             :  * bat_iterator_nolock, but be aware that this creates a copy of the
     894             :  * heap pointer(s) (i.e. theap and tvheap) and if the heaps get
     895             :  * extended, the pointers in the BAT structure may be modified, but that
     896             :  * does not modify the pointers in the iterator.  This means that after
     897             :  * operations that may grow a heap, the iterator should be
     898             :  * reinitialized.
     899             :  *
     900             :  * The BAT iterator provides a number of fields that can (and often
     901             :  * should) be used to access information about the BAT.  For string
     902             :  * BATs, if a parallel threads adds values, the offset heap (theap) may
     903             :  * get replaced by a one that is wider.  This involves changing the
     904             :  * twidth and tshift values in the BAT structure.  These changed values
     905             :  * should not be used to access the data in the iterator.  Instead, use
     906             :  * the width and shift values in the iterator itself.
     907             :  */
     908             : typedef struct BATiter {
     909             :         BAT *b;
     910             :         Heap *h;
     911             :         void *base;
     912             :         Heap *vh;
     913             :         BUN count;
     914             :         uint16_t width;
     915             :         uint8_t shift;
     916             :         int8_t type;
     917             :         oid tseq;
     918             :         BUN hfree, vhfree;
     919             :         union {
     920             :                 oid tvid;
     921             :                 bool tmsk;
     922             :         };
     923             : #ifndef NDEBUG
     924             :         bool locked;
     925             : #endif
     926             : } BATiter;
     927             : 
     928             : static inline BATiter
     929    19367548 : bat_iterator(BAT *b)
     930             : {
     931             :         /* needs matching bat_iterator_end */
     932             :         BATiter bi;
     933    19367548 :         if (b) {
     934    15541405 :                 MT_lock_set(&b->theaplock);
     935    15592967 :                 bi = (BATiter) {
     936             :                         .b = b,
     937    15592967 :                         .h = b->theap,
     938    15592967 :                         .base = b->theap->base ? b->theap->base + (b->tbaseoff << b->tshift) : NULL,
     939    15592967 :                         .vh = b->tvheap,
     940    15592967 :                         .count = b->batCount,
     941    15592967 :                         .width = b->twidth,
     942    15592967 :                         .shift = b->tshift,
     943    15592967 :                         .type = b->ttype,
     944    15592967 :                         .tseq = b->tseqbase,
     945    15592967 :                         .hfree = b->theap->free,
     946    15592967 :                         .vhfree = b->tvheap ? b->tvheap->free : 0,
     947             : #ifndef NDEBUG
     948             :                         .locked = true,
     949             : #endif
     950             :                 };
     951    15592967 :                 HEAPincref(bi.h);
     952    15592810 :                 if (bi.vh)
     953     4398910 :                         HEAPincref(bi.vh);
     954    15592445 :                 MT_lock_unset(&b->theaplock);
     955             :         } else {
     956     3826143 :                 bi = (BATiter) {
     957             :                         .b = NULL,
     958             : #ifndef NDEBUG
     959             :                         .locked = true,
     960             : #endif
     961             :                 };
     962             :         }
     963    19424729 :         return bi;
     964             : }
     965             : 
     966             : static inline void
     967    19345597 : bat_iterator_end(BATiter *bip)
     968             : {
     969             :         /* matches bat_iterator */
     970    19345597 :         assert(bip);
     971    19345597 :         assert(bip->locked);
     972    19345597 :         if (bip->h)
     973    15541449 :                 HEAPdecref(bip->h, false);
     974    19366618 :         if (bip->vh)
     975     4400239 :                 HEAPdecref(bip->vh, false);
     976    19365720 :         *bip = (BATiter) {0};
     977    19365720 : }
     978             : 
     979             : static inline BATiter
     980    91010316 : bat_iterator_nolock(BAT *b)
     981             : {
     982             :         /* does not get matched by bat_iterator_end */
     983    91010316 :         if (b) {
     984    91010316 :                 return (BATiter) {
     985             :                         .b = b,
     986    91010316 :                         .h = b->theap,
     987    91010316 :                         .base = b->theap->base ? b->theap->base + (b->tbaseoff << b->tshift) : NULL,
     988    91010316 :                         .vh = b->tvheap,
     989    91010316 :                         .count = b->batCount,
     990    91010316 :                         .width = b->twidth,
     991    91010316 :                         .shift = b->tshift,
     992    91010316 :                         .type = b->ttype,
     993    91010316 :                         .tseq = b->tseqbase,
     994    91010316 :                         .hfree = b->theap->free,
     995    91010316 :                         .vhfree = b->tvheap ? b->tvheap->free : 0,
     996             : #ifndef NDEBUG
     997             :                         .locked = false,
     998             : #endif
     999             :                 };
    1000             :         }
    1001           0 :         return (BATiter) {0};
    1002             : }
    1003             : 
    1004             : /*
    1005             :  * @- Internal HEAP Chunk Management
    1006             :  * Heaps are used in BATs to store data for variable-size atoms.  The
    1007             :  * implementor must manage malloc()/free() functionality for atoms in
    1008             :  * this heap. A standard implementation is provided here.
    1009             :  *
    1010             :  * @table @code
    1011             :  * @item void
    1012             :  * HEAP_initialize  (Heap* h, size_t nbytes, size_t nprivate, int align )
    1013             :  * @item void
    1014             :  * HEAP_destroy     (Heap* h)
    1015             :  * @item var_t
    1016             :  * HEAP_malloc      (Heap* heap, size_t nbytes)
    1017             :  * @item void
    1018             :  * HEAP_free        (Heap *heap, var_t block)
    1019             :  * @item int
    1020             :  * HEAP_private     (Heap* h)
    1021             :  * @item void
    1022             :  * HEAP_printstatus (Heap* h)
    1023             :  * @end table
    1024             :  *
    1025             :  * The heap space starts with a private space that is left untouched
    1026             :  * by the normal chunk allocation.  You can use this private space
    1027             :  * e.g. to store the root of an rtree HEAP_malloc allocates a chunk of
    1028             :  * memory on the heap, and returns an index to it.  HEAP_free frees a
    1029             :  * previously allocated chunk HEAP_private returns an integer index to
    1030             :  * private space.
    1031             :  */
    1032             : 
    1033             : gdk_export void HEAP_initialize(
    1034             :         Heap *heap,             /* nbytes -- Initial size of the heap. */
    1035             :         size_t nbytes,          /* alignment -- for objects on the heap. */
    1036             :         size_t nprivate,        /* nprivate -- Size of private space */
    1037             :         int alignment           /* alignment restriction for allocated chunks */
    1038             :         );
    1039             : 
    1040             : gdk_export var_t HEAP_malloc(BAT *b, size_t nbytes);
    1041             : gdk_export void HEAP_free(Heap *heap, var_t block);
    1042             : 
    1043             : /*
    1044             :  * @- BAT construction
    1045             :  * @multitable @columnfractions 0.08 0.7
    1046             :  * @item @code{BAT* }
    1047             :  * @tab COLnew (oid headseq, int tailtype, BUN cap, role_t role)
    1048             :  * @item @code{BAT* }
    1049             :  * @tab BATextend (BAT *b, BUN newcap)
    1050             :  * @end multitable
    1051             :  *
    1052             :  * A temporary BAT is instantiated using COLnew with the type aliases
    1053             :  * of the required binary association. The aliases include the
    1054             :  * built-in types, such as TYPE_int....TYPE_ptr, and the atomic types
    1055             :  * introduced by the user. The initial capacity to be accommodated
    1056             :  * within a BAT is indicated by cap.  Their extend is automatically
    1057             :  * incremented upon storage overflow.  Failure to create the BAT
    1058             :  * results in a NULL pointer.
    1059             :  *
    1060             :  * The routine BATclone creates an empty BAT storage area with the
    1061             :  * properties inherited from its argument.
    1062             :  */
    1063             : gdk_export BAT *COLnew(oid hseq, int tltype, BUN capacity, role_t role)
    1064             :         __attribute__((__warn_unused_result__));
    1065             : gdk_export BAT *BATdense(oid hseq, oid tseq, BUN cnt)
    1066             :         __attribute__((__warn_unused_result__));
    1067             : gdk_export gdk_return BATextend(BAT *b, BUN newcap)
    1068             :         __attribute__((__warn_unused_result__));
    1069             : 
    1070             : /* internal */
    1071             : gdk_export uint8_t ATOMelmshift(int sz)
    1072             :         __attribute__((__const__));
    1073             : 
    1074             : gdk_export gdk_return GDKupgradevarheap(BAT *b, var_t v, BUN cap, BUN ncopy)
    1075             :         __attribute__((__warn_unused_result__));
    1076             : gdk_export gdk_return BUNappend(BAT *b, const void *right, bool force)
    1077             :         __attribute__((__warn_unused_result__));
    1078             : gdk_export gdk_return BUNappendmulti(BAT *b, const void *values, BUN count, bool force)
    1079             :         __attribute__((__warn_unused_result__));
    1080             : gdk_export gdk_return BATappend(BAT *b, BAT *n, BAT *s, bool force)
    1081             :         __attribute__((__warn_unused_result__));
    1082             : 
    1083             : gdk_export gdk_return BUNreplace(BAT *b, oid left, const void *right, bool force)
    1084             :         __attribute__((__warn_unused_result__));
    1085             : gdk_export gdk_return BUNreplacemulti(BAT *b, const oid *positions, const void *values, BUN count, bool force)
    1086             :         __attribute__((__warn_unused_result__));
    1087             : gdk_export gdk_return BUNreplacemultiincr(BAT *b, oid position, const void *values, BUN count, bool force)
    1088             :         __attribute__((__warn_unused_result__));
    1089             : 
    1090             : gdk_export gdk_return BUNdelete(BAT *b, oid o)
    1091             :         __attribute__((__warn_unused_result__));
    1092             : gdk_export gdk_return BATdel(BAT *b, BAT *d)
    1093             :         __attribute__((__warn_unused_result__));
    1094             : 
    1095             : gdk_export gdk_return BATreplace(BAT *b, BAT *p, BAT *n, bool force)
    1096             :         __attribute__((__warn_unused_result__));
    1097             : gdk_export gdk_return BATupdate(BAT *b, BAT *p, BAT *n, bool force)
    1098             :         __attribute__((__warn_unused_result__));
    1099             : gdk_export gdk_return BATreplacepos(BAT *b, const oid *positions, BAT *n, bool autoincr, bool force)
    1100             :         __attribute__((__warn_unused_result__));
    1101             : gdk_export gdk_return BATupdatepos(BAT *b, const oid *positions, BAT *n, bool autoincr, bool force)
    1102             :         __attribute__((__warn_unused_result__));
    1103             : 
    1104             : /* Functions to perform a binary search on a sorted BAT.
    1105             :  * See gdk_search.c for details. */
    1106             : gdk_export BUN SORTfnd(BAT *b, const void *v);
    1107             : gdk_export BUN SORTfndfirst(BAT *b, const void *v);
    1108             : gdk_export BUN SORTfndlast(BAT *b, const void *v);
    1109             : 
    1110             : gdk_export BUN ORDERfnd(BAT *b, Heap *oidxh, const void *v);
    1111             : gdk_export BUN ORDERfndfirst(BAT *b, Heap *oidxh, const void *v);
    1112             : gdk_export BUN ORDERfndlast(BAT *b, Heap *oidxh, const void *v);
    1113             : 
    1114             : gdk_export BUN BUNfnd(BAT *b, const void *right);
    1115             : 
    1116             : #define BUNfndVOID(b, v)                                                \
    1117             :         (((is_oid_nil(*(const oid*)(v)) ^ is_oid_nil((b)->tseqbase)) |       \
    1118             :                 (*(const oid*)(v) < (b)->tseqbase) |                      \
    1119             :                 (*(const oid*)(v) >= (b)->tseqbase + (b)->batCount)) ? \
    1120             :          BUN_NONE :                                                     \
    1121             :          (BUN) (*(const oid*)(v) - (b)->tseqbase))
    1122             : 
    1123             : #define BATttype(b)     (BATtdense(b) ? TYPE_oid : (b)->ttype)
    1124             : 
    1125             : #define Tsize(b)        ((b)->twidth)
    1126             : 
    1127             : #define tailsize(b,p)   ((b)->ttype ?                                \
    1128             :                          (ATOMstorage((b)->ttype) == TYPE_msk ?      \
    1129             :                           (((size_t) (p) + 31) / 32) * 4 :      \
    1130             :                           ((size_t) (p)) << (b)->tshift) :     \
    1131             :                          0)
    1132             : 
    1133             : #define Tloc(b,p)       ((void *)((b)->theap->base+(((size_t)(p)+(b)->tbaseoff)<<(b)->tshift)))
    1134             : 
    1135             : typedef var_t stridx_t;
    1136             : #define SIZEOF_STRIDX_T SIZEOF_VAR_T
    1137             : #define GDK_VARALIGN SIZEOF_STRIDX_T
    1138             : 
    1139             : #define BUNtvaroff(bi,p) VarHeapVal((bi).base, (p), (bi).width)
    1140             : 
    1141             : #define BUNtloc(bi,p)   (ATOMstorage((bi).type) == TYPE_msk ? Tmsk(&(bi), p) : (void *) ((char *) (bi).base + ((p) << (bi).shift)))
    1142             : #define BUNtpos(bi,p)   Tpos(&(bi),p)
    1143             : #define BUNtvar(bi,p)   (assert((bi).type && (bi).b->tvarsized), (void *) ((bi).vh->base+BUNtvaroff(bi,p)))
    1144             : #define BUNtail(bi,p)   ((bi).type?(bi).b->tvarsized?BUNtvar(bi,p):BUNtloc(bi,p):BUNtpos(bi,p))
    1145             : 
    1146             : #define BUNlast(b)      (assert((b)->batCount <= BUN_MAX), (b)->batCount)
    1147             : 
    1148             : #define BATcount(b)     ((b)->batCount)
    1149             : 
    1150             : #include "gdk_atoms.h"
    1151             : 
    1152             : #include "gdk_cand.h"
    1153             : 
    1154             : /*
    1155             :  * @- BAT properties
    1156             :  * @multitable @columnfractions 0.08 0.7
    1157             :  * @item BUN
    1158             :  * @tab BATcount (BAT *b)
    1159             :  * @item void
    1160             :  * @tab BATsetcapacity (BAT *b, BUN cnt)
    1161             :  * @item void
    1162             :  * @tab BATsetcount (BAT *b, BUN cnt)
    1163             :  * @item BAT *
    1164             :  * @tab BATkey (BAT *b, bool onoff)
    1165             :  * @item BAT *
    1166             :  * @tab BATmode (BAT *b, bool transient)
    1167             :  * @item BAT *
    1168             :  * @tab BATsetaccess (BAT *b, restrict_t mode)
    1169             :  * @item int
    1170             :  * @tab BATdirty (BAT *b)
    1171             :  * @item restrict_t
    1172             :  * @tab BATgetaccess (BAT *b)
    1173             :  * @end multitable
    1174             :  *
    1175             :  * The function BATcount returns the number of associations stored in
    1176             :  * the BAT.
    1177             :  *
    1178             :  * The BAT is given a new logical name using BBPrename.
    1179             :  *
    1180             :  * The integrity properties to be maintained for the BAT are
    1181             :  * controlled separately.  A key property indicates that duplicates in
    1182             :  * the association dimension are not permitted.
    1183             :  *
    1184             :  * The persistency indicator tells the retention period of BATs.  The
    1185             :  * system support two modes: PERSISTENT and TRANSIENT.
    1186             :  * The PERSISTENT BATs are automatically saved upon session boundary
    1187             :  * or transaction commit.  TRANSIENT BATs are removed upon transaction
    1188             :  * boundary.  All BATs are initially TRANSIENT unless their mode is
    1189             :  * changed using the routine BATmode.
    1190             :  *
    1191             :  * The BAT properties may be changed at any time using BATkey
    1192             :  * and BATmode.
    1193             :  *
    1194             :  * Valid BAT access properties can be set with BATsetaccess and
    1195             :  * BATgetaccess: BAT_READ, BAT_APPEND, and BAT_WRITE.  BATs can be
    1196             :  * designated to be read-only. In this case some memory optimizations
    1197             :  * may be made (slice and fragment bats can point to stable subsets of
    1198             :  * a parent bat).  A special mode is append-only. It is then allowed
    1199             :  * to insert BUNs at the end of the BAT, but not to modify anything
    1200             :  * that already was in there.
    1201             :  */
    1202             : gdk_export BUN BATcount_no_nil(BAT *b, BAT *s);
    1203             : gdk_export void BATsetcapacity(BAT *b, BUN cnt);
    1204             : gdk_export void BATsetcount(BAT *b, BUN cnt);
    1205             : gdk_export BUN BATgrows(BAT *b);
    1206             : gdk_export gdk_return BATkey(BAT *b, bool onoff);
    1207             : gdk_export gdk_return BATmode(BAT *b, bool transient);
    1208             : gdk_export gdk_return BATroles(BAT *b, const char *tnme);
    1209             : gdk_export void BAThseqbase(BAT *b, oid o);
    1210             : gdk_export void BATtseqbase(BAT *b, oid o);
    1211             : 
    1212             : /* The batRestricted field indicates whether a BAT is readonly.
    1213             :  * we have modes: BAT_WRITE  = all permitted
    1214             :  *                BAT_APPEND = append-only
    1215             :  *                BAT_READ   = read-only
    1216             :  * VIEW bats are always mapped read-only.
    1217             :  */
    1218             : typedef enum {
    1219             :         BAT_WRITE,                /* all kinds of access allowed */
    1220             :         BAT_READ,                 /* only read-access allowed */
    1221             :         BAT_APPEND,               /* only reads and appends allowed */
    1222             : } restrict_t;
    1223             : 
    1224             : gdk_export BAT *BATsetaccess(BAT *b, restrict_t mode)
    1225             :         __attribute__((__warn_unused_result__));
    1226             : gdk_export restrict_t BATgetaccess(BAT *b);
    1227             : 
    1228             : 
    1229             : #define BATdirty(b)     (!(b)->batCopiedtodisk ||                    \
    1230             :                          (b)->batDirtydesc ||                                \
    1231             :                          (b)->theap->dirty ||                             \
    1232             :                          ((b)->tvheap != NULL && (b)->tvheap->dirty))
    1233             : #define BATdirtydata(b) (!(b)->batCopiedtodisk ||                    \
    1234             :                          (b)->theap->dirty ||                             \
    1235             :                          ((b)->tvheap != NULL && (b)->tvheap->dirty))
    1236             : 
    1237             : #define BATcapacity(b)  (b)->batCapacity
    1238             : /*
    1239             :  * @- BAT manipulation
    1240             :  * @multitable @columnfractions 0.08 0.7
    1241             :  * @item BAT *
    1242             :  * @tab BATclear (BAT *b, bool force)
    1243             :  * @item BAT *
    1244             :  * @tab COLcopy (BAT *b, int tt, bool writeable, role_t role)
    1245             :  * @end multitable
    1246             :  *
    1247             :  * The routine BATclear removes the binary associations, leading to an
    1248             :  * empty, but (re-)initialized BAT. Its properties are retained.  A
    1249             :  * temporary copy is obtained with Colcopy. The new BAT has an unique
    1250             :  * name.
    1251             :  */
    1252             : gdk_export gdk_return BATclear(BAT *b, bool force);
    1253             : gdk_export BAT *COLcopy(BAT *b, int tt, bool writable, role_t role);
    1254             : 
    1255             : gdk_export gdk_return BATgroup(BAT **groups, BAT **extents, BAT **histo, BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
    1256             :         __attribute__((__warn_unused_result__));
    1257             : 
    1258             : /*
    1259             :  * @- BAT Input/Output
    1260             :  * @multitable @columnfractions 0.08 0.7
    1261             :  * @item BAT *
    1262             :  * @tab BATload (str name)
    1263             :  * @item BAT *
    1264             :  * @tab BATsave (BAT *b)
    1265             :  * @item int
    1266             :  * @tab BATdelete (BAT *b)
    1267             :  * @end multitable
    1268             :  *
    1269             :  * A BAT created by COLnew is considered temporary until one calls the
    1270             :  * routine BATsave or BATmode.  This routine reserves disk space and
    1271             :  * checks for name clashes in the BAT directory. It also makes the BAT
    1272             :  * persistent. The empty BAT is initially marked as ordered on both
    1273             :  * columns.
    1274             :  *
    1275             :  * Failure to read or write the BAT results in a NULL, otherwise it
    1276             :  * returns the BAT pointer.
    1277             :  *
    1278             :  * @- Heap Storage Modes
    1279             :  * The discriminative storage modes are memory-mapped, compressed, or
    1280             :  * loaded in memory.  As can be seen in the bat record, each BAT has
    1281             :  * one BUN-heap (@emph{bn}), and possibly two heaps (@emph{hh} and
    1282             :  * @emph{th}) for variable-sized atoms.
    1283             :  */
    1284             : 
    1285             : gdk_export gdk_return BATsave(BAT *b)
    1286             :         __attribute__((__warn_unused_result__));
    1287             : gdk_export void BATmsync(BAT *b);
    1288             : 
    1289             : #define NOFARM (-1) /* indicate to GDKfilepath to create relative path */
    1290             : 
    1291             : gdk_export char *GDKfilepath(int farmid, const char *dir, const char *nme, const char *ext);
    1292             : gdk_export bool GDKinmemory(int farmid);
    1293             : gdk_export bool GDKembedded(void);
    1294             : gdk_export gdk_return GDKcreatedir(const char *nme);
    1295             : 
    1296             : gdk_export void OIDXdestroy(BAT *b);
    1297             : 
    1298             : /*
    1299             :  * @- Printing
    1300             :  * @multitable @columnfractions 0.08 0.7
    1301             :  * @item int
    1302             :  * @tab BATprintcolumns (stream *f, int argc, BAT *b[]);
    1303             :  * @end multitable
    1304             :  *
    1305             :  * The functions to convert BATs into ASCII. They are primarily meant for ease of
    1306             :  * debugging and to a lesser extent for output processing.  Printing a
    1307             :  * BAT is done essentially by looping through its components, printing
    1308             :  * each association.
    1309             :  *
    1310             :  */
    1311             : gdk_export gdk_return BATprintcolumns(stream *s, int argc, BAT *argv[]);
    1312             : gdk_export gdk_return BATprint(stream *s, BAT *b);
    1313             : 
    1314             : /*
    1315             :  * @- BAT clustering
    1316             :  * @multitable @columnfractions 0.08 0.7
    1317             :  * @item bool
    1318             :  * @tab BATordered (BAT *b)
    1319             :  * @end multitable
    1320             :  *
    1321             :  * When working in a main-memory situation, clustering of data on
    1322             :  * disk-pages is not important. Whenever mmap()-ed data is used
    1323             :  * intensively, reducing the number of page faults is a hot issue.
    1324             :  *
    1325             :  * The above functions rearrange data in MonetDB heaps (used for
    1326             :  * storing BUNs var-sized atoms, or accelerators). Applying these
    1327             :  * clusterings will allow that MonetDB's main-memory oriented
    1328             :  * algorithms work efficiently also in a disk-oriented context.
    1329             :  *
    1330             :  * BATordered starts a check on the tail values to see if they are
    1331             :  * ordered. The result is returned and stored in the tsorted field of
    1332             :  * the BAT.
    1333             :  */
    1334             : gdk_export bool BATordered(BAT *b);
    1335             : gdk_export bool BATordered_rev(BAT *b);
    1336             : gdk_export gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, bool reverse, bool nilslast, bool stable)
    1337             :         __attribute__((__warn_unused_result__));
    1338             : 
    1339             : 
    1340             : gdk_export void GDKqsort(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast);
    1341             : 
    1342             : #define BATtordered(b)  ((b)->tsorted)
    1343             : #define BATtrevordered(b) ((b)->trevsorted)
    1344             : /* BAT is dense (i.e., BATtvoid() is true and tseqbase is not NIL) */
    1345             : #define BATtdense(b)    (!is_oid_nil((b)->tseqbase) &&                       \
    1346             :                          ((b)->tvheap == NULL || (b)->tvheap->free == 0))
    1347             : /* BATtvoid: BAT can be (or actually is) represented by TYPE_void */
    1348             : #define BATtvoid(b)     (BATtdense(b) || (b)->ttype==TYPE_void)
    1349             : #define BATtkey(b)      ((b)->tkey || BATtdense(b))
    1350             : 
    1351             : /* set some properties that are trivial to deduce */
    1352             : static inline void
    1353    24704792 : BATsettrivprop(BAT *b)
    1354             : {
    1355    24704792 :         assert(!is_oid_nil(b->hseqbase));
    1356    24704792 :         assert(is_oid_nil(b->tseqbase) || ATOMtype(b->ttype) == TYPE_oid);
    1357    24704792 :         if (!b->batDirtydesc)
    1358             :                 return;
    1359    24704792 :         if (b->ttype == TYPE_void) {
    1360     2714367 :                 if (is_oid_nil(b->tseqbase)) {
    1361        7273 :                         b->tnonil = b->batCount == 0;
    1362        7273 :                         b->tnil = !b->tnonil;
    1363        7273 :                         b->trevsorted = true;
    1364        7273 :                         b->tkey = b->batCount <= 1;
    1365             :                 } else {
    1366     2707094 :                         b->tnonil = true;
    1367     2707094 :                         b->tnil = false;
    1368     2707094 :                         b->tkey = true;
    1369     2707094 :                         b->trevsorted = b->batCount <= 1;
    1370             :                 }
    1371     2714367 :                 b->tsorted = true;
    1372    21990425 :         } else if (b->batCount <= 1) {
    1373     6269080 :                 if (ATOMlinear(b->ttype)) {
    1374     6267110 :                         b->tsorted = true;
    1375     6267110 :                         b->trevsorted = true;
    1376             :                 }
    1377     6269080 :                 b->tkey = true;
    1378     6269080 :                 if (b->batCount == 0) {
    1379     4984977 :                         b->tnonil = true;
    1380     4984977 :                         b->tnil = false;
    1381     4984977 :                         if (b->ttype == TYPE_oid) {
    1382      229313 :                                 b->tseqbase = 0;
    1383             :                         }
    1384     1284103 :                 } else if (b->ttype == TYPE_oid) {
    1385             :                         /* b->batCount == 1 */
    1386      139965 :                         oid sqbs = ((const oid *) b->theap->base)[b->tbaseoff];
    1387      139965 :                         if (is_oid_nil(sqbs)) {
    1388         487 :                                 b->tnonil = false;
    1389         487 :                                 b->tnil = true;
    1390             :                         } else {
    1391      139478 :                                 b->tnonil = true;
    1392      139478 :                                 b->tnil = false;
    1393             :                         }
    1394      139965 :                         b->tseqbase = sqbs;
    1395             :                 }
    1396    15721345 :         } else if (b->batCount == 2 && ATOMlinear(b->ttype)) {
    1397             :                 int c;
    1398      308339 :                 if (b->tvarsized)
    1399       55849 :                         c = ATOMcmp(b->ttype,
    1400             :                                     b->tvheap->base + VarHeapVal(Tloc(b, 0), 0, b->twidth),
    1401             :                                     b->tvheap->base + VarHeapVal(Tloc(b, 0), 1, b->twidth));
    1402             :                 else
    1403      252490 :                         c = ATOMcmp(b->ttype, Tloc(b, 0), Tloc(b, 1));
    1404      307704 :                 b->tsorted = c <= 0;
    1405      307704 :                 b->tnosorted = !b->tsorted;
    1406      307704 :                 b->trevsorted = c >= 0;
    1407      307704 :                 b->tnorevsorted = !b->trevsorted;
    1408      307704 :                 b->tkey = c != 0;
    1409      307704 :                 b->tnokey[0] = 0;
    1410      307704 :                 b->tnokey[1] = !b->tkey;
    1411    15413006 :         } else if (!ATOMlinear(b->ttype)) {
    1412           0 :                 b->tsorted = false;
    1413           0 :                 b->trevsorted = false;
    1414             :         }
    1415             : }
    1416             : 
    1417             : /*
    1418             :  * @+ BAT Buffer Pool
    1419             :  * @multitable @columnfractions 0.08 0.7
    1420             :  * @item int
    1421             :  * @tab BBPfix (bat bi)
    1422             :  * @item int
    1423             :  * @tab BBPunfix (bat bi)
    1424             :  * @item int
    1425             :  * @tab BBPretain (bat bi)
    1426             :  * @item int
    1427             :  * @tab BBPrelease (bat bi)
    1428             :  * @item str
    1429             :  * @tab BBPname (bat bi)
    1430             :  * @item bat
    1431             :  * @tab BBPindex  (str nme)
    1432             :  * @item BAT*
    1433             :  * @tab BATdescriptor (bat bi)
    1434             :  * @end multitable
    1435             :  *
    1436             :  * The BAT Buffer Pool module contains the code to manage the storage
    1437             :  * location of BATs.
    1438             :  *
    1439             :  * The remaining BBP tables contain status information to load, swap
    1440             :  * and migrate the BATs. The core table is BBPcache which contains a
    1441             :  * pointer to the BAT descriptor with its heaps.  A zero entry means
    1442             :  * that the file resides on disk. Otherwise it has been read or mapped
    1443             :  * into memory.
    1444             :  *
    1445             :  * BATs loaded into memory are retained in a BAT buffer pool.  They
    1446             :  * retain their position within the cache during their life cycle,
    1447             :  * which make indexing BATs a stable operation.
    1448             :  *
    1449             :  * The BBPindex routine checks if a BAT with a certain name is
    1450             :  * registered in the buffer pools. If so, it returns its BAT id.  The
    1451             :  * BATdescriptor routine has a BAT id parameter, and returns a pointer
    1452             :  * to the corresponding BAT record (after incrementing the reference
    1453             :  * count). The BAT will be loaded into memory, if necessary.
    1454             :  *
    1455             :  * The structure of the BBP file obeys the tuple format for GDK.
    1456             :  *
    1457             :  * The status and BAT persistency information is encoded in the status
    1458             :  * field.
    1459             :  */
    1460             : typedef struct {
    1461             :         BAT *cache;             /* if loaded: BAT* handle */
    1462             :         char *logical;          /* logical name (may point at bak) */
    1463             :         char bak[16];           /* logical name backup (tmp_%o) */
    1464             :         BAT *desc;              /* the BAT descriptor */
    1465             :         char *options;          /* A string list of options */
    1466             : #if SIZEOF_VOID_P == 4
    1467             :         char physical[20];      /* dir + basename for storage */
    1468             : #else
    1469             :         char physical[24];      /* dir + basename for storage */
    1470             : #endif
    1471             :         bat next;               /* next BBP slot in linked list */
    1472             :         int refs;               /* in-memory references on which the loaded status of a BAT relies */
    1473             :         int lrefs;              /* logical references on which the existence of a BAT relies */
    1474             :         ATOMIC_TYPE status;     /* status mask used for spin locking */
    1475             :         MT_Id pid;              /* creator of this bat while "private" */
    1476             : } BBPrec;
    1477             : 
    1478             : gdk_export bat BBPlimit;
    1479             : #if SIZEOF_VOID_P == 4
    1480             : #define N_BBPINIT       1000
    1481             : #define BBPINITLOG      11
    1482             : #else
    1483             : #define N_BBPINIT       10000
    1484             : #define BBPINITLOG      14
    1485             : #endif
    1486             : #define BBPINIT         (1 << BBPINITLOG)
    1487             : /* absolute maximum number of BATs is N_BBPINIT * BBPINIT
    1488             :  * this also gives the longest possible "physical" name and "bak" name
    1489             :  * of a BAT: the "bak" name is "tmp_%o", so at most 14 + \0 bytes on
    1490             :  * 64 bit architecture and 11 + \0 on 32 bit architecture; the
    1491             :  * physical name is a bit more complicated, but the longest possible
    1492             :  * name is 22 + \0 bytes (16 + \0 on 32 bits) */
    1493             : gdk_export BBPrec *BBP[N_BBPINIT];
    1494             : 
    1495             : /* fast defines without checks; internal use only  */
    1496             : #define BBP_record(i)   BBP[(i)>>BBPINITLOG][(i)&(BBPINIT-1)]
    1497             : #define BBP_cache(i)    BBP_record(i).cache
    1498             : #define BBP_logical(i)  BBP_record(i).logical
    1499             : #define BBP_bak(i)      BBP_record(i).bak
    1500             : #define BBP_next(i)     BBP_record(i).next
    1501             : #define BBP_physical(i) BBP_record(i).physical
    1502             : #define BBP_options(i)  BBP_record(i).options
    1503             : #define BBP_desc(i)     BBP_record(i).desc
    1504             : #define BBP_refs(i)     BBP_record(i).refs
    1505             : #define BBP_lrefs(i)    BBP_record(i).lrefs
    1506             : #define BBP_status(i)   ((unsigned) ATOMIC_GET(&BBP_record(i).status))
    1507             : #define BBP_pid(i)      BBP_record(i).pid
    1508             : #define BATgetId(b)     BBP_logical((b)->batCacheid)
    1509             : #define BBPvalid(i)     (BBP_logical(i) != NULL && *BBP_logical(i) != '.')
    1510             : 
    1511             : /* macros that nicely check parameters */
    1512             : #define BBPstatus(i)    (BBPcheck(i) ? BBP_status(i) : 0)
    1513             : #define BBPrefs(i)      (BBPcheck(i) ? BBP_refs(i) : -1)
    1514             : #define BBPcache(i)     (BBPcheck(i) ? BBP_cache(i) : (BAT*) NULL)
    1515             : #define BBPname(i)      (BBPcheck(i) ? BBP_logical(i) : "")
    1516             : 
    1517             : #define BBPRENAME_ALREADY       (-1)
    1518             : #define BBPRENAME_ILLEGAL       (-2)
    1519             : #define BBPRENAME_LONG          (-3)
    1520             : #define BBPRENAME_MEMORY        (-4)
    1521             : 
    1522             : gdk_export void BBPlock(void);
    1523             : 
    1524             : gdk_export void BBPunlock(void);
    1525             : 
    1526             : gdk_export BAT *BBPquickdesc(bat b);
    1527             : 
    1528             : /*
    1529             :  * @- GDK error handling
    1530             :  *  @multitable @columnfractions 0.08 0.7
    1531             :  * @item str
    1532             :  * @tab
    1533             :  *  GDKmessage
    1534             :  * @item bit
    1535             :  * @tab
    1536             :  *  GDKfatal(str msg)
    1537             :  * @item int
    1538             :  * @tab
    1539             :  *  GDKwarning(str msg)
    1540             :  * @item int
    1541             :  * @tab
    1542             :  *  GDKerror (str msg)
    1543             :  * @item int
    1544             :  * @tab
    1545             :  *  GDKgoterrors ()
    1546             :  * @item int
    1547             :  * @tab
    1548             :  *  GDKsyserror (str msg)
    1549             :  * @item str
    1550             :  * @tab
    1551             :  *  GDKerrbuf
    1552             :  *  @item
    1553             :  * @tab GDKsetbuf (str buf)
    1554             :  * @end multitable
    1555             :  *
    1556             :  * The error handling mechanism is not sophisticated yet. Experience
    1557             :  * should show if this mechanism is sufficient.  Most routines return
    1558             :  * a pointer with zero to indicate an error.
    1559             :  *
    1560             :  * The error messages are also copied to standard output.  The last
    1561             :  * error message is kept around in a global variable.
    1562             :  *
    1563             :  * Error messages can also be collected in a user-provided buffer,
    1564             :  * instead of being echoed to a stream. This is a thread-specific
    1565             :  * issue; you want to decide on the error mechanism on a
    1566             :  * thread-specific basis.  This effect is established with
    1567             :  * GDKsetbuf. The memory (de)allocation of this buffer, that must at
    1568             :  * least be 1024 chars long, is entirely by the user. A pointer to
    1569             :  * this buffer is kept in the pseudo-variable GDKerrbuf. Normally,
    1570             :  * this is a NULL pointer.
    1571             :  */
    1572             : #define GDKMAXERRLEN    10240
    1573             : #define GDKWARNING      "!WARNING: "
    1574             : #define GDKERROR        "!ERROR: "
    1575             : #define GDKMESSAGE      "!OS: "
    1576             : #define GDKFATAL        "!FATAL: "
    1577             : 
    1578             : /* Data Distilleries uses ICU for internationalization of some MonetDB error messages */
    1579             : 
    1580             : #include "gdk_tracer.h"
    1581             : 
    1582             : gdk_export gdk_return GDKtracer_fill_comp_info(BAT *id, BAT *component, BAT *log_level);
    1583             : 
    1584             : #define GDKerror(format, ...)                                   \
    1585             :         GDKtracer_log(__FILE__, __func__, __LINE__, M_ERROR,    \
    1586             :                       GDK, NULL, format, ##__VA_ARGS__)
    1587             : #define GDKsyserr(errno, format, ...)                                   \
    1588             :         GDKtracer_log(__FILE__, __func__, __LINE__, M_CRITICAL,         \
    1589             :                       GDK, GDKstrerror(errno, (char[64]){0}, 64),       \
    1590             :                       format, ##__VA_ARGS__)
    1591             : #define GDKsyserror(format, ...)        GDKsyserr(errno, format, ##__VA_ARGS__)
    1592             : 
    1593             : gdk_export _Noreturn void GDKfatal(_In_z_ _Printf_format_string_ const char *format, ...)
    1594             :         __attribute__((__format__(__printf__, 1, 2)));
    1595             :         /*
    1596             : gdk_export void GDKfatal(_In_z_ _Printf_format_string_ const char *format, ...)
    1597             :         __attribute__((__format__(__printf__, 1, 2)));
    1598             :         */
    1599             : gdk_export void GDKclrerr(void);
    1600             : 
    1601             : 
    1602             : /* tfastins* family: update a value at a particular location in the bat
    1603             :  * bunfastapp* family: append a value to the bat
    1604             :  * *_nocheck: do not check whether the capacity is large enough
    1605             :  * * (without _nocheck): check bat capacity and possibly extend
    1606             :  *
    1607             :  * This means, for tfastins* it is the caller's responsibility to set
    1608             :  * the batCount and theap->free values correctly (e.g. by calling
    1609             :  * BATsetcount(), and for *_nocheck to make sure there is enough space
    1610             :  * allocated in the theap (tvheap for variable-sized types is still
    1611             :  * extended if needed, making that these functions can fail).
    1612             :  */
    1613             : static inline gdk_return __attribute__((__warn_unused_result__))
    1614    70056547 : tfastins_nocheckVAR(BAT *b, BUN p, const void *v)
    1615             : {
    1616             :         var_t d;
    1617             :         gdk_return rc;
    1618    70056547 :         assert(b->tbaseoff == 0);
    1619    70056547 :         assert(b->theap->parentid == b->batCacheid);
    1620    70056547 :         if ((rc = ATOMputVAR(b, &d, v)) != GDK_SUCCEED)
    1621             :                 return rc;
    1622    73066028 :         if (b->twidth < SIZEOF_VAR_T &&
    1623    63307214 :             (b->twidth <= 2 ? d - GDK_VAROFFSET : d) >= ((size_t) 1 << (8 << b->tshift))) {
    1624             :                 /* doesn't fit in current heap, upgrade it */
    1625       13424 :                 rc = GDKupgradevarheap(b, d, 0, MAX(p, b->batCount));
    1626       13422 :                 if (rc != GDK_SUCCEED)
    1627             :                         return rc;
    1628             :         }
    1629    73066025 :         switch (b->twidth) {
    1630    25455131 :         case 1:
    1631    25455131 :                 ((uint8_t *) b->theap->base)[p] = (uint8_t) (d - GDK_VAROFFSET);
    1632    25455131 :                 break;
    1633    14759629 :         case 2:
    1634    14759629 :                 ((uint16_t *) b->theap->base)[p] = (uint16_t) (d - GDK_VAROFFSET);
    1635    14759629 :                 break;
    1636    24447670 :         case 4:
    1637    24447670 :                 ((uint32_t *) b->theap->base)[p] = (uint32_t) d;
    1638    24447670 :                 break;
    1639             : #if SIZEOF_VAR_T == 8
    1640     8403595 :         case 8:
    1641     8403595 :                 ((uint64_t *) b->theap->base)[p] = (uint64_t) d;
    1642     8403595 :                 break;
    1643             : #endif
    1644             :         }
    1645             :         return GDK_SUCCEED;
    1646             : }
    1647             : 
    1648             : static inline gdk_return __attribute__((__warn_unused_result__))
    1649   312794685 : tfastins_nocheckFIX(BAT *b, BUN p, const void *v)
    1650             : {
    1651   312794685 :         return ATOMputFIX(b->ttype, Tloc(b, p), v);
    1652             : }
    1653             : 
    1654             : static inline gdk_return __attribute__((__warn_unused_result__))
    1655   302627611 : tfastins_nocheck(BAT *b, BUN p, const void *v)
    1656             : {
    1657   302627611 :         assert(b->theap->parentid == b->batCacheid);
    1658   302627611 :         assert(b->tbaseoff == 0);
    1659   302627611 :         if (b->ttype == TYPE_void) {
    1660             :                 ;
    1661   311860706 :         } else if (ATOMstorage(b->ttype) == TYPE_msk) {
    1662           0 :                 mskSetVal(b, p, * (msk *) v);
    1663   311860706 :         } else if (b->tvarsized) {
    1664    26811926 :                 return tfastins_nocheckVAR(b, p, v);
    1665             :         } else {
    1666   285048780 :                 return tfastins_nocheckFIX(b, p, v);
    1667             :         }
    1668             :         return GDK_SUCCEED;
    1669             : }
    1670             : 
    1671             : static inline gdk_return __attribute__((__warn_unused_result__))
    1672   299073698 : tfastins(BAT *b, BUN p, const void *v)
    1673             : {
    1674   299073698 :         if (p > BATcapacity(b)) {
    1675           0 :                 if (p >= BUN_MAX) {
    1676           0 :                         GDKerror("tfastins: too many elements to accommodate (" BUNFMT ")\n", BUN_MAX);
    1677           0 :                         return GDK_FAIL;
    1678             :                 }
    1679           0 :                 BUN sz = BATgrows(b);
    1680           0 :                 if (sz <= p)
    1681           0 :                         sz = p + BATTINY;
    1682           0 :                 gdk_return rc = BATextend(b, sz);
    1683           0 :                 if (rc != GDK_SUCCEED)
    1684             :                         return rc;
    1685             :         }
    1686   299073698 :         return tfastins_nocheck(b, p, v);
    1687             : }
    1688             : 
    1689             : static inline gdk_return __attribute__((__warn_unused_result__))
    1690      151941 : bunfastapp_nocheck(BAT *b, const void *v)
    1691             : {
    1692      151941 :         BUN p = b->batCount;
    1693      151941 :         if (ATOMstorage(b->ttype) == TYPE_msk && p % 32 == 0)
    1694           0 :                 ((uint32_t *) b->theap->base)[p / 32] = 0;
    1695      151941 :         gdk_return rc = tfastins_nocheck(b, p, v);
    1696      151945 :         if (rc == GDK_SUCCEED) {
    1697      151945 :                 b->batCount++;
    1698      151945 :                 if (ATOMstorage(b->ttype) == TYPE_msk) {
    1699           0 :                         if (p % 32 == 0)
    1700           0 :                                 b->theap->free += 4;
    1701             :                 } else
    1702      151945 :                         b->theap->free += b->twidth;
    1703             :         }
    1704      151945 :         return rc;
    1705             : }
    1706             : 
    1707             : static inline gdk_return __attribute__((__warn_unused_result__))
    1708   296951067 : bunfastapp(BAT *b, const void *v)
    1709             : {
    1710   296951067 :         BUN p = b->batCount;
    1711   296951067 :         if (ATOMstorage(b->ttype) == TYPE_msk && p % 32 == 0)
    1712           0 :                 ((uint32_t *) b->theap->base)[p / 32] = 0;
    1713   296951067 :         gdk_return rc = tfastins(b, p, v);
    1714   299843457 :         if (rc == GDK_SUCCEED) {
    1715   302003897 :                 b->batCount++;
    1716   302003897 :                 if (ATOMstorage(b->ttype) == TYPE_msk) {
    1717           0 :                         if (p % 32 == 0)
    1718           0 :                                 b->theap->free += 4;
    1719             :                 } else
    1720   302003897 :                         b->theap->free += b->twidth;
    1721             :         }
    1722   299843457 :         return rc;
    1723             : }
    1724             : 
    1725             : #define bunfastappTYPE(TYPE, b, v)                                      \
    1726             :         (BATcount(b) >= BATcapacity(b) &&                            \
    1727             :          ((BATcount(b) == BUN_MAX &&                                    \
    1728             :            (GDKerror("bunfastapp: too many elements to accommodate (" BUNFMT ")\n", BUN_MAX), \
    1729             :             true)) ||                                                   \
    1730             :           BATextend((b), BATgrows(b)) != GDK_SUCCEED) ?                 \
    1731             :          GDK_FAIL :                                                     \
    1732             :          (assert((b)->theap->parentid == (b)->batCacheid),             \
    1733             :           (b)->theap->free += sizeof(TYPE),                               \
    1734             :           ((TYPE *) (b)->theap->base)[(b)->batCount++] = * (const TYPE *) (v), \
    1735             :           GDK_SUCCEED))
    1736             : 
    1737             : static inline gdk_return __attribute__((__warn_unused_result__))
    1738         341 : bunfastapp_nocheckVAR(BAT *b, const void *v)
    1739             : {
    1740             :         gdk_return rc;
    1741         341 :         rc = tfastins_nocheckVAR(b, b->batCount, v);
    1742         342 :         if (rc == GDK_SUCCEED) {
    1743         342 :                 b->batCount++;
    1744         342 :                 b->theap->free += b->twidth;
    1745             :         }
    1746         342 :         return rc;
    1747             : }
    1748             : 
    1749             : /*
    1750             :  * @- Column Imprints Functions
    1751             :  *
    1752             :  * @multitable @columnfractions 0.08 0.7
    1753             :  * @item BAT*
    1754             :  * @tab
    1755             :  *  BATimprints (BAT *b)
    1756             :  * @end multitable
    1757             :  *
    1758             :  * The column imprints index structure.
    1759             :  *
    1760             :  */
    1761             : 
    1762             : gdk_export gdk_return BATimprints(BAT *b);
    1763             : gdk_export void IMPSdestroy(BAT *b);
    1764             : gdk_export lng IMPSimprintsize(BAT *b);
    1765             : 
    1766             : /* The ordered index structure */
    1767             : 
    1768             : gdk_export gdk_return BATorderidx(BAT *b, bool stable);
    1769             : gdk_export gdk_return GDKmergeidx(BAT *b, BAT**a, int n_ar);
    1770             : gdk_export bool BATcheckorderidx(BAT *b);
    1771             : 
    1772             : #include "gdk_delta.h"
    1773             : #include "gdk_hash.h"
    1774             : #include "gdk_bbp.h"
    1775             : #include "gdk_utils.h"
    1776             : 
    1777             : /* functions defined in gdk_bat.c */
    1778             : gdk_export gdk_return void_inplace(BAT *b, oid id, const void *val, bool force)
    1779             :         __attribute__((__warn_unused_result__));
    1780             : gdk_export BAT *BATattach(int tt, const char *heapfile, role_t role);
    1781             : 
    1782             : #ifdef NATIVE_WIN32
    1783             : #ifdef _MSC_VER
    1784             : #define fileno _fileno
    1785             : #endif
    1786             : #define fdopen _fdopen
    1787             : #define putenv _putenv
    1788             : #endif
    1789             : 
    1790             : /* Return a pointer to the value contained in V.  Also see VALget
    1791             :  * which returns a void *. */
    1792             : static inline const void *
    1793   373783303 : VALptr(const ValRecord *v)
    1794             : {
    1795   373783303 :         switch (ATOMstorage(v->vtype)) {
    1796       34778 :         case TYPE_void: return (const void *) &v->val.oval;
    1797           0 :         case TYPE_msk: return (const void *) &v->val.mval;
    1798    12864622 :         case TYPE_bte: return (const void *) &v->val.btval;
    1799     1299143 :         case TYPE_sht: return (const void *) &v->val.shval;
    1800    92915367 :         case TYPE_int: return (const void *) &v->val.ival;
    1801       18311 :         case TYPE_flt: return (const void *) &v->val.fval;
    1802      683480 :         case TYPE_dbl: return (const void *) &v->val.dval;
    1803   122507678 :         case TYPE_lng: return (const void *) &v->val.lval;
    1804             : #ifdef HAVE_HGE
    1805       32608 :         case TYPE_hge: return (const void *) &v->val.hval;
    1806             : #endif
    1807        1363 :         case TYPE_uuid: return (const void *) &v->val.uval;
    1808      450217 :         case TYPE_ptr: return (const void *) &v->val.pval;
    1809   142969175 :         case TYPE_str: return (const void *) v->val.sval;
    1810        6561 :         default:       return (const void *) v->val.pval;
    1811             :         }
    1812             : }
    1813             : 
    1814             : /*
    1815             :  * The kernel maintains a central table of all active threads.  They
    1816             :  * are indexed by their tid. The structure contains information on the
    1817             :  * input/output file descriptors, which should be set before a
    1818             :  * database operation is started. It ensures that output is delivered
    1819             :  * to the proper client.
    1820             :  *
    1821             :  * The Thread structure should be ideally made directly accessible to
    1822             :  * each thread. This speeds up access to tid and file descriptors.
    1823             :  */
    1824             : #define THREADS 1024
    1825             : #define THREADDATA      3
    1826             : 
    1827             : typedef struct threadStruct {
    1828             :         int tid;                /* logical ID by MonetDB; val == index
    1829             :                                  * into this array + 1 (0 is
    1830             :                                  * invalid) */
    1831             :         ATOMIC_TYPE pid;        /* thread id, 0 = unallocated */
    1832             :         char name[MT_NAME_LEN];
    1833             :         void *data[THREADDATA];
    1834             :         uintptr_t sp;
    1835             : } *Thread;
    1836             : 
    1837             : 
    1838             : gdk_export int THRgettid(void);
    1839             : gdk_export Thread THRget(int tid);
    1840             : gdk_export MT_Id THRcreate(void (*f) (void *), void *arg, enum MT_thr_detach d, const char *name);
    1841             : gdk_export void THRdel(Thread t);
    1842             : gdk_export void THRsetdata(int, void *);
    1843             : gdk_export void *THRgetdata(int);
    1844             : gdk_export int THRhighwater(void);
    1845             : 
    1846             : gdk_export void *THRdata[THREADDATA];
    1847             : 
    1848             : #define GDKstdout       ((stream*)THRdata[0])
    1849             : #define GDKstdin        ((stream*)THRdata[1])
    1850             : 
    1851             : #define GDKerrbuf       ((char*)THRgetdata(2))
    1852             : #define GDKsetbuf(x)    THRsetdata(2,(void *)(x))
    1853             : 
    1854             : #define THRget_errbuf(t)        ((char*)t->data[2])
    1855             : #define THRset_errbuf(t,b)      (t->data[2] = b)
    1856             : 
    1857             : static inline bat
    1858   511791513 : BBPcheck(bat x)
    1859             : {
    1860   511791513 :         if (!is_bat_nil(x)) {
    1861   513260684 :                 assert(x > 0);
    1862             : 
    1863   513260684 :                 if (x < 0 || x >= getBBPsize() || BBP_logical(x) == NULL) {
    1864         404 :                         TRC_DEBUG(CHECK_, "range error %d\n", (int) x);
    1865             :                 } else {
    1866   515390283 :                         assert(BBP_pid(x) == 0 || BBP_pid(x) == MT_getpid());
    1867   515411373 :                         return x;
    1868             :                 }
    1869             :         }
    1870             :         return 0;
    1871             : }
    1872             : 
    1873             : static inline BAT *
    1874   121924243 : BATdescriptor(bat i)
    1875             : {
    1876             :         BAT *b = NULL;
    1877             : 
    1878   121924243 :         if (BBPcheck(i)) {
    1879   121304825 :                 if (BBPfix(i) <= 0)
    1880             :                         return NULL;
    1881   121848225 :                 b = BBP_cache(i);
    1882   121848225 :                 if (b == NULL)
    1883       14701 :                         b = BBPdescriptor(i);
    1884             :         }
    1885             :         return b;
    1886             : }
    1887             : 
    1888             : static inline void *
    1889      654973 : Tpos(BATiter *bi, BUN p)
    1890             : {
    1891      654973 :         assert(bi->base == NULL);
    1892      654973 :         if (bi->vh) {
    1893             :                 oid o;
    1894          17 :                 assert(!is_oid_nil(bi->tseq));
    1895          17 :                 if (((ccand_t *) bi->vh)->type == CAND_NEGOID) {
    1896          17 :                         BUN nexc = (bi->vhfree - sizeof(ccand_t)) / SIZEOF_OID;
    1897          17 :                         o = bi->tseq + p;
    1898          17 :                         if (nexc > 0) {
    1899          17 :                                 const oid *exc = (const oid *) (bi->vh->base + sizeof(ccand_t));
    1900          17 :                                 if (o >= exc[0]) {
    1901          17 :                                         if (o + nexc > exc[nexc - 1]) {
    1902             :                                                 o += nexc;
    1903             :                                         } else {
    1904             :                                                 BUN lo = 0;
    1905           0 :                                                 BUN hi = nexc - 1;
    1906           0 :                                                 while (hi - lo > 1) {
    1907           0 :                                                         BUN mid = (hi + lo) / 2;
    1908           0 :                                                         if (exc[mid] - mid > o)
    1909             :                                                                 hi = mid;
    1910             :                                                         else
    1911             :                                                                 lo = mid;
    1912             :                                                 }
    1913           0 :                                                 o += hi;
    1914             :                                         }
    1915             :                                 }
    1916             :                         }
    1917             :                 } else {
    1918           0 :                         const uint32_t *msk = (const uint32_t *) (bi->vh->base + sizeof(ccand_t));
    1919           0 :                         BUN nmsk = (bi->vhfree - sizeof(ccand_t)) / sizeof(uint32_t);
    1920             :                         o = 0;
    1921           0 :                         for (BUN i = 0; i < nmsk; i++) {
    1922           0 :                                 uint32_t m = candmask_pop(msk[i]);
    1923           0 :                                 if (o + m > p) {
    1924             :                                         m = msk[i];
    1925           0 :                                         for (i = 0; i < 32; i++) {
    1926           0 :                                                 if (m & (1U << i) && ++o == p)
    1927             :                                                         break;
    1928             :                                         }
    1929             :                                         break;
    1930             :                                 }
    1931             :                                 o += m;
    1932             :                         }
    1933             :                 }
    1934          17 :                 bi->tvid = o;
    1935      654956 :         } else if (is_oid_nil(bi->tseq)) {
    1936         562 :                 bi->tvid = oid_nil;
    1937             :         } else {
    1938      654394 :                 bi->tvid = bi->tseq + p;
    1939             :         }
    1940      654973 :         return (void *) &bi->tvid;
    1941             : }
    1942             : 
    1943             : static inline bool
    1944             : Tmskval(BATiter *bi, BUN p)
    1945             : {
    1946        1631 :         return ((uint32_t *) bi->base)[p / 32] & (1U << (p % 32));
    1947             : }
    1948             : 
    1949             : static inline void *
    1950             : Tmsk(BATiter *bi, BUN p)
    1951             : {
    1952        3400 :         bi->tmsk = Tmskval(bi, p);
    1953           0 :         return &bi->tmsk;
    1954             : }
    1955             : 
    1956             : /* return the oid value at BUN position p from the (v)oid bat b
    1957             :  * works with any TYPE_void or TYPE_oid bat */
    1958             : static inline oid
    1959    21150229 : BUNtoid(BAT *b, BUN p)
    1960             : {
    1961    21150229 :         assert(ATOMtype(b->ttype) == TYPE_oid);
    1962             :         /* BATcount is the number of valid entries, so with
    1963             :          * exceptions, the last value can well be larger than
    1964             :          * b->tseqbase + BATcount(b) */
    1965    21150229 :         assert(p < BATcount(b));
    1966    21150229 :         assert(b->ttype == TYPE_void || b->tvheap == NULL);
    1967    21150229 :         if (is_oid_nil(b->tseqbase)) {
    1968    20952485 :                 if (b->ttype == TYPE_void)
    1969           0 :                         return oid_nil;
    1970    20952485 :                 MT_lock_set(&b->theaplock);
    1971    21409559 :                 oid o = ((const oid *) b->theap->base)[p + b->tbaseoff];
    1972    21409559 :                 MT_lock_unset(&b->theaplock);
    1973    20812110 :                 return o;
    1974             :         }
    1975      197744 :         if (b->ttype == TYPE_oid || b->tvheap == NULL) {
    1976      197727 :                 return b->tseqbase + p;
    1977             :         }
    1978             :         /* b->tvheap != NULL, so we know there will be no parallel
    1979             :          * modifications (so no locking) */
    1980          17 :         BATiter bi = bat_iterator_nolock(b);
    1981          17 :         return * (oid *) Tpos(&bi, p);
    1982             : }
    1983             : 
    1984             : /*
    1985             :  * @+ Transaction Management
    1986             :  * @multitable @columnfractions 0.08 0.7
    1987             :  * @item int
    1988             :  * @tab
    1989             :  *  TMcommit ()
    1990             :  * @item int
    1991             :  * @tab
    1992             :  *  TMabort ()
    1993             :  * @item int
    1994             :  * @tab
    1995             :  *  TMsubcommit ()
    1996             :  * @end multitable
    1997             :  *
    1998             :  * MonetDB by default offers a global transaction environment.  The
    1999             :  * global transaction involves all activities on all persistent BATs
    2000             :  * by all threads.  Each global transaction ends with either TMabort
    2001             :  * or TMcommit, and immediately starts a new transaction.  TMcommit
    2002             :  * implements atomic commit to disk on the collection of all
    2003             :  * persistent BATs. For all persistent BATs, the global commit also
    2004             :  * flushes the delta status for these BATs (see
    2005             :  * BATcommit/BATabort). This allows to perform TMabort quickly in
    2006             :  * memory (without re-reading all disk images from disk).  The
    2007             :  * collection of which BATs is persistent is also part of the global
    2008             :  * transaction state. All BATs that where persistent at the last
    2009             :  * commit, but were made transient since then, are made persistent
    2010             :  * again by TMabort.  In other words, BATs that are deleted, are only
    2011             :  * physically deleted at TMcommit time. Until that time, rollback
    2012             :  * (TMabort) is possible.
    2013             :  *
    2014             :  * Use of TMabort is currently NOT RECOMMENDED due to two bugs:
    2015             :  *
    2016             :  * @itemize
    2017             :  * @item
    2018             :  * TMabort after a failed %TMcommit@ does not bring us back to the
    2019             :  * previous committed state; but to the state at the failed TMcommit.
    2020             :  * @item
    2021             :  * At runtime, TMabort does not undo BAT name changes, whereas a cold
    2022             :  * MonetDB restart does.
    2023             :  * @end itemize
    2024             :  *
    2025             :  * In effect, the problems with TMabort reduce the functionality of
    2026             :  * the global transaction mechanism to consistent checkpointing at
    2027             :  * each TMcommit. For many applications, consistent checkpointingis
    2028             :  * enough.
    2029             :  *
    2030             :  * Extension modules exist that provide fine grained locking (lock
    2031             :  * module) and Write Ahead Logging (sqlserver).  Applications that
    2032             :  * need more fine-grained transactions, should build this on top of
    2033             :  * these extension primitives.
    2034             :  *
    2035             :  * TMsubcommit is intended to quickly add or remove BATs from the
    2036             :  * persistent set. In both cases, rollback is not necessary, such that
    2037             :  * the commit protocol can be accelerated. It comes down to writing a
    2038             :  * new BBP.dir.
    2039             :  *
    2040             :  * Its parameter is a BAT-of-BATs (in the tail); the persistence
    2041             :  * status of that BAT is committed. We assume here that the calling
    2042             :  * thread has exclusive access to these bats.  An error is reported if
    2043             :  * you try to partially commit an already committed persistent BAT (it
    2044             :  * needs the rollback mechanism).
    2045             :  */
    2046             : gdk_export gdk_return TMcommit(void);
    2047             : gdk_export void TMabort(void);
    2048             : gdk_export gdk_return TMsubcommit(BAT *bl);
    2049             : gdk_export gdk_return TMsubcommit_list(bat *restrict subcommit, BUN *restrict sizes, int cnt, lng logno, lng transid);
    2050             : 
    2051             : /*
    2052             :  * @- Delta Management
    2053             :  *  @multitable @columnfractions 0.08 0.6
    2054             :  * @item BAT *
    2055             :  * @tab BATcommit (BAT *b)
    2056             :  * @item BAT *
    2057             :  * @tab BATfakeCommit (BAT *b)
    2058             :  * @item BAT *
    2059             :  * @tab BATundo (BAT *b)
    2060             :  * @end multitable
    2061             :  *
    2062             :  * The BAT keeps track of updates with respect to a 'previous state'.
    2063             :  * Do not confuse 'previous state' with 'stable' or
    2064             :  * 'commited-on-disk', because these concepts are not always the
    2065             :  * same. In particular, they diverge when BATcommit, BATfakecommit,
    2066             :  * and BATundo are called explictly, bypassing the normal global
    2067             :  * TMcommit protocol (some applications need that flexibility).
    2068             :  *
    2069             :  * BATcommit make the current BAT state the new 'stable state'.  This
    2070             :  * happens inside the global TMcommit on all persistent BATs previous
    2071             :  * to writing all bats to persistent storage using a BBPsync.
    2072             :  *
    2073             :  * EXPERT USE ONLY: The routine BATfakeCommit updates the delta
    2074             :  * information on BATs and clears the dirty bit. This avoids any
    2075             :  * copying to disk.  Expert usage only, as it bypasses the global
    2076             :  * commit protocol, and changes may be lost after quitting or crashing
    2077             :  * MonetDB.
    2078             :  *
    2079             :  * BATabort undo-s all changes since the previous state. The global
    2080             :  * TMabort achieves a rollback to the previously committed state by
    2081             :  * doing BATabort on all persistent bats.
    2082             :  *
    2083             :  * BUG: after a failed TMcommit, TMabort does not do anything because
    2084             :  * TMcommit does the BATcommits @emph{before} attempting to sync to
    2085             :  * disk instead of @sc{after} doing this.
    2086             :  */
    2087             : gdk_export void BATcommit(BAT *b, BUN size);
    2088             : gdk_export void BATfakeCommit(BAT *b);
    2089             : gdk_export void BATundo(BAT *b);
    2090             : 
    2091             : /*
    2092             :  * @+ BAT Alignment and BAT views
    2093             :  * @multitable @columnfractions 0.08 0.7
    2094             :  * @item int
    2095             :  * @tab ALIGNsynced (BAT* b1, BAT* b2)
    2096             :  * @item int
    2097             :  * @tab ALIGNsync   (BAT *b1, BAT *b2)
    2098             :  * @item int
    2099             :  * @tab ALIGNrelated (BAT *b1, BAT *b2)
    2100             :  *
    2101             :  * @item BAT*
    2102             :  * @tab VIEWcreate   (oid seq, BAT *b)
    2103             :  * @item int
    2104             :  * @tab isVIEW   (BAT *b)
    2105             :  * @item bat
    2106             :  * @tab VIEWhparent   (BAT *b)
    2107             :  * @item bat
    2108             :  * @tab VIEWtparent   (BAT *b)
    2109             :  * @end multitable
    2110             :  *
    2111             :  * Alignments of two columns of a BAT means that the system knows
    2112             :  * whether these two columns are exactly equal. Relatedness of two
    2113             :  * BATs means that one pair of columns (either head or tail) of both
    2114             :  * BATs is aligned. The first property is checked by ALIGNsynced, the
    2115             :  * latter by ALIGNrelated.
    2116             :  *
    2117             :  * All algebraic BAT commands propagate the properties - including
    2118             :  * alignment properly on their results.
    2119             :  *
    2120             :  * VIEW BATs are BATs that lend their storage from a parent BAT.  They
    2121             :  * are just a descriptor that points to the data in this parent BAT. A
    2122             :  * view is created with VIEWcreate. The cache id of the parent (if
    2123             :  * any) is returned by VIEWtparent (otherwise it returns 0).
    2124             :  *
    2125             :  * VIEW bats are read-only!!
    2126             :  */
    2127             : gdk_export int ALIGNsynced(BAT *b1, BAT *b2);
    2128             : 
    2129             : gdk_export void BATassertProps(BAT *b);
    2130             : 
    2131             : gdk_export BAT *VIEWcreate(oid seq, BAT *b);
    2132             : gdk_export void VIEWbounds(BAT *b, BAT *view, BUN l, BUN h);
    2133             : 
    2134             : #define ALIGNapp(x, f, e)                                               \
    2135             :         do {                                                            \
    2136             :                 if (!(f) && ((x)->batRestricted == BAT_READ ||               \
    2137             :                              (x)->batSharecnt > 0)) {                     \
    2138             :                         GDKerror("access denied to %s, aborting.\n",  \
    2139             :                                  BATgetId(x));                          \
    2140             :                         return (e);                                     \
    2141             :                 }                                                       \
    2142             :         } while (false)
    2143             : 
    2144             : /* the parentid in a VIEW is correct for the normal view. We must
    2145             :  * correct for the reversed view.
    2146             :  */
    2147             : #define isVIEW(x)                                                       \
    2148             :         (((x)->theap && (x)->theap->parentid != (x)->batCacheid) || \
    2149             :          ((x)->tvheap && (x)->tvheap->parentid != (x)->batCacheid))
    2150             : 
    2151             : #define VIEWtparent(x)  ((x)->theap == NULL || (x)->theap->parentid == (x)->batCacheid ? 0 : (x)->theap->parentid)
    2152             : #define VIEWvtparent(x) ((x)->tvheap == NULL || (x)->tvheap->parentid == (x)->batCacheid ? 0 : (x)->tvheap->parentid)
    2153             : 
    2154             : /*
    2155             :  * @+ BAT Iterators
    2156             :  *  @multitable @columnfractions 0.15 0.7
    2157             :  * @item BATloop
    2158             :  * @tab
    2159             :  *  (BAT *b; BUN p, BUN q)
    2160             :  * @item BATloopDEL
    2161             :  * @tab
    2162             :  *  (BAT *b; BUN p; BUN q; int dummy)
    2163             :  * @item HASHloop
    2164             :  * @tab
    2165             :  *  (BAT *b; Hash *h, size_t dummy; ptr value)
    2166             :  * @item HASHloop_bte
    2167             :  * @tab
    2168             :  *  (BAT *b; Hash *h, size_t idx; bte *value, BUN w)
    2169             :  * @item HASHloop_sht
    2170             :  * @tab
    2171             :  *  (BAT *b; Hash *h, size_t idx; sht *value, BUN w)
    2172             :  * @item HASHloop_int
    2173             :  * @tab
    2174             :  *  (BAT *b; Hash *h, size_t idx; int *value, BUN w)
    2175             :  * @item HASHloop_flt
    2176             :  * @tab
    2177             :  *  (BAT *b; Hash *h, size_t idx; flt *value, BUN w)
    2178             :  * @item HASHloop_lng
    2179             :  * @tab
    2180             :  *  (BAT *b; Hash *h, size_t idx; lng *value, BUN w)
    2181             :  * @item HASHloop_hge
    2182             :  * @tab
    2183             :  *  (BAT *b; Hash *h, size_t idx; hge *value, BUN w)
    2184             :  * @item HASHloop_dbl
    2185             :  * @tab
    2186             :  *  (BAT *b; Hash *h, size_t idx; dbl *value, BUN w)
    2187             :  * @item  HASHloop_str
    2188             :  * @tab
    2189             :  *  (BAT *b; Hash *h, size_t idx; str value, BUN w)
    2190             :  * @item HASHlooploc
    2191             :  * @tab
    2192             :  *  (BAT *b; Hash *h, size_t idx; ptr value, BUN w)
    2193             :  * @item HASHloopvar
    2194             :  * @tab
    2195             :  *  (BAT *b; Hash *h, size_t idx; ptr value, BUN w)
    2196             :  * @end multitable
    2197             :  *
    2198             :  * The @emph{BATloop()} looks like a function call, but is actually a
    2199             :  * macro.
    2200             :  *
    2201             :  * @- simple sequential scan
    2202             :  * The first parameter is a BAT, the p and q are BUN pointers, where p
    2203             :  * is the iteration variable.
    2204             :  */
    2205             : #define BATloop(r, p, q)                        \
    2206             :         for (q = BUNlast(r), p = 0; p < q; p++)
    2207             : 
    2208             : /*
    2209             :  * @+ Common BAT Operations
    2210             :  * Much used, but not necessarily kernel-operations on BATs.
    2211             :  *
    2212             :  * For each BAT we maintain its dimensions as separately accessible
    2213             :  * properties. They can be used to improve query processing at higher
    2214             :  * levels.
    2215             :  */
    2216             : enum prop_t {
    2217             :         GDK_MIN_VALUE = 3,      /* smallest non-nil value in BAT */
    2218             :         GDK_MIN_POS,            /* BUN position of smallest value (oid) */
    2219             :         GDK_MAX_VALUE,          /* largest non-nil value in BAT */
    2220             :         GDK_MAX_POS,            /* BUN position of largest value (oid) */
    2221             :         GDK_HASH_BUCKETS,       /* last used hash bucket size (oid) */
    2222             :         GDK_NUNIQUE,            /* number of unique values (oid) */
    2223             :         GDK_UNIQUE_ESTIMATE,    /* estimate of number of distinct values (dbl) */
    2224             : };
    2225             : 
    2226             : gdk_export ValPtr BATgetprop(BAT *b, enum prop_t idx);
    2227             : 
    2228             : /*
    2229             :  * @- BAT relational operators
    2230             :  *
    2231             :  * The full-materialization policy intermediate results in MonetDB
    2232             :  * means that a join can produce an arbitrarily large result and choke
    2233             :  * the system. The Data Distilleries tool therefore first computes the
    2234             :  * join result size before the actual join (better waste time than
    2235             :  * crash the server). To exploit that perfect result size knowledge,
    2236             :  * an result-size estimate parameter was added to all equi-join
    2237             :  * implementations.  TODO: add this for
    2238             :  * semijoin/select/unique/diff/intersect
    2239             :  *
    2240             :  * @- modes for thethajoin
    2241             :  */
    2242             : #define JOIN_EQ         0
    2243             : #define JOIN_LT         (-1)
    2244             : #define JOIN_LE         (-2)
    2245             : #define JOIN_GT         1
    2246             : #define JOIN_GE         2
    2247             : #define JOIN_BAND       3
    2248             : #define JOIN_NE         (-3)
    2249             : 
    2250             : gdk_export BAT *BATselect(BAT *b, BAT *s, const void *tl, const void *th, bool li, bool hi, bool anti);
    2251             : gdk_export BAT *BATthetaselect(BAT *b, BAT *s, const void *val, const char *op);
    2252             : 
    2253             : gdk_export BAT *BATconstant(oid hseq, int tt, const void *val, BUN cnt, role_t role);
    2254             : gdk_export gdk_return BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
    2255             :         __attribute__((__warn_unused_result__));
    2256             : 
    2257             : gdk_export gdk_return BATleftjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
    2258             :         __attribute__((__warn_unused_result__));
    2259             : gdk_export gdk_return BATouterjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool match_one, BUN estimate)
    2260             :         __attribute__((__warn_unused_result__));
    2261             : gdk_export gdk_return BATthetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, int op, bool nil_matches, BUN estimate)
    2262             :         __attribute__((__warn_unused_result__));
    2263             : gdk_export gdk_return BATsemijoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool max_one, BUN estimate)
    2264             :         __attribute__((__warn_unused_result__));
    2265             : gdk_export BAT *BATintersect(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool max_one, BUN estimate);
    2266             : gdk_export BAT *BATdiff(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool not_in, BUN estimate);
    2267             : gdk_export gdk_return BATjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
    2268             :         __attribute__((__warn_unused_result__));
    2269             : gdk_export BUN BATguess_uniques(BAT *b, struct canditer *ci);
    2270             : gdk_export gdk_return BATbandjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, const void *c1, const void *c2, bool li, bool hi, BUN estimate)
    2271             :         __attribute__((__warn_unused_result__));
    2272             : gdk_export gdk_return BATrangejoin(BAT **r1p, BAT **r2p, BAT *l, BAT *rl, BAT *rh, BAT *sl, BAT *sr, bool li, bool hi, bool anti, bool symmetric, BUN estimate)
    2273             :         __attribute__((__warn_unused_result__));
    2274             : gdk_export BAT *BATproject(BAT *restrict l, BAT *restrict r);
    2275             : gdk_export BAT *BATproject2(BAT *restrict l, BAT *restrict r1, BAT *restrict r2);
    2276             : gdk_export BAT *BATprojectchain(BAT **bats);
    2277             : 
    2278             : gdk_export BAT *BATslice(BAT *b, BUN low, BUN high);
    2279             : 
    2280             : gdk_export BAT *BATunique(BAT *b, BAT *s);
    2281             : 
    2282             : gdk_export BAT *BATmergecand(BAT *a, BAT *b);
    2283             : gdk_export BAT *BATintersectcand(BAT *a, BAT *b);
    2284             : gdk_export BAT *BATdiffcand(BAT *a, BAT *b);
    2285             : 
    2286             : gdk_export gdk_return BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *cands, BAT *grps, BUN n, bool asc, bool nilslast, bool distinct)
    2287             :         __attribute__((__warn_unused_result__));
    2288             : 
    2289             : #include "gdk_calc.h"
    2290             : 
    2291             : /*
    2292             :  * @- BAT sample operators
    2293             :  *
    2294             :  * @multitable @columnfractions 0.08 0.7
    2295             :  * @item BAT *
    2296             :  * @tab BATsample (BAT *b, n)
    2297             :  * @end multitable
    2298             :  *
    2299             :  * The routine BATsample returns a random sample on n BUNs of a BAT.
    2300             :  *
    2301             :  */
    2302             : gdk_export BAT *BATsample(BAT *b, BUN n);
    2303             : gdk_export BAT *BATsample_with_seed(BAT *b, BUN n, uint64_t seed);
    2304             : 
    2305             : /*
    2306             :  *
    2307             :  */
    2308             : #define MAXPARAMS       32
    2309             : 
    2310             : #endif /* _GDK_H_ */

Generated by: LCOV version 1.14