3 //=============================================================================
7 * @author Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
9 //=============================================================================
11 #ifndef ACE_MAP_MANAGER_H
12 #define ACE_MAP_MANAGER_H
14 #include /**/ "ace/pre.h"
16 #include /**/ "ace/config-all.h"
18 #if !defined (ACE_LACKS_PRAGMA_ONCE)
20 #endif /* ACE_LACKS_PRAGMA_ONCE */
22 #include "ace/Basic_Types.h"
23 #include "ace/Global_Macros.h"
24 #include "ace/Default_Constants.h"
26 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
28 // Forward declaration.
32 * @class ACE_Map_Entry
34 * @brief An entry in the Map.
36 template <class EXT_ID
, class INT_ID
>
40 /// Initialize member variables.
41 ACE_Map_Entry () = default;
43 /// We need this destructor to keep some compilers from complaining.
44 /// It's just a no-op, however.
45 ~ACE_Map_Entry () = default;
47 /// Key used to look up an entry.
50 /// The contents of the entry itself.
53 /// Dump the state of an object.
56 /// Declare the dynamic allocation hooks.
57 ACE_ALLOC_HOOK_DECLARE
;
59 // = These are really private, but unfortunately template friends
63 ACE_UINT32
next () const;
66 void next (ACE_UINT32 n
);
69 ACE_UINT32
prev () const;
72 void prev (ACE_UINT32 p
);
74 /// Keeps track of the next entry.
77 /// Keeps track of the previous entry.
80 #if defined (ACE_HAS_LAZY_MAP_MANAGER)
82 /// Is this entry free?
84 #endif /* ACE_HAS_LAZY_MAP_MANAGER */
88 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
89 class ACE_Map_Iterator_Base
;
92 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
93 class ACE_Map_Const_Iterator_Base
;
96 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
97 class ACE_Map_Iterator
;
100 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
101 class ACE_Map_Const_Iterator
;
104 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
105 class ACE_Map_Reverse_Iterator
;
108 * @class ACE_Map_Manager
111 * Define a map abstraction that associates EXT_IDs with
114 * The EXT_ID must support @c operator==. This constraint can
115 * be alleviated via template specialization, as shown in the
116 * $ACE_ROOT/tests/Conn_Test.cpp test.
117 * This class uses an ACE_Allocator to allocate memory. The
118 * user can make this a persistant class by providing an
119 * ACE_Allocator with a persistable memory pool.
120 * This implementation of a map uses an array, which is searched
121 * linearly. For more efficient searching you should use the
122 * ACE_Hash_Map_Manager.
124 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
125 class ACE_Map_Manager
128 friend class ACE_Map_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
>;
129 friend class ACE_Map_Const_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
>;
130 friend class ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
>;
131 friend class ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
>;
132 friend class ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
>;
136 typedef INT_ID VALUE
;
137 typedef ACE_LOCK lock_type
;
138 typedef ACE_Map_Entry
<EXT_ID
, INT_ID
> ENTRY
;
139 typedef ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> ITERATOR
;
140 typedef ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> CONST_ITERATOR
;
141 typedef ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> REVERSE_ITERATOR
;
143 typedef ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> iterator
;
144 typedef ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> const_iterator
;
145 typedef ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> reverse_iterator
;
147 /// Initialize a ACE_Map_Manager with the ACE_DEFAULT_MAP_SIZE.
148 ACE_Map_Manager (ACE_Allocator
*alloc
= nullptr);
150 /// Initialize a ACE_Map_Manager with @a size entries.
151 ACE_Map_Manager (size_t size
,
152 ACE_Allocator
*alloc
= nullptr);
154 /// Initialize a ACE_Map_Manager with size @a length.
155 int open (size_t length
= ACE_DEFAULT_MAP_SIZE
,
156 ACE_Allocator
*alloc
= nullptr);
158 /// Close down a ACE_Map_Manager and release dynamically allocated
162 /// Close down a ACE_Map_Manager and release dynamically allocated
167 * Associate @a ext_id with @a int_id. If @a ext_id is already in the
168 * map then the ACE_Map_Entry is not changed.
169 * @retval 0 If a new entry is bound successfully.
170 * @retval 1 If an attempt is made to bind an existing entry.
171 * @retval -1 If failures occur.
173 int bind (const EXT_ID
&ext_id
,
174 const INT_ID
&int_id
);
177 * Reassociate @a ext_id with @a int_id. If @a ext_id is not in the
178 * map then behaves just like bind(). Otherwise, store the old
179 * values of @a ext_id and @a int_id into the "out" parameters and
180 * rebind the new parameters. This is very useful if you need to
181 * have an atomic way of updating <Map_Entries> and you also need
182 * full control over memory allocation.
183 * @retval 0 If a new entry is bound successfully.
184 * @retval 1 If an existing entry was rebound.
185 * @retval -1 If failures occur.
187 int rebind (const EXT_ID
&ext_id
,
188 const INT_ID
&int_id
,
193 * Reassociate @a ext_id with @a int_id. If @a ext_id is not in the
194 * map then behaves just like bind(). Otherwise, store the old
195 * values of @a int_id into the "out" parameter and rebind the new
197 * @retval 0 If a new entry is bound successfully.
198 * @retval 1 If an existing entry was rebound.
199 * @retval -1 If failures occur.
201 int rebind (const EXT_ID
&ext_id
,
202 const INT_ID
&int_id
,
205 /// Reassociate @a ext_id with @a int_id. Old values in the map are
207 int rebind (const EXT_ID
&ext_id
,
208 const INT_ID
&int_id
);
211 * Associate @a ext_id with @a int_id if and only if @a ext_id is not
212 * in the map. If @a ext_id is already in the map then the @a int_id
213 * parameter is overwritten with the existing value in the map
214 * @retval 0 If a new entry is bound successfully.
215 * @retval 1 If an attempt is made to bind an existing entry.
216 * @retval -1 If failures occur.
218 int trybind (const EXT_ID
&ext_id
,
222 * Locate @a ext_id and pass out parameter via @a int_id.
223 * @retval 0 If found.
224 * @retval -1 If not found.
226 int find (const EXT_ID
&ext_id
,
227 INT_ID
&int_id
) const;
229 /// Returns 0 if the @a ext_id is in the mapping, otherwise -1.
230 int find (const EXT_ID
&ext_id
) const;
233 * Unbind (remove) the @a ext_id from the map. Don't return the
234 * @a int_id to the caller (this is useful for collections where the
235 * @a int_ids are *not* dynamically allocated...) Returns 0 if
236 * successful, else -1.
238 int unbind (const EXT_ID
&ext_id
);
241 * Break any association of @a ext_id. Returns the value of @a int_id
242 * in case the caller needs to deallocate memory. Returns 0 if
243 * successful, else -1.
245 int unbind (const EXT_ID
&ext_id
,
249 * Unbind all entires.
253 /// Return the current size of the map.
254 size_t current_size () const;
256 /// Return the total size of the map.
257 size_t total_size () const;
260 * Returns a reference to the underlying ACE_LOCK. This makes it
261 * possible to acquire the lock explicitly, which can be useful in
262 * some cases if you instantiate the ACE_Atomic_Op with an
263 * ACE_Recursive_Mutex or ACE_Process_Mutex, or if you need to
264 * guard the state of an iterator.
265 * @note The right name would be lock, but HP/C++ will choke on that!
269 /// Dump the state of an object.
272 // = STL styled iterator factory functions.
274 /// Return forward iterator.
275 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> begin ();
276 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> end ();
278 /// Return reverse iterator.
279 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> rbegin ();
280 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> rend ();
282 /// Declare the dynamic allocation hooks.
283 ACE_ALLOC_HOOK_DECLARE
;
286 // = The following methods do the actual work.
288 // These methods assume that the locks are held by the private
291 /// Performs the binding of @a ext_id to @a int_id. Must be called
293 int bind_i (const EXT_ID
&ext_id
,
294 const INT_ID
&int_id
);
296 /// Bind an entry (without finding first). Must be called with locks
298 int shared_bind (const EXT_ID
&ext_id
,
299 const INT_ID
&int_id
);
301 /// Performs a rebinding of <ext_it> to @a int_id. Also, recovers old
302 /// values. Must be called with locks held.
303 int rebind_i (const EXT_ID
&ext_id
,
304 const INT_ID
&int_id
,
308 /// Performs a rebinding of <ext_it> to @a int_id. Also, recovers old
309 /// values. Must be called with locks held.
310 int rebind_i (const EXT_ID
&ext_id
,
311 const INT_ID
&int_id
,
314 /// Performs a rebinding of <ext_it> to @a int_id. Must be called
316 int rebind_i (const EXT_ID
&ext_id
,
317 const INT_ID
&int_id
);
319 /// Performs a conditional bind of @a int_id using @a ext_id as the
320 /// key. Must be called with locks held.
321 int trybind_i (const EXT_ID
&ext_id
,
324 /// Performs a find of @a int_id using @a ext_id as the key. Must be
325 /// called with locks held.
326 int find_i (const EXT_ID
&ext_id
,
329 /// Performs a find using @a ext_id as the key. Must be called with
331 int find_and_return_index (const EXT_ID
&ext_id
,
334 /// Performs an unbind of @a int_id using @a ext_id as the key. Must
335 /// be called with locks held.
336 int unbind_i (const EXT_ID
&ext_id
,
339 /// Performs an unbind using @a ext_id as the key. Must be called
341 int unbind_i (const EXT_ID
&ext_id
);
343 /// Performs an unbind using @a ext_id as the key. Must be called
345 int unbind_and_return_index (const EXT_ID
&ext_id
,
349 void unbind_slot (ACE_UINT32 slot
);
351 /// Resize the map. Must be called with locks held.
352 int resize_i (ACE_UINT32 size
);
354 /// Close down a <Map_Manager>. Must be called with locks held.
357 /// Returns 1 if <id1> == <id2>, else 0. This is defined as a
358 /// separate method to facilitate template specialization.
359 int equal (const EXT_ID
&id1
, const EXT_ID
&id2
);
361 /// This function returns the new size of the Map Manager. This
362 /// function is called when we run out of room and need to resize.
363 ACE_UINT32
new_size ();
365 /// Explicitly call the destructors and free up the
366 /// <search_structure_>.
367 void free_search_structure ();
369 /// Id of the free list sentinel.
370 ACE_UINT32
free_list_id () const;
372 /// Id of the occupied list sentinel.
373 ACE_UINT32
occupied_list_id () const;
375 /// Finds the next free slot.
376 int next_free (ACE_UINT32
&slot
);
378 /// Move from free list to occupied list.
379 void move_from_free_list_to_occupied_list (ACE_UINT32 slot
);
381 /// Move from occupied list to free list.
382 void move_from_occupied_list_to_free_list (ACE_UINT32 slot
);
384 #if defined (ACE_HAS_LAZY_MAP_MANAGER)
387 * In the case of lazy map managers, the movement of free slots from
388 * the occupied list to the free list is delayed until we run out of
389 * free slots in the free list. This function goes through the
390 * entire occupied list, moving free slots to the free list.
392 void move_all_free_slots_from_occupied_list ();
394 #endif /* ACE_HAS_LAZY_MAP_MANAGER */
397 void shared_move (ACE_UINT32 slot
,
398 ACE_Map_Entry
<EXT_ID
, INT_ID
> ¤t_list
,
399 ACE_UINT32 current_list_id
,
400 ACE_Map_Entry
<EXT_ID
, INT_ID
> &new_list
,
401 ACE_UINT32 new_list_id
);
403 /// Pointer to a memory allocator.
404 ACE_Allocator
*allocator_
;
406 /// Synchronization variable for the MT_SAFE ACE_Map_Manager.
407 mutable ACE_LOCK lock_
;
409 /// Implement the Map as a resizeable array of ACE_Map_Entry.
410 ACE_Map_Entry
<EXT_ID
, INT_ID
> *search_structure_
;
412 /// Total number of elements in this->search_structure_.
413 ACE_UINT32 total_size_
;
415 /// Current size of the map.
416 ACE_UINT32 cur_size_
;
419 ACE_Map_Entry
<EXT_ID
, INT_ID
> free_list_
;
422 ACE_Map_Entry
<EXT_ID
, INT_ID
> occupied_list_
;
426 /// Grow map exponentially up to 64K
427 MAX_EXPONENTIAL
= 64 * 1024,
429 /// Afterwards grow in chunks of 32K
430 LINEAR_INCREASE
= 32 * 1024
434 // = Disallow these operations.
435 void operator= (const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &) = delete;
436 ACE_Map_Manager (const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &) = delete;
440 * @class ACE_Map_Iterator_Base
442 * @brief Iterator for the ACE_Map_Manager.
444 * This class factors out common code from its templatized
447 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
448 class ACE_Map_Iterator_Base
451 /// Constructor. If head != 0, the iterator constructed is positioned
452 /// at the head of the map, it is positioned at the end otherwise.
453 ACE_Map_Iterator_Base (ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &mm
);
455 // = Iteration methods.
457 /// Pass back the next <entry> that hasn't been seen in the Set.
458 /// Returns 0 when all items have been seen, else 1.
459 int next (ACE_Map_Entry
<EXT_ID
, INT_ID
> *&next_entry
) const;
461 /// Returns 1 when all items have been seen, else 0.
464 /// Returns a reference to the interal element @c this is pointing to.
465 ACE_Map_Entry
<EXT_ID
, INT_ID
>& operator* () const;
467 /// Returns reference the Map_Manager that is being iterated
469 ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
>& map ();
471 /// Check if two iterators point to the same position
472 bool operator== (const ACE_Map_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
> &) const;
473 bool operator!= (const ACE_Map_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
> &) const;
475 /// Declare the dynamic allocation hooks.
476 ACE_ALLOC_HOOK_DECLARE
;
479 /// Move forward by one element in the set. Returns 0 when there's
480 /// no more item in the set after the current items, else 1.
483 /// Move backware by one element in the set. Returns 0 when there's
484 /// no more item in the set before the current item, else 1.
487 /// Dump the state of an object.
488 void dump_i () const;
490 /// Map we are iterating over.
491 ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> *map_man_
;
493 /// Keeps track of how far we've advanced...
498 * @class ACE_Map_Const_Iterator_Base
500 * @brief Const iterator for the ACE_Map_Manager.
502 * This class factors out common code from its templatized
505 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
506 class ACE_Map_Const_Iterator_Base
509 /// Constructor. If head != 0, the iterator constructed is positioned
510 /// at the head of the map, it is positioned at the end otherwise.
511 ACE_Map_Const_Iterator_Base (const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &mm
);
513 // = Iteration methods.
515 /// Pass back the next <entry> that hasn't been seen in the Set.
516 /// Returns 0 when all items have been seen, else 1.
517 int next (ACE_Map_Entry
<EXT_ID
, INT_ID
> *&next_entry
) const;
519 /// Returns 1 when all items have been seen, else 0.
522 /// Returns a reference to the interal element @c this is pointing to.
523 ACE_Map_Entry
<EXT_ID
, INT_ID
>& operator* () const;
525 /// Returns reference the Map_Manager that is being iterated
527 const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
>& map () const;
529 /// Check if two iterators point to the same position
530 bool operator== (const ACE_Map_Const_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
> &) const;
531 bool operator!= (const ACE_Map_Const_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
> &) const;
533 /// Declare the dynamic allocation hooks.
534 ACE_ALLOC_HOOK_DECLARE
;
537 /// Move forward by one element in the set. Returns 0 when there's
538 /// no more item in the set after the current items, else 1.
541 /// Move backware by one element in the set. Returns 0 when there's
542 /// no more item in the set before the current item, else 1.
545 /// Dump the state of an object.
546 void dump_i () const;
548 /// Map we are iterating over.
549 const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> *map_man_
;
551 /// Keeps track of how far we've advanced...
556 * @class ACE_Map_Iterator
558 * @brief Forward iterator for the ACE_Map_Manager.
560 * This class does not perform any internal locking of the
561 * ACE_Map_Manager it is iterating upon since locking is
562 * inherently inefficient and/or error-prone within an STL-style
563 * iterator. If you require locking, you can explicitly use an
564 * ACE_GUARD or ACE_READ_GUARD on the ACE_Map_Manager's
565 * internal lock, which is accessible via its mutex() method.
567 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
568 class ACE_Map_Iterator
: public ACE_Map_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
>
571 ACE_Map_Iterator (ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &mm
,
574 // = Iteration methods.
576 /// Move forward by one element in the set. Returns 0 when all the
577 /// items in the set have been seen, else 1.
580 /// Dump the state of an object.
583 // = STL styled iteration, compare, and reference functions.
586 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator++ ();
589 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator++ (int);
592 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator-- ();
595 ACE_Map_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator-- (int);
597 /// Declare the dynamic allocation hooks.
598 ACE_ALLOC_HOOK_DECLARE
;
602 * @class ACE_Map_Const_Iterator
604 * @brief Forward const iterator for the ACE_Map_Manager.
606 * This class does not perform any internal locking of the
607 * ACE_Map_Manager it is iterating upon since locking is
608 * inherently inefficient and/or error-prone within an STL-style
609 * iterator. If you require locking, you can explicitly use an
610 * ACE_GUARD or ACE_READ_GUARD on the ACE_Map_Manager's
611 * internal lock, which is accessible via its mutex() method.
613 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
614 class ACE_Map_Const_Iterator
: public ACE_Map_Const_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
>
617 ACE_Map_Const_Iterator (const ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &mm
,
620 // = Iteration methods.
622 /// Move forward by one element in the set. Returns 0 when all the
623 /// items in the set have been seen, else 1.
626 /// Dump the state of an object.
629 // = STL styled iteration, compare, and reference functions.
632 ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator++ ();
635 ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator++ (int);
638 ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator-- ();
641 ACE_Map_Const_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator-- (int);
643 /// Declare the dynamic allocation hooks.
644 ACE_ALLOC_HOOK_DECLARE
;
648 * @class ACE_Map_Reverse_Iterator
650 * @brief Reverse Iterator for the ACE_Map_Manager.
652 * This class does not perform any internal locking of the
653 * ACE_Map_Manager it is iterating upon since locking is
654 * inherently inefficient and/or error-prone within an STL-style
655 * iterator. If you require locking, you can explicitly use an
656 * ACE_GUARD or ACE_READ_GUARD on the ACE_Map_Manager's
657 * internal lock, which is accessible via its mutex() method.
659 template <class EXT_ID
, class INT_ID
, class ACE_LOCK
>
660 class ACE_Map_Reverse_Iterator
: public ACE_Map_Iterator_Base
<EXT_ID
, INT_ID
, ACE_LOCK
>
663 ACE_Map_Reverse_Iterator (ACE_Map_Manager
<EXT_ID
, INT_ID
, ACE_LOCK
> &mm
,
666 // = Iteration methods.
668 /// Move forward by one element in the set. Returns 0 when all the
669 /// items in the set have been seen, else 1.
672 /// Dump the state of an object.
675 // = STL styled iteration, compare, and reference functions.
678 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator++ ();
681 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator++ (int);
684 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> &operator-- ();
687 ACE_Map_Reverse_Iterator
<EXT_ID
, INT_ID
, ACE_LOCK
> operator-- (int);
689 /// Declare the dynamic allocation hooks.
690 ACE_ALLOC_HOOK_DECLARE
;
693 ACE_END_VERSIONED_NAMESPACE_DECL
695 #if defined (__ACE_INLINE__)
696 #include "ace/Map_Manager.inl"
697 #endif /* __ACE_INLINE__ */
699 #include "ace/Map_Manager.cpp"
701 #include /**/ "ace/post.h"
703 #endif /* ACE_MAP_MANAGER_H */