kdb/modules/lcrash/kl_btnode.h

   1 /*
   2  * $Id: kl_btnode.h 1122 2004-12-21 23:26:23Z tjm $
   3  *
   4  * This file is part of libutil.
   5  * A library which provides auxiliary functions.
   6  * libutil is part of lkcdutils -- utilities for Linux kernel crash dumps.
   7  *
   8  * Created by Silicon Graphics, Inc.
   9  * Contributions by IBM, NEC, and others
  10  *
  11  * Copyright (C) 1999 - 2002 Silicon Graphics, Inc. All rights reserved.
  12  * Copyright (C) 2001, 2002 IBM Deutschland Entwicklung GmbH, IBM Corporation
  13  * Copyright 2000 Junichi Nomura, NEC Solutions <j-nomura@ce.jp.nec.com>
  14  *
  15  * This code is free software; you can redistribute it and/or modify
  16  * it under the terms of the GNU Lesser Public License as published by
  17  * the Free Software Foundation; either version 2.1 of the License, or
  18  * (at your option) any later version. See the file COPYING for more
  19  * information.
  20  */
  21
  22 #ifndef __KL_BTNODE_H
  23 #define __KL_BTNODE_H
  24
  25 /*
  26  * Node header struct for use in binary search tree routines
  27  */
  28 typedef struct btnode_s {
  29         struct btnode_s     *bt_left;
  30         struct btnode_s     *bt_right;
  31         struct btnode_s     *bt_parent;
  32         char                *bt_key;
  33         int                  bt_height;
  34 } btnode_t;
  35
  36 #define DUPLICATES_OK   1
  37
  38 /**
  39  ** btnode operation function prototypes
  40  **/
  41
  42 /* Return the hight of a given btnode_s struct in a tree. In the
  43  * event of an error (a NULL btnode_s pointer was passed in), a
  44  * value of -1 will be returned.
  45  */
  46 int kl_btnode_height(
  47         btnode_t*       /* pointer to btnode_s struct */);
  48
  49 /* Insert a btnode_s struct into a tree. After the insertion, the
  50  * tree will be left in a reasonibly ballanced state. Note that, if
  51  * the DUPLICATES_OK flag is set, duplicate keys will be inserted
  52  * into the tree (otherwise return an error). In the event of an
  53  * error, a value of -1 will be returned.
  54  */
  55 int kl_insert_btnode(
  56         btnode_t**      /* pointer to root of tree */,
  57         btnode_t*       /* pointer to btnode_s struct to insert */,
  58         int             /* flags (DUPLICATES_OK) */);
  59
  60 /* Finds a btnode in a tree and removes it, making sure to keep
  61  * the tree in a reasonably balanced state. As part of the
  62  * delete_btnode() operation, a call will be made to the free
  63  * function (passed in as a parameter) to free any application
  64  * specific data.
  65  */
  66 int kl_delete_btnode(
  67         btnode_t**      /* pointer to the root of the btree */,
  68         btnode_t*       /* pointer to btnode_s struct to delete */,
  69         void(*)(void*)  /* pointer to function to actually free the node */,
  70         int             /* flags */);
  71
  72 /* Traverse a tree looking for a particular key. In the event that
  73  * duplicate keys are allowed in the tree, returns the first occurance
  74  * of the search key found. A pointer to an int should be passed in
  75  * to hold the maximum depth reached in the search. Upon success,
  76  * returns a pointer to a btnode_s struct. Otherwise, a NULL pointer
  77  * will be returned.
  78  */
  79 btnode_t *_kl_find_btnode(
  80         btnode_t*       /* pointer to btnode_s struct to start search with */,
  81         char*           /* key we are looking for */,
  82         int*            /* pointer to where max depth vlaue will be placed */,
  83         size_t          /* if nonzero compare only first n chars of key */);
  84 #define kl_find_btnode(A, B, C) _kl_find_btnode(A, B, C, 0)
  85
  86 btnode_t *kl_first_btnode(
  87         btnode_t *      /* pointer to any btnode in a btree */);
  88
  89 btnode_t *kl_next_btnode(
  90         btnode_t *      /* pointer to current btnode */);
  91
  92 btnode_t *kl_prev_btnode(
  93         btnode_t *      /* Pointer to current btnode */);
  94
  95 #endif /* __KL_BTNODE_H */