aboutsummaryrefslogtreecommitdiffstats
path: root/src/vhdl/vhdl-ieee-std_logic_1164.adb
blob: 58ce607698622c34bf96c9e20d2e5bcc6e502f8b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
--  Nodes recognizer for ieee.std_logic_1164.
--  Copyright (C) 2002, 2003, 2004, 2005 Tristan Gingold
--
--  GHDL 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, or (at your option) any later
--  version.
--
--  GHDL is distributed in the hope that it will be useful, but WITHOUT ANY
--  WARRANTY; without even the implied warranty of MERCHANTABILITY or
--  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
--  for more details.
--
--  You should have received a copy of the GNU General Public License
--  along with GHDL; see the file COPYING.  If not, write to the Free
--  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
--  02111-1307, USA.
with Types; use Types;
with Name_Table;
with Std_Names; use Std_Names;
with Vhdl.Errors; use Vhdl.Errors;

package body Vhdl.Ieee.Std_Logic_1164 is
   function Is_Scalar_Parameter (Inter : Iir) return Boolean is
   begin
      return Get_Base_Type (Get_Type (Inter)) = Std_Ulogic_Type;
   end Is_Scalar_Parameter;

   function Is_Vector_Parameter (Inter : Iir) return Boolean
   is
      Base_Type : constant Iir := Get_Base_Type (Get_Type (Inter));
   begin
      return Base_Type = Std_Ulogic_Vector_Type
        or Base_Type = Std_Logic_Vector_Type;
   end Is_Vector_Parameter;

   --  Return True iff the profile of FUNC is: (l, r : std_ulogic)
   function Is_Scalar_Scalar_Function (Func : Iir) return Boolean
   is
      Inter : constant Iir := Get_Interface_Declaration_Chain (Func);
      Inter2 : Iir;
   begin
      if Get_Implicit_Definition (Func) /= Iir_Predefined_None then
         return False;
      end if;
      if Inter = Null_Iir or else not Is_Scalar_Parameter (Inter) then
         return False;
      end if;
      Inter2 := Get_Chain (Inter);
      if Inter2 =  Null_Iir or else not Is_Scalar_Parameter (Inter2) then
         return False;
      end if;
      if Get_Chain (Inter2) /= Null_Iir then
         return False;
      end if;

      return True;
   end Is_Scalar_Scalar_Function;

   --  Return True iff the profile of FUNC is: (l : std_ulogic)
   function Is_Scalar_Function (Func : Iir) return Boolean
   is
      Inter : constant Iir := Get_Interface_Declaration_Chain (Func);
   begin
      if Get_Implicit_Definition (Func) /= Iir_Predefined_None then
         return False;
      end if;
      if Inter = Null_Iir or else not Is_Scalar_Parameter (Inter) then
         return False;
      end if;
      if Get_Chain (Inter) /= Null_Iir then
         return False;
      end if;

      return True;
   end Is_Scalar_Function;

   --  Return True iff the profile of FUNC is: (l, r : std_[u]logic_vector)
   function Is_Vector_Vector_Function (Func : Iir) return Boolean
   is
      Inter : constant Iir := Get_Interface_Declaration_Chain (Func);
      Inter2 : Iir;
   begin
      if Get_Implicit_Definition (Func) /= Iir_Predefined_None then
         return False;
      end if;
      if Inter = Null_Iir or else not Is_Vector_Parameter (Inter) then
         return False;
      end if;
      Inter2 := Get_Chain (Inter);
      if Inter2 =  Null_Iir or else not Is_Vector_Parameter (Inter2) then
         return False;
      end if;
      if Get_Chain (Inter2) /= Null_Iir then
         return False;
      end if;

      return True;
   end Is_Vector_Vector_Function;

   --  Return True iff the profile of FUNC is: (l : std_[u]logic_vector)
   function Is_Vector_Function (Func : Iir) return Boolean
   is
      Inter : constant Iir := Get_Interface_Declaration_Chain (Func);
   begin
      if Get_Implicit_Definition (Func) /= Iir_Predefined_None then
         return False;
      end if;
      if Inter = Null_Iir or else not Is_Vector_Parameter (Inter) then
         return False;
      end if;
      if Get_Chain (Inter) /= Null_Iir then
         return False;
      end if;

      return True;
   end Is_Vector_Function;

   procedure Extract_Declarations (Pkg : Iir_Package_Declaration)
   is
      Error : exception;

      Decl : Iir;
      Def : Iir;
   begin
      Std_Logic_1164_Pkg := Pkg;

      Decl := Get_Declaration_Chain (Pkg);

      --  Skip a potential copyright constant.
      Decl := Skip_Copyright_Notice (Decl);

      --  The first declaration should be type std_ulogic.
      if Decl = Null_Iir
        or else Get_Kind (Decl) /= Iir_Kind_Type_Declaration
        or else Get_Identifier (Decl) /= Name_Std_Ulogic
      then
         raise Error;
      end if;

      Def := Get_Type_Definition (Decl);
      if Get_Kind (Def) /= Iir_Kind_Enumeration_Type_Definition then
         raise Error;
      end if;
      Std_Ulogic_Type := Def;

      --  Get node of some literals.
      declare
         use Name_Table;
         Lit_List : constant Iir_Flist := Get_Enumeration_Literal_List (Def);
      begin
         if Get_Nbr_Elements (Lit_List) /= 9 then
            raise Error;
         end if;
         Std_Ulogic_0 := Get_Nth_Element (Lit_List, 2);
         Std_Ulogic_1 := Get_Nth_Element (Lit_List, 3);
         if Get_Identifier (Std_Ulogic_0) /= Get_Identifier ('0')
           or else Get_Identifier (Std_Ulogic_1) /= Get_Identifier ('1')
         then
            raise Error;
         end if;
      end;

      --  The second declaration should be std_ulogic_vector.
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      if Decl = Null_Iir
        or else Get_Kind (Decl) /= Iir_Kind_Type_Declaration
        or else Get_Identifier (Decl) /= Name_Std_Ulogic_Vector
      then
         raise Error;
      end if;
      Def := Get_Type_Definition (Decl);
      if Get_Kind (Def) /= Iir_Kind_Array_Type_Definition then
         raise Error;
      end if;
      Std_Ulogic_Vector_Type := Def;

      --  The third declaration should be resolved.
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      if Decl = Null_Iir
        or else Get_Kind (Decl) /= Iir_Kind_Function_Declaration
      then
         --  FIXME: check name ?
         raise Error;
      end if;
      Resolved := Decl;

      --  The fourth declaration should be std_logic.
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      if Decl = Null_Iir
        or else Get_Kind (Decl) /= Iir_Kind_Subtype_Declaration
        or else Get_Identifier (Decl) /= Name_Std_Logic
      then
         raise Error;
      end if;
      Def := Get_Type (Decl);
      if Get_Kind (Def) /= Iir_Kind_Enumeration_Subtype_Definition then
         raise Error;
      end if;
      Std_Logic_Type := Def;

      --  The fifth declaration should be std_logic_vector.
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      if Decl = Null_Iir
        or else (Get_Kind (Decl) /= Iir_Kind_Type_Declaration
                   and then Get_Kind (Decl) /= Iir_Kind_Subtype_Declaration)
        or else Get_Identifier (Decl) /= Name_Std_Logic_Vector
      then
         raise Error;
      end if;
      Def := Get_Type (Decl);
