libsc  1.6.0
src/sc_containers.h
Go to the documentation of this file.
00001 /*
00002   This file is part of the SC Library.
00003   The SC Library provides support for parallel scientific applications.
00004 
00005   Copyright (C) 2010 The University of Texas System
00006 
00007   The SC Library is free software; you can redistribute it and/or
00008   modify it under the terms of the GNU Lesser General Public
00009   License as published by the Free Software Foundation; either
00010   version 2.1 of the License, or (at your option) any later version.
00011 
00012   The SC Library is distributed in the hope that it will be useful,
00013   but WITHOUT ANY WARRANTY; without even the implied warranty of
00014   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015   Lesser General Public License for more details.
00016 
00017   You should have received a copy of the GNU Lesser General Public
00018   License along with the SC Library; if not, write to the Free Software
00019   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00020   02110-1301, USA.
00021 */
00022 
00023 #ifndef SC_CONTAINERS_H
00024 #define SC_CONTAINERS_H
00025 
00040 #include <sc_obstack.h>
00041 
00042 SC_EXTERN_C_BEGIN;
00043 
00044 /* Hash macros from lookup3.c by Bob Jenkins, May 2006, public domain. */
00045 #define sc_hash_rot(x,k) (((x) << (k)) | ((x) >> (32 - (k))))
00046 #define sc_hash_mix(a,b,c) ((void)                                      \
00047                             (a -= c, a ^= sc_hash_rot(c, 4), c += b,    \
00048                              b -= a, b ^= sc_hash_rot(a, 6), a += c,    \
00049                              c -= b, c ^= sc_hash_rot(b, 8), b += a,    \
00050                              a -= c, a ^= sc_hash_rot(c,16), c += b,    \
00051                              b -= a, b ^= sc_hash_rot(a,19), a += c,    \
00052                              c -= b, c ^= sc_hash_rot(b, 4), b += a))
00053 #define sc_hash_final(a,b,c) ((void)                            \
00054                               (c ^= b, c -= sc_hash_rot(b,14),  \
00055                                a ^= c, a -= sc_hash_rot(c,11),  \
00056                                b ^= a, b -= sc_hash_rot(a,25),  \
00057                                c ^= b, c -= sc_hash_rot(b,16),  \
00058                                a ^= c, a -= sc_hash_rot(c, 4),  \
00059                                b ^= a, b -= sc_hash_rot(a,14),  \
00060                                c ^= b, c -= sc_hash_rot(b,24)))
00061 
00067 typedef unsigned    (*sc_hash_function_t) (const void *v, const void *u);
00068 
00073 typedef int         (*sc_equal_function_t) (const void *v1,
00074                                             const void *v2, const void *u);
00075 
00081 typedef int         (*sc_hash_foreach_t) (void **v, const void *u);
00082 
00092 typedef struct sc_array
00093 {
00094   /* interface variables */
00095   size_t              elem_size;        
00096   size_t              elem_count;       
00098   /* implementation variables */
00099   ssize_t             byte_alloc;       
00104   char               *array;    
00105 }
00106 sc_array_t;
00107 
00109 #define SC_ARRAY_IS_OWNER(a) ((a)->byte_alloc >= 0)
00110 
00111 #define SC_ARRAY_BYTE_ALLOC(a) ((size_t) \
00112          (SC_ARRAY_IS_OWNER (a) ? (a)->byte_alloc : -((a)->byte_alloc + 1)))
00113 
00120 size_t              sc_array_memory_used (sc_array_t * array, int is_dynamic);
00121 
00126 sc_array_t         *sc_array_new (size_t elem_size);
00127 
00134 sc_array_t         *sc_array_new_size (size_t elem_size, size_t elem_count);
00135 
00143 sc_array_t         *sc_array_new_view (sc_array_t * array,
00144                                        size_t offset, size_t length);
00145 
00152 sc_array_t         *sc_array_new_data (void *base,
00153                                        size_t elem_size, size_t elem_count);
00154 
00158 void                sc_array_destroy (sc_array_t * array);
00159 
00164 void                sc_array_init (sc_array_t * array, size_t elem_size);
00165 
00172 void                sc_array_init_size (sc_array_t * array,
00173                                         size_t elem_size, size_t elem_count);
00174 
00183 void                sc_array_init_view (sc_array_t * view, sc_array_t * array,
00184                                         size_t offset, size_t length);
00185 
00193 void                sc_array_init_data (sc_array_t * view, void *base,
00194                                         size_t elem_size, size_t elem_count);
00195 
00202 void                sc_array_reset (sc_array_t * array);
00203 
00211 void                sc_array_truncate (sc_array_t * array);
00212 
00220 void                sc_array_resize (sc_array_t * array, size_t new_count);
00221 
00227 void                sc_array_copy (sc_array_t * dest, sc_array_t * src);
00228 
00233 void                sc_array_sort (sc_array_t * array,
00234                                    int (*compar) (const void *,
00235                                                   const void *));
00236 
00242 int                 sc_array_is_sorted (sc_array_t * array,
00243                                         int (*compar) (const void *,
00244                                                        const void *));
00245 
00252 int                 sc_array_is_equal (sc_array_t * array,
00253                                        sc_array_t * other);
00254 
00260 void                sc_array_uniq (sc_array_t * array,
00261                                    int (*compar) (const void *,
00262                                                   const void *));
00263 
00270 ssize_t             sc_array_bsearch (sc_array_t * array,
00271                                       const void *key,
00272                                       int (*compar) (const void *,
00273                                                      const void *));
00274 
00280 typedef             size_t (*sc_array_type_t) (sc_array_t * array,
00281                                                size_t index, void *data);
00282 
00299 void                sc_array_split (sc_array_t * array, sc_array_t * offsets,
00300                                     size_t num_types, sc_array_type_t type_fn,
00301                                     void *data);
00302 
00310 int                 sc_array_is_permutation (sc_array_t * array);
00311 
00323 void                sc_array_permute (sc_array_t * array,
00324                                       sc_array_t * newindices, int keepperm);
00325 
00329 unsigned            sc_array_checksum (sc_array_t * array);
00330 
00344 size_t              sc_array_pqueue_add (sc_array_t * array,
00345                                          void *temp,
00346                                          int (*compar) (const void *,
00347                                                         const void *));
00348 
00358 size_t              sc_array_pqueue_pop (sc_array_t * array,
00359                                          void *result,
00360                                          int (*compar) (const void *,
00361                                                         const void *));
00362 
00366 /*@unused@*/
00367 static inline void *
00368 sc_array_index (sc_array_t * array, size_t iz)
00369 {
00370   SC_ASSERT (iz < array->elem_count);
00371 
00372   return (void *) (array->array + (array->elem_size * iz));
00373 }
00374 
00378 /*@unused@*/
00379 static inline void *
00380 sc_array_index_int (sc_array_t * array, int i)
00381 {
00382   SC_ASSERT (i >= 0 && (size_t) i < array->elem_count);
00383 
00384   return (void *) (array->array + (array->elem_size * (size_t) i));
00385 }
00386 
00390 /*@unused@*/
00391 static inline void *
00392 sc_array_index_long (sc_array_t * array, long l)
00393 {
00394   SC_ASSERT (l >= 0 && (size_t) l < array->elem_count);
00395 
00396   return (void *) (array->array + (array->elem_size * (size_t) l));
00397 }
00398 
00402 /*@unused@*/
00403 static inline void *
00404 sc_array_index_ssize_t (sc_array_t * array, ssize_t is)
00405 {
00406   SC_ASSERT (is >= 0 && (size_t) is < array->elem_count);
00407 
00408   return (void *) (array->array + (array->elem_size * (size_t) is));
00409 }
00410 
00414 /*@unused@*/
00415 static inline void *
00416 sc_array_index_int16 (sc_array_t * array, int16_t i16)
00417 {
00418   SC_ASSERT (i16 >= 0 && (size_t) i16 < array->elem_count);
00419 
00420   return (void *) (array->array + (array->elem_size * (size_t) i16));
00421 }
00422 
00426 /*@unused@*/
00427 static inline       size_t
00428 sc_array_position (sc_array_t * array, void *element)
00429 {
00430   size_t              position;
00431 
00432   SC_ASSERT (array->array <= (char *) element);
00433   SC_ASSERT (((char *) element - array->array) % array->elem_size == 0);
00434 
00435   position = ((char *) element - array->array) / array->elem_size;
00436   SC_ASSERT (position < array->elem_count);
00437 
00438   return position;
00439 }
00440 
00446 /*@unused@*/
00447 static inline void *
00448 sc_array_pop (sc_array_t * array)
00449 {
00450   SC_ASSERT (SC_ARRAY_IS_OWNER (array));
00451   SC_ASSERT (array->elem_count > 0);
00452 
00453   return (void *) (array->array + (array->elem_size * --array->elem_count));
00454 }
00455 
00460 /*@unused@*/
00461 static inline void *
00462 sc_array_push_count (sc_array_t * array, size_t add_count)
00463 {
00464   const size_t        old_count = array->elem_count;
00465   const size_t        new_count = old_count + add_count;
00466 
00467   SC_ASSERT (SC_ARRAY_IS_OWNER (array));
00468 
00469   if (array->elem_size * new_count > (size_t) array->byte_alloc) {
00470     sc_array_resize (array, new_count);
00471   }
00472   else {
00473     array->elem_count = new_count;
00474   }
00475 
00476   return (void *) (array->array + array->elem_size * old_count);
00477 }
00478 
00483 /*@unused@*/
00484 static inline void *
00485 sc_array_push (sc_array_t * array)
00486 {
00487   return sc_array_push_count (array, 1);
00488 }
00489 
00496 typedef struct sc_mempool
00497 {
00498   /* interface variables */
00499   size_t              elem_size;        
00500   size_t              elem_count;       
00502   /* implementation variables */
00503   struct obstack      obstack;  
00504   sc_array_t          freed;    
00505 }
00506 sc_mempool_t;
00507 
00512 size_t              sc_mempool_memory_used (sc_mempool_t * mempool);
00513 
00518 sc_mempool_t       *sc_mempool_new (size_t elem_size);
00519 
00523 void                sc_mempool_destroy (sc_mempool_t * mempool);
00524 
00527 void                sc_mempool_truncate (sc_mempool_t * mempool);
00528 
00533 /*@unused@*/
00534 static inline void *
00535 sc_mempool_alloc (sc_mempool_t * mempool)
00536 {
00537   void               *ret;
00538   sc_array_t         *freed = &mempool->freed;
00539 
00540   ++mempool->elem_count;
00541 
00542   if (freed->elem_count > 0) {
00543     ret = *(void **) sc_array_pop (freed);
00544   }
00545   else {
00546     ret = obstack_alloc (&mempool->obstack, (int) mempool->elem_size);
00547   }
00548 
00549 #ifdef SC_DEBUG
00550   memset (ret, -1, mempool->elem_size);
00551 #endif
00552 
00553   return ret;
00554 }
00555 
00559 /*@unused@*/
00560 static inline void
00561 sc_mempool_free (sc_mempool_t * mempool, void *elem)
00562 {
00563   sc_array_t         *freed = &mempool->freed;
00564 
00565   SC_ASSERT (mempool->elem_count > 0);
00566 
00567 #ifdef SC_DEBUG
00568   memset (elem, -1, mempool->elem_size);
00569 #endif
00570 
00571   --mempool->elem_count;
00572 
00573   *(void **) sc_array_push (freed) = elem;
00574 }
00575 
00578 typedef struct sc_link
00579 {
00580   void               *data;
00581   struct sc_link     *next;
00582 }
00583 sc_link_t;
00584 
00587 typedef struct sc_list
00588 {
00589   /* interface variables */
00590   size_t              elem_count;
00591   sc_link_t          *first;
00592   sc_link_t          *last;
00593 
00594   /* implementation variables */
00595   int                 allocator_owned;
00596   sc_mempool_t       *allocator;        /* must allocate sc_link_t */
00597 }
00598 sc_list_t;
00599 
00606 size_t              sc_list_memory_used (sc_list_t * list, int is_dynamic);
00607 
00611 sc_list_t          *sc_list_new (sc_mempool_t * allocator);
00612 
00616 void                sc_list_destroy (sc_list_t * list);
00617 
00622 void                sc_list_init (sc_list_t * list, sc_mempool_t * allocator);
00623 
00629 void                sc_list_reset (sc_list_t * list);
00630 
00635 void                sc_list_unlink (sc_list_t * list);
00636 
00637 void                sc_list_prepend (sc_list_t * list, void *data);
00638 void                sc_list_append (sc_list_t * list, void *data);
00639 
00643 void                sc_list_insert (sc_list_t * list,
00644                                     sc_link_t * pred, void *data);
00645 
00651 void               *sc_list_remove (sc_list_t * list, sc_link_t * pred);
00652 
00656 void               *sc_list_pop (sc_list_t * list);
00657 
00661 typedef struct sc_hash
00662 {
00663   /* interface variables */
00664   size_t              elem_count;       
00666   /* implementation variables */
00667   sc_array_t         *slots;    
00668   void               *user_data;        
00669   sc_hash_function_t  hash_fn;
00670   sc_equal_function_t equal_fn;
00671   size_t              resize_checks, resize_actions;
00672   int                 allocator_owned;
00673   sc_mempool_t       *allocator;        
00674 }
00675 sc_hash_t;
00676 
00683 unsigned            sc_hash_function_string (const void *s, const void *u);
00684 
00689 size_t              sc_hash_memory_used (sc_hash_t * hash);
00690 
00698 sc_hash_t          *sc_hash_new (sc_hash_function_t hash_fn,
00699                                  sc_equal_function_t equal_fn,
00700                                  void *user_data, sc_mempool_t * allocator);
00701 
00707 void                sc_hash_destroy (sc_hash_t * hash);
00708 
00714 void                sc_hash_truncate (sc_hash_t * hash);
00715 
00722 void                sc_hash_unlink (sc_hash_t * hash);
00723 
00728 void                sc_hash_unlink_destroy (sc_hash_t * hash);
00729 
00737 int                 sc_hash_lookup (sc_hash_t * hash, void *v, void ***found);
00738 
00746 int                 sc_hash_insert_unique (sc_hash_t * hash, void *v,
00747                                            void ***found);
00748 
00755 int                 sc_hash_remove (sc_hash_t * hash, void *v, void **found);
00756 
00760 void                sc_hash_foreach (sc_hash_t * hash, sc_hash_foreach_t fn);
00761 
00764 void                sc_hash_print_statistics (int package_id,
00765                                               int log_priority,
00766                                               sc_hash_t * hash);
00767 
00768 typedef struct sc_hash_array_data
00769 {
00770   sc_array_t         *pa;
00771   sc_hash_function_t  hash_fn;
00772   sc_equal_function_t equal_fn;
00773   void               *user_data;
00774   void               *current_item;
00775 }
00776 sc_hash_array_data_t;
00777 
00781 typedef struct sc_hash_array
00782 {
00783   /* implementation variables */
00784   sc_array_t          a;
00785   sc_hash_array_data_t internal_data;
00786   sc_hash_t          *h;
00787 }
00788 sc_hash_array_t;
00789 
00794 size_t              sc_hash_array_memory_used (sc_hash_array_t * ha);
00795 
00801 sc_hash_array_t    *sc_hash_array_new (size_t elem_size,
00802                                        sc_hash_function_t hash_fn,
00803                                        sc_equal_function_t equal_fn,
00804                                        void *user_data);
00805 
00808 void                sc_hash_array_destroy (sc_hash_array_t * hash_array);
00809 
00812 int                 sc_hash_array_is_valid (sc_hash_array_t * hash_array);
00813 
00817 void                sc_hash_array_truncate (sc_hash_array_t * hash_array);
00818 
00827 int                 sc_hash_array_lookup (sc_hash_array_t * hash_array,
00828                                           void *v, size_t * position);
00829 
00841 void               *sc_hash_array_insert_unique (sc_hash_array_t * hash_array,
00842                                                  void *v, size_t * position);
00843 
00850 void                sc_hash_array_rip (sc_hash_array_t * hash_array,
00851                                        sc_array_t * rip);
00852 
00858 typedef struct sc_recycle_array
00859 {
00860   /* interface variables */
00861   size_t              elem_count;       /* number of valid entries */
00862 
00863   /* implementation variables */
00864   sc_array_t          a;
00865   sc_array_t          f;
00866 }
00867 sc_recycle_array_t;
00868 
00873 void                sc_recycle_array_init (sc_recycle_array_t * rec_array,
00874                                            size_t elem_size);
00875 
00881 void                sc_recycle_array_reset (sc_recycle_array_t * rec_array);
00882 
00890 void               *sc_recycle_array_insert (sc_recycle_array_t * rec_array,
00891                                              size_t * position);
00892 
00900 void               *sc_recycle_array_remove (sc_recycle_array_t * rec_array,
00901                                              size_t position);
00902 
00903 SC_EXTERN_C_END;
00904 
00905 #endif /* !SC_CONTAINERS_H */
 All Data Structures Files Functions Variables Typedefs Defines