hdf5_ep

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

 * Copyright by The HDF Group.                                               *

 * Copyright by the Board of Trustees of the University of Illinois.         *

 * All rights reserved.                                                      *

 *                                                                           *

 * This file is part of HDF5.  The full HDF5 copyright notice, including     *

 * terms governing use, modification, and redistribution, is contained in    *

 * the COPYING file, which can be found at the root of the source code       *

 * distribution tree, or in https://support.hdfgroup.org/ftp/HDF5/releases.  *

 * If you do not have access to either file, you may request a copy from     *

 * help@hdfgroup.org.                                                        *

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

​

/*

 * Purpose: Provides a skip list abstract data type.

 *

 *              (See "Deterministic Skip Lists" by Munro, Papadakis & Sedgewick)

 *

 *              (Implementation changed to a deterministic skip list from a

 *               probabilistic one.  This implementation uses a 1-2-3 skip list

 *               using arrays, as described by Munro, Papadakis & Sedgewick.

 *

 *               Arrays are allocated using a free list factory for each size

 *               that is a power of two.  Factories are created as soon as they

 *               are needed, and are never destroyed until the package is shut

 *               down.  There is no longer a maximum level or "p" value.

 *               -NAF 2008/11/05)

 *

 *              (See "Skip Lists: A Probabilistic Alternative to Balanced Trees"

 *               by William Pugh for additional information)

 *

 *              (This implementation has the optimization for reducing key

 *               key comparisons mentioned in section 3.5 of "A Skip List

 *               Cookbook" by William Pugh

 *              -Removed as our implementation of this was useless for a 1-2-3

 *               skip list.  The implementation in that document hurts

 *               performance, at least for integer keys. -NAF)

 *

 *              (Also, this implementation has a couple of home-grown

 *               optimizations, including setting the "update" vector to the

 *               actual 'forward' pointer to update, instead of the node

 *               containing the forward pointer -QAK

 *              -No longer uses update vector, as insertions/deletions are now

 *               always at level 0. -NAF)

 *

 *              (Note: This implementation does not have the information for

 *               implementing the "Linear List Operations" (like insert/delete/

 *               search by position) in section 3.4 of "A Skip List Cookbook",

 *               but they shouldn't be that hard to add, if necessary)

 *

 *              (This implementation has an additional backward pointer, which