view release on metacpan or  search on metacpan

src/judy-1.0.5/src/Judy1/Judy1.h  view on Meta::CPAN

// Free Software Foundation; either version 2 of the License, or (at your
// option) any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
// for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// _________________

// @(#) $Revision: 4.76 $ $Source: /judy/src/Judy1/Judy1.h $

// ****************************************************************************
//          JUDY1 -- SMALL/LARGE AND/OR CLUSTERED/SPARSE BIT ARRAYS
//
//                                    -by-
//
//                             Douglas L. Baskins
//                             doug@sourcejudy.com
//
// Judy arrays are designed to be used instead of arrays.  The performance
// suggests the reason why Judy arrays are thought of as arrays, instead of
// trees.  They are remarkably memory efficient at all populations.
// Implemented as a hybrid digital tree (but really a state machine, see
// below), Judy arrays feature fast insert/retrievals, fast near neighbor
// searching, and contain a population tree for extremely fast ordinal related
// retrievals.
//
// CONVENTIONS:
//
// - The comments here refer to 32-bit [64-bit] systems.
//
// - BranchL, LeafL refer to linear branches and leaves (small populations),
//   except LeafL does not actually appear as such; rather, Leaf1..3 [Leaf1..7]
//   is used to represent leaf Index sizes, and LeafW refers to a Leaf with
//   full (long) word Indexes, which is also a type of linear leaf.  Note that
//   root-level LeafW (Leaf4 [Leaf8]) leaves are also called LEAFW.
//
// - BranchB, LeafB1 refer to bitmap branches and leaves (intermediate
//   populations).
//
// - BranchU refers to uncompressed branches.  An uncompressed branch has 256
//   JPs, some of which could be null.  Note:  All leaves are compressed (and
//   sorted), or else an expanse is full (FullPopu), so there is no LeafU
//   equivalent to BranchU.
//
// - "Popu" is short for "Population".
// - "Pop1" refers to actual population (base 1).
// - "Pop0" refers to Pop1 - 1 (base 0), the way populations are stored in data
//   structures.
//
// - Branches and Leaves are both named by the number of bytes in their Pop0
//   field.  In the case of Leaves, the same number applies to the Index sizes.
//
// - The representation of many numbers as hex is a relatively safe and
//   portable way to get desired bitpatterns as unsigned longs.
//
// - Some preprocessors cant handle single apostrophe characters within
//   #ifndef code, so here, use delete all instead.

#include "JudyPrivate.h"        // includes Judy.h in turn.
#include "JudyPrivateBranch.h"


// ****************************************************************************
// JUDY1 ROOT POINTER (JRP) AND JUDY1 POINTER (JP) TYPE FIELDS
// ****************************************************************************
//
// The following enum lists all possible JP Type fields. 

typedef enum            // uint8_t -- but C does not support this type of enum.
{

// JP NULL TYPES:
//
// There is a series of cJ1_JPNULL* Types because each one pre-records a
// different Index Size for when the first Index is inserted in the previously
// null JP.  They must start >= 8 (three bits).
//
// Note:  These Types must be in sequential order for doing relative
// calculations between them.

        cJ1_JPNULL1 = 1,
                                // Index Size 1[1] byte  when 1 Index inserted.
        cJ1_JPNULL2,            // Index Size 2[2] bytes when 1 Index inserted.
        cJ1_JPNULL3,            // Index Size 3[3] bytes when 1 Index inserted.

#ifndef JU_64BIT
#define cJ1_JPNULLMAX cJ1_JPNULL3
#else
        cJ1_JPNULL4,            // Index Size 4[4] bytes when 1 Index inserted.
        cJ1_JPNULL5,            // Index Size 5[5] bytes when 1 Index inserted.
        cJ1_JPNULL6,            // Index Size 6[6] bytes when 1 Index inserted.
        cJ1_JPNULL7,            // Index Size 7[7] bytes when 1 Index inserted.
#define cJ1_JPNULLMAX cJ1_JPNULL7
#endif


// JP BRANCH TYPES:
//
// Note:  There are no state-1 branches; only leaves reside at state 1.

// Linear branches:
//
// Note:  These Types must be in sequential order for doing relative
// calculations between them.

        cJ1_JPBRANCH_L2,        // 2[2] bytes Pop0, 1[5] bytes Dcd.
        cJ1_JPBRANCH_L3,        // 3[3] bytes Pop0, 0[4] bytes Dcd.

#ifdef JU_64BIT
        cJ1_JPBRANCH_L4,        //  [4] bytes Pop0,  [3] bytes Dcd.
        cJ1_JPBRANCH_L5,        //  [5] bytes Pop0,  [2] bytes Dcd.
        cJ1_JPBRANCH_L6,        //  [6] bytes Pop0,  [1] byte  Dcd.
        cJ1_JPBRANCH_L7,        //  [7] bytes Pop0,  [0] bytes Dcd.
#endif

        cJ1_JPBRANCH_L,         // note:  DcdPopO field not used.