--      if Get_Kind (Def) /= Iir_Kind_Array_Type_Definition then
--         raise Error;
--      end if;
      Std_Logic_Vector_Type := Def;

      --  Skip any declarations but functions.
      loop
         Decl := Get_Chain (Decl);
         exit when Decl = Null_Iir;

         if Get_Kind (Decl) = Iir_Kind_Function_Declaration then
            if Get_Identifier (Decl) = Name_Rising_Edge then
               Rising_Edge := Decl;
            elsif Get_Identifier (Decl) = Name_Falling_Edge then
               Falling_Edge := Decl;
            elsif Is_Scalar_Scalar_Function (Decl) then
               declare
                  Predefined : Iir_Predefined_Functions;
               begin
                  case Get_Identifier (Decl) is
                     when Name_And =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_And;
                     when Name_Nand =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_Nand;
                     when Name_Or =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_Or;
                     when Name_Nor =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_Nor;
                     when Name_Xor =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_Xor;
                     when Name_Xnor =>
                        Predefined := Iir_Predefined_Ieee_1164_Scalar_Xnor;
                     when others =>
                        Predefined := Iir_Predefined_None;
                  end case;
                  Set_Implicit_Definition (Decl, Predefined);
               end;
            elsif Is_Scalar_Function (Decl)
              and then Get_Identifier (Decl) = Name_Not
            then
               Set_Implicit_Definition
                 (Decl, Iir_Predefined_Ieee_1164_Scalar_Not);
            elsif Is_Vector_Vector_Function (Decl) then
               declare
                  Predefined : Iir_Predefined_Functions;
               begin
                  case Get_Identifier (Decl) is
                     when Name_And =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_And;
                     when Name_Nand =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_Nand;
                     when Name_Or =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_Or;
                     when Name_Nor =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_Nor;
                     when Name_Xor =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_Xor;
                     when Name_Xnor =>
                        Predefined := Iir_Predefined_Ieee_1164_Vector_Xnor;
                     when others =>
                        Predefined := Iir_Predefined_None;
                  end case;
                  Set_Implicit_Definition (Decl, Predefined);
               end;
            elsif Is_Vector_Function (Decl)
              and then Get_Identifier (Decl) = Name_Not
            then
               Set_Implicit_Definition
                 (Decl, Iir_Predefined_Ieee_1164_Vector_Not);
            end if;
         end if;
      end loop;

      --  Since rising_edge and falling_edge do not read activity of its
      --  parameter, clear the flag to allow more optimizations.
      if Rising_Edge /= Null_Iir then
         Set_Has_Active_Flag
           (Get_Interface_Declaration_Chain (Rising_Edge), False);
      else
         raise Error;
      end if;
      if Falling_Edge /= Null_Iir then
         Set_Has_Active_Flag
           (Get_Interface_Declaration_Chain (Falling_Edge), False);
      else
         raise Error;
      end if;

   exception
      when Error =>
         Error_Msg_Sem (+Pkg, "package ieee.std_logic_1164 is ill-formed");

         --  Clear all definitions.
         Std_Logic_1164_Pkg := Null_Iir;
         Std_Ulogic_Type := Null_Iir;
         Std_Ulogic_Vector_Type := Null_Iir;
         Std_Logic_Type := Null_Iir;
         Std_Logic_Vector_Type := Null_Iir;
         Std_Ulogic_0 := Null_Iir;
         Std_Ulogic_1 := Null_Iir;
         Rising_Edge := Null_Iir;
         Falling_Edge := Null_Iir;
   end Extract_Declarations;
