1#include "mupdf/fitz.h"
2
3#include <string.h>
4
5/* AA-tree */
6
7struct fz_tree_s
8{
9 char *key;
10 void *value;
11 fz_tree *left, *right;
12 int level;
13};
14
15static fz_tree tree_sentinel = { "", NULL, &tree_sentinel, &tree_sentinel, 0 };
16
17static fz_tree *fz_tree_new_node(fz_context *ctx, const char *key, void *value)
18{
19 fz_tree *node = fz_malloc_struct(ctx, fz_tree);
20 fz_try(ctx)
21 {
22 node->key = fz_strdup(ctx, key);
23 node->value = value;
24 node->left = node->right = &tree_sentinel;
25 node->level = 1;
26 }
27 fz_catch(ctx)
28 {
29 fz_free(ctx, node);
30 fz_rethrow(ctx);
31 }
32 return node;
33}
34
35void *fz_tree_lookup(fz_context *ctx, fz_tree *node, const char *key)
36{
37 if (node)
38 {
39 while (node != &tree_sentinel)
40 {
41 int c = strcmp(key, node->key);
42 if (c == 0)
43 return node->value;
44 else if (c < 0)
45 node = node->left;
46 else
47 node = node->right;
48 }
49 }
50 return NULL;
51}
52
53static fz_tree *fz_tree_skew(fz_tree *node)
54{
55 if (node->level != 0)
56 {
57 if (node->left->level == node->level)
58 {
59 fz_tree *save = node;
60 node = node->left;
61 save->left = node->right;
62 node->right = save;
63 }
64 node->right = fz_tree_skew(node->right);
65 }
66 return node;
67}
68
69static fz_tree *fz_tree_split(fz_tree *node)
70{
71 if (node->level != 0 && node->right->right->level == node->level)
72 {
73 fz_tree *save = node;
74 node = node->right;
75 save->right = node->left;
76 node->left = save;
77 node->level++;
78 node->right = fz_tree_split(node->right);
79 }
80 return node;
81}
82
83/*
84 Insert a new key/value pair and rebalance the tree.
85 Return the new root of the tree after inserting and rebalancing.
86 May be called with a NULL root to create a new tree.
87*/
88fz_tree *fz_tree_insert(fz_context *ctx, fz_tree *node, const char *key, void *value)
89{
90 if (node && node != &tree_sentinel)
91 {
92 int c = strcmp(key, node->key);
93 if (c < 0)
94 node->left = fz_tree_insert(ctx, node->left, key, value);
95 else
96 node->right = fz_tree_insert(ctx, node->right, key, value);
97 node = fz_tree_skew(node);
98 node = fz_tree_split(node);
99 return node;
100 }
101 else
102 {
103 return fz_tree_new_node(ctx, key, value);
104 }
105}
106
107void fz_drop_tree(fz_context *ctx, fz_tree *node, void (*dropfunc)(fz_context *ctx, void *value))
108{
109 if (node)
110 {
111 if (node->left != &tree_sentinel)
112 fz_drop_tree(ctx, node->left, dropfunc);
113 if (node->right != &tree_sentinel)
114 fz_drop_tree(ctx, node->right, dropfunc);
115 fz_free(ctx, node->key);
116 if (dropfunc)
117 dropfunc(ctx, node->value);
118 fz_free(ctx, node);
119 }
120}
121