1 /*
2 Copyright 2015-2016 David Anderson. All rights reserved.
3
4 This program is free software; you can redistribute it and/or modify it
5 under the terms of version 2 of the GNU General Public License as
6 published by the Free Software Foundation.
7
8 This program is distributed in the hope that it would be useful, but
9 WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
11
12 Further, this software is distributed without any warranty that it is
13 free of the rightful claim of any third person regarding infringement
14 or the like. Any license provided herein, whether implied or
15 otherwise, applies only to this software file. Patent licenses, if
16 any, provided herein do not apply to combinations of this program with
17 other software, or any other product whatsoever.
18
19 You should have received a copy of the GNU General Public License along
20 with this program; if not, write the Free Software Foundation, Inc., 51
21 Franklin Street - Fifth Floor, Boston MA 02110-1301, USA.
22 */
23
24 #include "globals.h"
25 #include "esb.h"
26 #include "dwarf_tsearch.h"
27 #include "helpertree.h"
28
29 #define TRUE 1
30 #define FALSE 0
31 /* WARNING: the tree walk functions will, if presented **tree
32 when *tree is wanted, simply find nothing. No error,
33 just bad results. So when a walk produces nothing
34 suspect a code mistake here.
35 The basic problem is void* is a terrible way to
36 pass in a pointer. But it's how tsearch was defined
37 long ago.
38 */
39 /* For .debug_info (not for tied file) */
40 struct Helpertree_Base_s helpertree_offsets_base_info;
41 /* For .debug_types (not for tied file) */
42 struct Helpertree_Base_s helpertree_offsets_base_types;
43
44 static struct Helpertree_Map_Entry_s *
helpertree_map_create_entry(Dwarf_Unsigned offset,int val)45 helpertree_map_create_entry(Dwarf_Unsigned offset,
46 int val)
47 {
48 struct Helpertree_Map_Entry_s *mp =
49 (struct Helpertree_Map_Entry_s *)
50 calloc(1,sizeof(struct Helpertree_Map_Entry_s));
51 if (!mp) {
52 return 0;
53 }
54 mp->hm_key = offset;
55 mp->hm_val = val;
56 return mp;
57 }
58 static void
helpertree_map_free_func(void * mx)59 helpertree_map_free_func(void *mx)
60 {
61 struct Helpertree_Map_Entry_s *m = mx;
62 free(m);
63 }
64
65 static int
helpertree_map_compare_func(const void * l,const void * r)66 helpertree_map_compare_func(const void *l, const void *r)
67 {
68 const struct Helpertree_Map_Entry_s *ml = l;
69 const struct Helpertree_Map_Entry_s *mr = r;
70 if (ml->hm_key < mr->hm_key) {
71 return -1;
72 }
73 if (ml->hm_key > mr->hm_key) {
74 return 1;
75 }
76 return 0;
77 }
78 static void
helpertree_map_destroy(void * map)79 helpertree_map_destroy(void *map)
80 {
81 /* tdestroy is not part of Posix. */
82 dwarf_tdestroy(map,helpertree_map_free_func);
83 }
84
85 /* Globally-visible functions follow this line. */
86
87 struct Helpertree_Map_Entry_s *
helpertree_add_entry(Dwarf_Unsigned offset,int val,struct Helpertree_Base_s * base)88 helpertree_add_entry(Dwarf_Unsigned offset,
89 int val,struct Helpertree_Base_s *base)
90 {
91 void *retval = 0;
92 struct Helpertree_Map_Entry_s *re = 0;
93 struct Helpertree_Map_Entry_s *e;
94 void **tree1 = 0;
95
96 tree1 = &base->hb_base;
97 e = helpertree_map_create_entry(offset,val);
98 /* tsearch records e's contents unless e
99 is already present . We must not free it till
100 destroy time if it got added to tree1. */
101 retval = dwarf_tsearch(e,tree1, helpertree_map_compare_func);
102 if (retval) {
103 re = *(struct Helpertree_Map_Entry_s **)retval;
104 if (re != e) {
105 /* We returned an existing record, e not needed.
106 Set val. */
107 re->hm_val = val;
108 helpertree_map_free_func(e);
109 } else {
110 /* Record e got added to tree1, do not free record e. */
111 }
112 return retval;
113 }
114 return NULL;
115 }
116
117 struct Helpertree_Map_Entry_s *
helpertree_find(Dwarf_Unsigned offset,struct Helpertree_Base_s * base)118 helpertree_find(Dwarf_Unsigned offset,struct Helpertree_Base_s *base)
119 {
120 void *retval = 0;
121 struct Helpertree_Map_Entry_s *re = 0;
122 struct Helpertree_Map_Entry_s *e = 0;
123
124 e = helpertree_map_create_entry(offset,0);
125 retval = dwarf_tfind(e,&base->hb_base, helpertree_map_compare_func);
126 if (retval) {
127 re = *(struct Helpertree_Map_Entry_s **)retval;
128 }
129 /* The one we created here must be deleted, it is dead.
130 We look at the returned one instead. */
131 helpertree_map_free_func(e);
132 return re;
133 }
134
135
136
137 void
helpertree_clear_statistics(struct Helpertree_Base_s * base)138 helpertree_clear_statistics(struct Helpertree_Base_s *base)
139 {
140 if(!base) {
141 return;
142 }
143 if (!base->hb_base) {
144 return;
145 }
146 helpertree_map_destroy(base->hb_base);
147 base->hb_base = 0;
148 }
149
150
151 #ifdef SELFTEST
152
153 struct Helpertree_Base_s testbase;
main()154 int main()
155 {
156 struct Helpertree_Map_Entry_s *re = 0;
157 int failcount = 0;
158
159 /* Test 1 */
160 re = helpertree_add_entry(0x1000,0,&testbase);
161 if (!re) {
162 printf("FAIL test1\n");
163 failcount++;
164 }
165 re = helpertree_add_entry(0x2000,0,&testbase);
166 if (!re) {
167 printf("FAIL test2\n");
168 failcount++;
169 }
170
171 re = helpertree_find(0x1000,&testbase);
172 if (!re) {
173 printf("FAIL test3\n");
174 failcount++;
175 }
176 re = helpertree_find(0x2000,&testbase);
177 if (!re) {
178 printf("FAIL test4\n");
179 failcount++;
180 }
181 re = helpertree_find(0x2004,&testbase);
182 if (re) {
183 printf("FAIL test5\n");
184 failcount++;
185 }
186 helpertree_clear_statistics(&testbase);
187 if (failcount) {
188 return 1;
189 }
190 printf("PASS helpertree\n");
191 return 0;
192 }
193 #endif /* SELFTEST */
194