psplay.h

Go to the documentation of this file.

/*
    psplay.h - probabilistic splay tree

   Copyright (C)       (contributed to CinelerraCV)
     2004-2006,       Christian Thaeter <chth@gmx.net>
   Copyright (C)     
     2007, 2008,      Christian Thaeter <ct@pipapo.org>

  **Lumiera** 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. See the file COPYING for further details.
*/


#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*/