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