libsc
1.6.0
|
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 */