psplay.h

Go to the documentation of this file.

/*
    psplay.h - probabilistic splay tree

  Copyright (C)
    2004, 2005, 2006,   Christian Thaeter <chth@gmx.net>
  Copyright (C)         Lumiera.org
    2007, 2008,         Christian Thaeter <ct@pipapo.org>

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the 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 General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/


#ifndef LIB_PSPLAY_H
#define LIB_PSPLAY_H

#include <stdint.h>
#include <stdio.h>


typedef struct psplaynode_struct psplaynode;
typedef psplaynode* PSplaynode;
struct psplaynode_struct
{
  PSplaynode left;
  PSplaynode right;
};

#define PSPLAYNODE_INITIALIZER {NULL, NULL}

typedef int (*psplay_cmp_fn)(const void* a, const void* b);


typedef void (*psplay_delete_fn)(PSplaynode node);


typedef const void* (*psplay_key_fn)(const PSplaynode node);


typedef struct psplay_struct psplay;
typedef psplay* PSplay;

struct psplay_struct
{
  PSplaynode tree;                      /* the tree */
  PSplaynode* found_parent;             /* maybe direct parent of last found node, used for fast remove */
  psplay_cmp_fn cmp;
  psplay_key_fn key;
  psplay_delete_fn del;

  size_t elem_cnt;
  unsigned log2;                        /* roughly log2 of the elem_cnt*/
};


static inline size_t
psplay_nelements (PSplay self)
{
  return self->elem_cnt;
};


PSplay
psplay_init (PSplay self, psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del);


PSplay
psplay_destroy (PSplay self);

PSplay
psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del);


void
psplay_delete (PSplay self);


PSplaynode
psplaynode_init (PSplaynode self);


PSplaynode
psplay_insert (PSplay self, PSplaynode node, int splayfactor);


PSplaynode
psplay_find (PSplay self, const void* key, int splayfactor);


PSplaynode
psplay_remove (PSplay self, PSplaynode node);


PSplaynode
psplay_remove_key (PSplay self, void* key);


void
psplay_delete_node (PSplay self, PSplaynode node);


void
psplay_delete_key (PSplay self, void* key);


enum psplay_order_enum
  {
    PSPLAY_PREORDER,
    PSPLAY_INORDER,
    PSPLAY_POSTORDER
  };

typedef psplay_delete_fn (*psplay_action_fn)(PSplaynode node, const enum psplay_order_enum which, int level, void* data);

extern const psplay_delete_fn PSPLAY_CONT;
extern const psplay_delete_fn PSPLAY_STOP;
extern const psplay_delete_fn PSPLAY_REMOVE;

int
psplay_walk (PSplay self, PSplaynode node, psplay_action_fn action, int level, void* data);


void
psplay_dump (PSplay self, FILE* dest);

#endif /*LIB_PSPLAY_H*/