end Vhdl.Ieee.Std_Logic_1164;
class="p">(node)) { if (index > 0) return NULL; return is_slot ? (void *)&root->rnode : node; } node = indirect_to_ptr(node); height = node->height; if (index > radix_tree_maxindex(height)) return NULL; shift = (height-1) * RADIX_TREE_MAP_SHIFT; do { slot = (struct radix_tree_node **) (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); node = rcu_dereference(*slot); if (node == NULL) return NULL; shift -= RADIX_TREE_MAP_SHIFT; height--; } while (height > 0); return is_slot ? (void *)slot : indirect_to_ptr(node); } /** * radix_tree_lookup_slot - lookup a slot in a radix tree * @root: radix tree root * @index: index key * * Returns: the slot corresponding to the position @index in the * radix tree @root. This is useful for update-if-exists operations. * * This function can be called under rcu_read_lock iff the slot is not * modified by radix_tree_replace_slot, otherwise it must be called * exclusive from other writers. Any dereference of the slot must be done * using radix_tree_deref_slot. */ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) { return (void **)radix_tree_lookup_element(root, index, 1); } EXPORT_SYMBOL(radix_tree_lookup_slot); /** * radix_tree_lookup - perform lookup operation on a radix tree * @root: radix tree root * @index: index key * * Lookup the item at the position @index in the radix tree @root. * * This function can be called under rcu_read_lock, however the caller * must manage lifetimes of leaf nodes (eg. RCU may also be used to free * them safely). No RCU barriers are required to access or modify the * returned item, however. */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { return radix_tree_lookup_element(root, index, 0); } EXPORT_SYMBOL(radix_tree_lookup); /** * radix_tree_next_hole - find the next hole (not-present entry) * @root: tree root * @index: index key * @max_scan: maximum range to search * * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest * indexed hole. * * Returns: the index of the hole if found, otherwise returns an index * outside of the set specified (in which case 'return - index >= max_scan' * will be true). In rare cases of index wrap-around, 0 will be returned. * * radix_tree_next_hole may be called under rcu_read_lock. However, like * radix_tree_gang_lookup, this will not atomically search a snapshot of * the tree at a single point in time. For example, if a hole is created * at index 5, then subsequently a hole is created at index 10, * radix_tree_next_hole covering both indexes may return 10 if called * under rcu_read_lock. */ unsigned long radix_tree_next_hole(struct radix_tree_root *root, unsigned long index, unsigned long max_scan) { unsigned long i; for (i = 0; i < max_scan; i++) { if (!radix_tree_lookup(root, index)) break; index++; if (index == 0) break; } return index; } EXPORT_SYMBOL(radix_tree_next_hole); /** * radix_tree_prev_hole - find the prev hole (not-present entry) * @root: tree root * @index: index key * @max_scan: maximum range to search * * Search backwards in the range [max(index-max_scan+1, 0), index] * for the first hole. * * Returns: the index of the hole if found, otherwise returns an index * outside of the set specified (in which case 'index - return >= max_scan' * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. * * radix_tree_next_hole may be called under rcu_read_lock. However, like * radix_tree_gang_lookup, this will not atomically search a snapshot of * the tree at a single point in time. For example, if a hole is created * at index 10, then subsequently a hole is created at index 5, * radix_tree_prev_hole covering both indexes may return 5 if called under * rcu_read_lock. */ unsigned long radix_tree_prev_hole(struct radix_tree_root *root, unsigned long index, unsigned long max_scan) { unsigned long i; for (i = 0; i < max_scan; i++) { if (!radix_tree_lookup(root, index)) break; index--; if (index == ULONG_MAX) break; } return index; } EXPORT_SYMBOL(radix_tree_prev_hole); static unsigned int __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, unsigned int max_items, unsigned long *next_index) { unsigned int nr_found = 0; unsigned int shift, height; unsigned long i; height = slot->height; if (height == 0) goto out; shift = (height-1) * RADIX_TREE_MAP_SHIFT; for ( ; height > 1; height--) { i = (index >> shift) & RADIX_TREE_MAP_MASK; for (;;) { if (slot->slots[i] != NULL) break; index &= ~((1UL << shift) - 1); index += 1UL << shift; if (index == 0) goto out; /* 32-bit wraparound */ i++; if (i == RADIX_TREE_MAP_SIZE) goto out; } shift -= RADIX_TREE_MAP_SHIFT; slot = rcu_dereference(slot->slots[i]); if (slot == NULL) goto out; } /* Bottom level: grab some items */ for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { index++; if (slot->slots[i]) { results[nr_found++] = &(slot->slots[i]); if (nr_found == max_items) goto out; } } out: *next_index = index; return nr_found; } /** * radix_tree_gang_lookup - perform multiple lookup on a radix tree * @root: radix tree root * @results: where the results of the lookup are placed * @first_index: start the lookup from this key * @max_items: place up to this many items at *results * * Performs an index-ascending scan of the tree for present items. Places * them at *@results and returns the number of items which were placed at * *@results. * * The implementation is naive. * * Like radix_tree_lookup, radix_tree_gang_lookup may be called under * rcu_read_lock. In this case, rather than the returned results being * an atomic snapshot of the tree at a single point in time, the semantics * of an RCU protected gang lookup are as though multiple radix_tree_lookups * have been issued in individual locks, and results stored in 'results'. */ unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items) { unsigned long max_index; struct radix_tree_node *node; unsigned long cur_index = first_index; unsigned int ret; node = rcu_dereference(root->rnode); if (!node) return 0; if (!radix_tree_is_indirect_ptr(node)) { if (first_index > 0) return 0; results[0] = node; return 1; } node = indirect_to_ptr(node); max_index = radix_tree_maxindex(node->height); ret = 0; while (ret < max_items) { unsigned int nr_found, slots_found, i; unsigned long next_index; /* Index of next search */ if (cur_index > max_index) break; slots_found = __lookup(node, (void ***)results + ret, cur_index, max_items - ret, &next_index); nr_found = 0; for (i = 0; i < slots_found; i++) { struct radix_tree_node *slot; slot = *(((void ***)results)[ret + i]); if (!slot) continue; results[ret + nr_found] = indirect_to_ptr(rcu_dereference(slot)); nr_found++; } ret += nr_found; if (next_index == 0) break; cur_index = next_index; } return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup); /** * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree * @root: radix tree root * @results: where the results of the lookup are placed * @first_index: start the lookup from this key * @max_items: place up to this many items at *results * * Performs an index-ascending scan of the tree for present items. Places * their slots at *@results and returns the number of items which were * placed at *@results. * * The implementation is naive. * * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must * be dereferenced with radix_tree_deref_slot, and if using only RCU * protection, radix_tree_deref_slot may fail requiring a retry. */ unsigned int radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, unsigned long first_index, unsigned int max_items) { unsigned long max_index; struct radix_tree_node *node; unsigned long cur_index = first_index; unsigned int ret; node = rcu_dereference(root->rnode); if (!node) return 0; if (!radix_tree_is_indirect_ptr(node)) { if (first_index > 0) return 0; results[0] = (void **)&root->rnode; return 1; } node = indirect_to_ptr(node); max_index = radix_tree_maxindex(node->height); ret = 0; while (ret < max_items) { unsigned int slots_found; unsigned long next_index; /* Index of next search */ if (cur_index > max_index) break; slots_found = __lookup(node, results + ret, cur_index, max_items - ret, &next_index); ret += slots_found; if (next_index == 0) break; cur_index = next_index; } return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_slot); /** * radix_tree_shrink - shrink height of a radix tree to minimal * @root radix tree root */ static inline void radix_tree_shrink(struct radix_tree_root *root) { /* try to shrink tree height */ while (root->height > 0) { struct radix_tree_node *to_free = root->rnode; void *newptr; BUG_ON(!radix_tree_is_indirect_ptr(to_free)); to_free = indirect_to_ptr(to_free); /* * The candidate node has more than one child, or its child * is not at the leftmost slot, we cannot shrink. */ if (to_free->count != 1) break; if (!to_free->slots[0]) break; /* * We don't need rcu_assign_pointer(), since we are simply * moving the node from one part of the tree to another: if it * was safe to dereference the old pointer to it * (to_free->slots[0]), it will be safe to dereference the new * one (root->rnode) as far as dependent read barriers go. */ newptr = to_free->slots[0]; if (root->height > 1) newptr = ptr_to_indirect(newptr); root->rnode = newptr; root->height--; /* * We have a dilemma here. The node's slot[0] must not be * NULLed in case there are concurrent lookups expecting to * find the item. However if this was a bottom-level node, * then it may be subject to the slot pointer being visible * to callers dereferencing it. If item corresponding to * slot[0] is subsequently deleted, these callers would expect * their slot to become empty sooner or later. * * For example, lockless pagecache will look up a slot, deref * the page pointer, and if the page is 0 refcount it means it * was concurrently deleted from pagecache so try the deref * again. Fortunately there is already a requirement for logic * to retry the entire slot lookup -- the indirect pointer * problem (replacing direct root node with an indirect pointer * also results in a stale slot). So tag the slot as indirect * to force callers to retry. */ if (root->height == 0) *((unsigned long *)&to_free->slots[0]) |= RADIX_TREE_INDIRECT_PTR; radix_tree_node_free(root, to_free); } } /** * radix_tree_delete - delete an item from a radix tree * @root: radix tree root * @index: index key * * Remove the item at @index from the radix tree rooted at @root. * * Returns the address of the deleted item, or NULL if it was not present. */ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) { /* * The radix tree path needs to be one longer than the maximum path * since the "list" is null terminated. */ struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; struct radix_tree_node *slot = NULL; struct radix_tree_node *to_free; unsigned int height, shift; int offset; height = root->height; if (index > radix_tree_maxindex(height)) goto out; slot = root->rnode; if (height == 0) { root->rnode = NULL; goto out; } slot = indirect_to_ptr(slot); shift = (height - 1) * RADIX_TREE_MAP_SHIFT; pathp->node = NULL; do { if (slot == NULL) goto out; pathp++; offset = (index >> shift) & RADIX_TREE_MAP_MASK; pathp->offset = offset; pathp->node = slot; slot = slot->slots[offset]; shift -= RADIX_TREE_MAP_SHIFT; height--; } while (height > 0); if (slot == NULL) goto out; to_free = NULL; /* Now free the nodes we do not need anymore */ while (pathp->node) { pathp->node->slots[pathp->offset] = NULL; pathp->node->count--; /* * Queue the node for deferred freeing after the * last reference to it disappears (set NULL, above). */ if (to_free) radix_tree_node_free(root, to_free); if (pathp->node->count) { if (pathp->node == indirect_to_ptr(root->rnode)) radix_tree_shrink(root); goto out; } /* Node with zero slots in use so free it */ to_free = pathp->node; pathp--; } root->height = 0; root->rnode = NULL; if (to_free) radix_tree_node_free(root, to_free); out: return slot; } EXPORT_SYMBOL(radix_tree_delete); static void radix_tree_node_destroy( struct radix_tree_root *root, struct radix_tree_node *node, void (*slot_free)(void *)) { int i; for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { struct radix_tree_node *slot = node->slots[i]; BUG_ON(radix_tree_is_indirect_ptr(slot)); if (slot == NULL) continue; if (node->height == 1) { if (slot_free) slot_free(slot); } else { radix_tree_node_destroy(root, slot, slot_free); } } radix_tree_node_free(root, node); } void radix_tree_destroy( struct radix_tree_root *root, void (*slot_free)(void *)) { struct radix_tree_node *node = root->rnode; if (node == NULL) return; if (!radix_tree_is_indirect_ptr(node)) { if (slot_free) slot_free(node); } else { node = indirect_to_ptr(node); radix_tree_node_destroy(root, node, slot_free); } radix_tree_init(root); } void radix_tree_init(struct radix_tree_root *root) { memset(root, 0, sizeof(*root)); root->node_alloc = rcu_node_alloc; root->node_free = rcu_node_free; } void radix_tree_set_alloc_callbacks( struct radix_tree_root *root, radix_tree_alloc_fn_t *node_alloc, radix_tree_free_fn_t *node_free, void *node_alloc_free_arg) { root->node_alloc = node_alloc; root->node_free = node_free; root->node_alloc_free_arg = node_alloc_free_arg; } static __init unsigned long __maxindex(unsigned int height) { unsigned int width = height * RADIX_TREE_MAP_SHIFT; int shift = RADIX_TREE_INDEX_BITS - width; if (shift < 0) return ~0UL; if (shift >= BITS_PER_LONG) return 0UL; return ~0UL >> shift; } static __init int radix_tree_init_maxindex(void) { unsigned int i; for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) height_to_maxindex[i] = __maxindex(i); return 0; } /* pre-SMP just so it runs before 'normal' initcalls */ presmp_initcall(radix_tree_init_maxindex);