view release on metacpan or  search on metacpan

src/judy-1.0.5/src/JudyL/JudyL.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.41 $ $Source: /judy/src/JudyL/JudyL.h $

// ****************************************************************************
//          JUDYL -- SMALL/LARGE AND/OR CLUSTERED/SPARSE 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 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, delete all instead.


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


// ****************************************************************************
// JUDYL ROOT POINTER (JRP) AND JUDYL POINTER (JP) TYPE FIELDS
// ****************************************************************************

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

// JP NULL TYPES:
//
// There is a series of cJL_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.

        cJL_JPNULL1 = 1,
                                // Index Size 1[1] byte  when 1 Index inserted.
        cJL_JPNULL2,            // Index Size 2[2] bytes when 1 Index inserted.
        cJL_JPNULL3,            // Index Size 3[3] bytes when 1 Index inserted.

#ifndef JU_64BIT
#define cJL_JPNULLMAX cJL_JPNULL3
#else
        cJL_JPNULL4,            // Index Size 4[4] bytes when 1 Index inserted.
        cJL_JPNULL5,            // Index Size 5[5] bytes when 1 Index inserted.
        cJL_JPNULL6,            // Index Size 6[6] bytes when 1 Index inserted.
        cJL_JPNULL7,            // Index Size 7[7] bytes when 1 Index inserted.
#define cJL_JPNULLMAX cJL_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.

        cJL_JPBRANCH_L2,        // 2[2] bytes Pop0, 1[5] bytes Dcd.
        cJL_JPBRANCH_L3,        // 3[3] bytes Pop0, 0[4] bytes Dcd.

#ifdef JU_64BIT
        cJL_JPBRANCH_L4,        //  [4] bytes Pop0,  [3] bytes Dcd.
        cJL_JPBRANCH_L5,        //  [5] bytes Pop0,  [2] bytes Dcd.
        cJL_JPBRANCH_L6,        //  [6] bytes Pop0,  [1] byte  Dcd.
        cJL_JPBRANCH_L7,        //  [7] bytes Pop0,  [0] bytes Dcd.
#endif

        cJL_JPBRANCH_L,         // note:  DcdPopO field not used.