dict.h 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
  1. /*
  2. * Dictionary Abstract Data Type
  3. * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
  4. *
  5. * Free Software License:
  6. *
  7. * All rights are reserved by the author, with the following exceptions:
  8. * Permission is granted to freely reproduce and distribute this software,
  9. * possibly in exchange for a fee, provided that this copyright notice appears
  10. * intact. Permission is also granted to adapt this software to produce
  11. * derivative works, as long as the modified versions carry this copyright
  12. * notice and additional notices stating that the work has been modified.
  13. * This source code may be translated into executable form and incorporated
  14. * into proprietary software; there is no requirement for such software to
  15. * contain a copyright notice related to this source.
  16. *
  17. * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $
  18. * $Name: $
  19. */
  20. #ifndef DICT_H
  21. #define DICT_H
  22. #include <limits.h>
  23. /*
  24. * Blurb for inclusion into C++ translation units
  25. */
  26. #ifdef __cplusplus
  27. extern "C" {
  28. #endif
  29. typedef unsigned long dictcount_t;
  30. #define DICTCOUNT_T_MAX ULONG_MAX
  31. /*
  32. * The dictionary is implemented as a red-black tree
  33. */
  34. typedef enum { dnode_red, dnode_black } dnode_color_t;
  35. typedef struct dnode_t {
  36. struct dnode_t *dict_left;
  37. struct dnode_t *dict_right;
  38. struct dnode_t *dict_parent;
  39. dnode_color_t dict_color;
  40. const void *dict_key;
  41. void *dict_data;
  42. } dnode_t;
  43. typedef int (*dict_comp_t)(const void *, const void *);
  44. typedef dnode_t *(*dnode_alloc_t)(void *);
  45. typedef void (*dnode_free_t)(dnode_t *, void *);
  46. typedef struct dict_t {
  47. dnode_t dict_nilnode;
  48. dictcount_t dict_nodecount;
  49. dictcount_t dict_maxcount;
  50. dict_comp_t dict_compare;
  51. dnode_alloc_t dict_allocnode;
  52. dnode_free_t dict_freenode;
  53. void *dict_context;
  54. int dict_dupes;
  55. } dict_t;
  56. typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
  57. typedef struct dict_load_t {
  58. dict_t *dict_dictptr;
  59. dnode_t dict_nilnode;
  60. } dict_load_t;
  61. extern dict_t *dict_create(dictcount_t, dict_comp_t);
  62. extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
  63. extern void dict_destroy(dict_t *);
  64. extern void dict_free_nodes(dict_t *);
  65. extern void dict_free(dict_t *);
  66. extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
  67. extern void dict_init_like(dict_t *, const dict_t *);
  68. extern int dict_verify(dict_t *);
  69. extern int dict_similar(const dict_t *, const dict_t *);
  70. extern dnode_t *dict_lookup(dict_t *, const void *);
  71. extern dnode_t *dict_lower_bound(dict_t *, const void *);
  72. extern dnode_t *dict_upper_bound(dict_t *, const void *);
  73. extern void dict_insert(dict_t *, dnode_t *, const void *);
  74. extern dnode_t *dict_delete(dict_t *, dnode_t *);
  75. extern int dict_alloc_insert(dict_t *, const void *, void *);
  76. extern void dict_delete_free(dict_t *, dnode_t *);
  77. extern dnode_t *dict_first(dict_t *);
  78. extern dnode_t *dict_last(dict_t *);
  79. extern dnode_t *dict_next(dict_t *, dnode_t *);
  80. extern dnode_t *dict_prev(dict_t *, dnode_t *);
  81. extern dictcount_t dict_count(dict_t *);
  82. extern int dict_isempty(dict_t *);
  83. extern int dict_isfull(dict_t *);
  84. extern int dict_contains(dict_t *, dnode_t *);
  85. extern void dict_allow_dupes(dict_t *);
  86. extern int dnode_is_in_a_dict(dnode_t *);
  87. extern dnode_t *dnode_create(void *);
  88. extern dnode_t *dnode_init(dnode_t *, void *);
  89. extern void dnode_destroy(dnode_t *);
  90. extern void *dnode_get(dnode_t *);
  91. extern const void *dnode_getkey(dnode_t *);
  92. extern void dnode_put(dnode_t *, void *);
  93. extern void dict_process(dict_t *, void *, dnode_process_t);
  94. extern void dict_load_begin(dict_load_t *, dict_t *);
  95. extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
  96. extern void dict_load_end(dict_load_t *);
  97. extern void dict_merge(dict_t *, dict_t *);
  98. #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
  99. #define dict_count(D) ((D)->dict_nodecount)
  100. #define dict_isempty(D) ((D)->dict_nodecount == 0)
  101. #define dnode_get(N) ((N)->dict_data)
  102. #define dnode_getkey(N) ((N)->dict_key)
  103. #define dnode_put(N, X) ((N)->dict_data = (X))
  104. #ifdef __cplusplus
  105. }
  106. #endif
  107. #endif