sc_containers.h

Go to the documentation of this file.

/*
  This file is part of the SC Library.
  The SC Library provides support for parallel scientific applications.
 
  Copyright (C) 2010 The University of Texas System
  Additional copyright (C) 2011 individual authors
 
  The SC Library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
 
  The SC Library 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
  Lesser General Public License for more details.
 
  You should have received a copy of the GNU Lesser General Public
  License along with the SC Library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  02110-1301, USA.
*/
 
#ifndef SC_CONTAINERS_H
#define SC_CONTAINERS_H
 
#include <sc.h>
 
SC_EXTERN_C_BEGIN;
 
/* Hash macros from lookup3.c by Bob Jenkins, May 2006, public domain. */
 
#define sc_hash_rot(x,k) (((x) << (k)) | ((x) >> (32 - (k))))
 
#define sc_hash_mix(a,b,c) ((void)                                      \
                            (a -= c, a ^= sc_hash_rot(c, 4), c += b,    \
                             b -= a, b ^= sc_hash_rot(a, 6), a += c,    \
                             c -= b, c ^= sc_hash_rot(b, 8), b += a,    \
                             a -= c, a ^= sc_hash_rot(c,16), c += b,    \
                             b -= a, b ^= sc_hash_rot(a,19), a += c,    \
                             c -= b, c ^= sc_hash_rot(b, 4), b += a))
 
#define sc_hash_final(a,b,c) ((void)                            \
                              (c ^= b, c -= sc_hash_rot(b,14),  \
                               a ^= c, a -= sc_hash_rot(c,11),  \
                               b ^= a, b -= sc_hash_rot(a,25),  \
                               c ^= b, c -= sc_hash_rot(b,16),  \
                               a ^= c, a -= sc_hash_rot(c, 4),  \
                               b ^= a, b -= sc_hash_rot(a,14),  \
                               c ^= b, c -= sc_hash_rot(b,24)))
 
typedef unsigned int (*sc_hash_function_t) (const void *v, const void *u);
 
typedef int         (*sc_equal_function_t) (const void *v1,
                                            const void *v2, const void *u);
 
typedef int         (*sc_hash_foreach_t) (void **v, const void *u);
 
typedef struct sc_array
{
  /* interface variables */
  size_t              elem_size;        
  size_t              elem_count;       
  /* implementation variables */
  ssize_t             byte_alloc;       
  char               *array;    
}
sc_array_t;
 
#define SC_ARRAY_IS_OWNER(a) ((a)->byte_alloc >= 0)
 
#define SC_ARRAY_BYTE_ALLOC(a) ((size_t) \
         (SC_ARRAY_IS_OWNER (a) ? (a)->byte_alloc : -((a)->byte_alloc + 1)))
 
size_t              sc_array_memory_used (sc_array_t * array, int is_dynamic);
 
sc_array_t         *sc_array_new (size_t elem_size);
 
sc_array_t         *sc_array_new_count (size_t elem_size, size_t elem_count);
 
#define sc_array_new_size(s,c) (sc_array_new_count ((s), (c)))
 
sc_array_t         *sc_array_new_view (sc_array_t * array,
                                       size_t offset, size_t length);
 
sc_array_t         *sc_array_new_data (void *base,
                                       size_t elem_size, size_t elem_count);
 
void                sc_array_destroy (sc_array_t * array);
 
void                sc_array_destroy_null (sc_array_t ** parray);
 
void                sc_array_init (sc_array_t * array, size_t elem_size);
 
void                sc_array_init_size (sc_array_t * array,
                                        size_t elem_size, size_t elem_count);
 
void                sc_array_init_count (sc_array_t * array,
                                         size_t elem_size, size_t elem_count);
 
void                sc_array_init_view (sc_array_t * view, sc_array_t * array,
                                        size_t offset, size_t length);
 
void                sc_array_init_reshape (sc_array_t * view,
                                           sc_array_t * array,
                                           size_t elem_size,
                                           size_t elem_count);
 
void                sc_array_init_data (sc_array_t * view, void *base,
                                        size_t elem_size, size_t elem_count);
 
void                sc_array_memset (sc_array_t * array, int c);
 
void                sc_array_reset (sc_array_t * array);
 
void                sc_array_truncate (sc_array_t * array);
 
void                sc_array_rewind (sc_array_t * array, size_t new_count);
 
void                sc_array_resize (sc_array_t * array, size_t new_count);
 
void                sc_array_copy (sc_array_t * dest, sc_array_t * src);
 
void                sc_array_copy_into (sc_array_t * dest, size_t dest_offset,
                                        sc_array_t * src);
 
void                sc_array_move_part (sc_array_t * dest, size_t dest_offset,
                                        sc_array_t * src, size_t src_offset,
                                        size_t count);
 
void                sc_array_sort (sc_array_t * array,
                                   int (*compar) (const void *,
                                                  const void *));
 
int                 sc_array_is_sorted (sc_array_t * array,
                                        int (*compar) (const void *,
                                                       const void *));
 
int                 sc_array_is_equal (sc_array_t * array,
                                       sc_array_t * other);
 
void                sc_array_uniq (sc_array_t * array,
                                   int (*compar) (const void *,
                                                  const void *));
 
ssize_t             sc_array_bsearch (sc_array_t * array,
                                      const void *key,
                                      int (*compar) (const void *,
                                                     const void *));
 
typedef size_t      (*sc_array_type_t) (sc_array_t * array,
                                        size_t index, void *data);
 
void                sc_array_split (sc_array_t * array, sc_array_t * offsets,
                                    size_t num_types, sc_array_type_t type_fn,
                                    void *data);
 
int                 sc_array_is_permutation (sc_array_t * array);
 
void                sc_array_permute (sc_array_t * array,
                                      sc_array_t * newindices, int keepperm);
 
unsigned int        sc_array_checksum (sc_array_t * array);
 
size_t              sc_array_pqueue_add (sc_array_t * array,
                                         void *temp,
                                         int (*compar) (const void *,
                                                        const void *));
 
size_t              sc_array_pqueue_pop (sc_array_t * array,
                                         void *result,
                                         int (*compar) (const void *,
                                                        const void *));
 
/*@unused@*/
static inline void *
sc_array_index (sc_array_t * array, size_t iz)
{
  SC_ASSERT (iz < array->elem_count);
 
  return (void *) (array->array + array->elem_size * iz);
}
 
/*@unused@*/
static inline void *
sc_array_index_null (sc_array_t * array, size_t iz)
{
  SC_ASSERT (iz <= array->elem_count);
 
  return iz == array->elem_count ? NULL :
    (void *) (array->array + array->elem_size * iz);
}
 
/*@unused@*/
static inline void *
sc_array_index_int (sc_array_t * array, int i)
{
  SC_ASSERT (i >= 0 && (size_t) i < array->elem_count);
 
  return (void *) (array->array + (array->elem_size * (size_t) i));
}
 
/*@unused@*/
static inline void *
sc_array_index_long (sc_array_t * array, long l)
{
  SC_ASSERT (l >= 0 && (size_t) l < array->elem_count);
 
  return (void *) (array->array + (array->elem_size * (size_t) l));
}
 
/*@unused@*/
static inline void *
sc_array_index_ssize_t (sc_array_t * array, ssize_t is)
{
  SC_ASSERT (is >= 0 && (size_t) is < array->elem_count);
 
  return (void *) (array->array + (array->elem_size * (size_t) is));
}
 
/*@unused@*/
static inline void *
sc_array_index_int16 (sc_array_t * array, int16_t i16)
{
  SC_ASSERT (i16 >= 0 && (size_t) i16 < array->elem_count);
 
  return (void *) (array->array + (array->elem_size * (size_t) i16));
}
 
/*@unused@*/
static inline size_t
sc_array_position (sc_array_t * array, void *element)
{
  ptrdiff_t           position;
 
  SC_ASSERT (array->array <= (char *) element);
  SC_ASSERT (((char *) element - array->array) %
             (ptrdiff_t) array->elem_size == 0);
 
  position = ((char *) element - array->array) / (ptrdiff_t) array->elem_size;
  SC_ASSERT (0 <= position && position < (ptrdiff_t) array->elem_count);
 
  return (size_t) position;
}
 
/*@unused@*/
static inline void *
sc_array_pop (sc_array_t * array)
{
  SC_ASSERT (SC_ARRAY_IS_OWNER (array));
  SC_ASSERT (array->elem_count > 0);
 
  return (void *) (array->array + (array->elem_size * --array->elem_count));
}
 
/*@unused@*/
static inline void *
sc_array_push_count (sc_array_t * array, size_t add_count)
{
  const size_t        old_count = array->elem_count;
  const size_t        new_count = old_count + add_count;
 
  SC_ASSERT (SC_ARRAY_IS_OWNER (array));
 
  if (array->elem_size * new_count > (size_t) array->byte_alloc) {
    sc_array_resize (array, new_count);
  }
  else {
    array->elem_count = new_count;
  }
 
  return (void *) (array->array + array->elem_size * old_count);
}
 
/*@unused@*/
static inline void *
sc_array_push (sc_array_t * array)
{
  return sc_array_push_count (array, 1);
}
 
typedef struct sc_mstamp
{
  size_t              elem_size;   
  size_t              per_stamp;   
  size_t              stamp_size;  
  size_t              cur_snext;   
  char               *current;     
  sc_array_t          remember;    
}
sc_mstamp_t;
 
void                sc_mstamp_init (sc_mstamp_t * mst,
                                    size_t stamp_unit, size_t elem_size);
 
void                sc_mstamp_reset (sc_mstamp_t * mst);
 
void                sc_mstamp_truncate (sc_mstamp_t * mst);
 
void               *sc_mstamp_alloc (sc_mstamp_t * mst);
 
size_t              sc_mstamp_memory_used (sc_mstamp_t * mst);
 
typedef struct sc_mempool
{
  /* interface variables */
  size_t              elem_size;        
  size_t              elem_count;       
  int                 zero_and_persist; 
  /* implementation variables */
  sc_mstamp_t         mstamp;   
  sc_array_t          freed;    
}
sc_mempool_t;
 
size_t              sc_mempool_memory_used (sc_mempool_t * mempool);
 
sc_mempool_t       *sc_mempool_new (size_t elem_size);
 
sc_mempool_t       *sc_mempool_new_zero_and_persist (size_t elem_size);
 
void                sc_mempool_init (sc_mempool_t * mempool,
                                     size_t elem_size);
 
void                sc_mempool_destroy (sc_mempool_t * mempool);
 
void                sc_mempool_destroy_null (sc_mempool_t ** pmempool);
 
void                sc_mempool_reset (sc_mempool_t * mempool);
 
void                sc_mempool_truncate (sc_mempool_t * mempool);
 
/*@unused@*/
static inline void *
sc_mempool_alloc (sc_mempool_t * mempool)
{
  void               *ret;
  sc_array_t         *freed = &mempool->freed;
 
  ++mempool->elem_count;
 
  if (freed->elem_count > 0) {
    ret = *(void **) sc_array_pop (freed);
  }
  else {
    ret = sc_mstamp_alloc (&mempool->mstamp);
    if (mempool->zero_and_persist) {
      memset (ret, 0, mempool->elem_size);
    }
  }
 
#ifdef SC_ENABLE_DEBUG
  if (!mempool->zero_and_persist) {
    memset (ret, -1, mempool->elem_size);
  }
#endif
 
  return ret;
}
 
/*@unused@*/
static inline void
sc_mempool_free (sc_mempool_t * mempool, void *elem)
{
  sc_array_t         *freed = &mempool->freed;
 
  SC_ASSERT (mempool->elem_count > 0);
 
#ifdef SC_ENABLE_DEBUG
  if (!mempool->zero_and_persist) {
    memset (elem, -1, mempool->elem_size);
  }
#endif
 
  --mempool->elem_count;
 
  *(void **) sc_array_push (freed) = elem;
}
 
typedef struct sc_link
{
  void               *data;     
  struct sc_link     *next;     
}
sc_link_t;
 
typedef struct sc_list
{
  /* interface variables */
  size_t              elem_count;       
  sc_link_t          *first;            
  sc_link_t          *last;             
  /* implementation variables */
  int                 allocator_owned;  
  sc_mempool_t       *allocator;        
}
sc_list_t;
 
size_t              sc_list_memory_used (sc_list_t * list, int is_dynamic);
 
sc_list_t          *sc_list_new (sc_mempool_t * allocator);
 
void                sc_list_destroy (sc_list_t * list);
 
void                sc_list_init (sc_list_t * list, sc_mempool_t * allocator);
 
void                sc_list_reset (sc_list_t * list);
 
void                sc_list_unlink (sc_list_t * list);
 
sc_link_t          *sc_list_prepend (sc_list_t * list, void *data);
 
sc_link_t          *sc_list_append (sc_list_t * list, void *data);
 
sc_link_t          *sc_list_insert (sc_list_t * list,
                                    sc_link_t * pred, void *data);
 
void               *sc_list_remove (sc_list_t * list, sc_link_t * pred);
 
void               *sc_list_pop (sc_list_t * list);
 
typedef struct sc_hash
{
  /* interface variables */
  size_t              elem_count;       
  void               *user_data;        
  /* implementation variables */
  sc_array_t         *slots;    
  sc_hash_function_t  hash_fn;  
  sc_equal_function_t equal_fn; 
  size_t              resize_checks;    
  size_t              resize_actions;   
  int                 allocator_owned;  
  sc_mempool_t       *allocator;        
}
sc_hash_t;
 
unsigned int        sc_hash_function_string (const void *s, const void *u);
 
size_t              sc_hash_memory_used (sc_hash_t * hash);
 
sc_hash_t          *sc_hash_new (sc_hash_function_t hash_fn,
                                 sc_equal_function_t equal_fn,
                                 void *user_data, sc_mempool_t * allocator);
 
void                sc_hash_destroy (sc_hash_t * hash);
 
void                sc_hash_destroy_null (sc_hash_t ** phash);
 
void                sc_hash_truncate (sc_hash_t * hash);
 
void                sc_hash_unlink (sc_hash_t * hash);
 
void                sc_hash_unlink_destroy (sc_hash_t * hash);
 
int                 sc_hash_lookup (sc_hash_t * hash, void *v, void ***found);
 
int                 sc_hash_insert_unique (sc_hash_t * hash, void *v,
                                           void ***found);
 
int                 sc_hash_remove (sc_hash_t * hash, void *v, void **found);
 
void                sc_hash_foreach (sc_hash_t * hash, sc_hash_foreach_t fn);
 
void                sc_hash_print_statistics (int package_id,
                                              int log_priority,
                                              sc_hash_t * hash);
 
typedef struct sc_hash_array_data sc_hash_array_data_t;
 
typedef struct sc_hash_array
{
  /* interface variables */
  void               *user_data;        
  /* implementation variables */
  sc_array_t          a;        
  sc_hash_t          *h;        
  sc_hash_array_data_t *internal_data;  
}
sc_hash_array_t;
 
size_t              sc_hash_array_memory_used (sc_hash_array_t * ha);
 
sc_hash_array_t    *sc_hash_array_new (size_t elem_size,
                                       sc_hash_function_t hash_fn,
                                       sc_equal_function_t equal_fn,
                                       void *user_data);
 
void                sc_hash_array_destroy (sc_hash_array_t * hash_array);
 
int                 sc_hash_array_is_valid (sc_hash_array_t * hash_array);
 
void                sc_hash_array_truncate (sc_hash_array_t * hash_array);
 
int                 sc_hash_array_lookup (sc_hash_array_t * hash_array,
                                          void *v, size_t *position);
 
void               *sc_hash_array_insert_unique (sc_hash_array_t * hash_array,
                                                 void *v, size_t *position);
 
void                sc_hash_array_foreach (sc_hash_array_t * hash_array,
                                           sc_hash_foreach_t fn);
 
void                sc_hash_array_rip (sc_hash_array_t * hash_array,
                                       sc_array_t * rip);
 
typedef struct sc_recycle_array
{
  /* interface variables */
  size_t              elem_count;       
  /* implementation variables */
  sc_array_t          a;                
  sc_array_t          f;                
}
sc_recycle_array_t;
 
void                sc_recycle_array_init (sc_recycle_array_t * rec_array,
                                           size_t elem_size);
 
void                sc_recycle_array_reset (sc_recycle_array_t * rec_array);
 
void               *sc_recycle_array_insert (sc_recycle_array_t * rec_array,
                                             size_t *position);
 
void               *sc_recycle_array_remove (sc_recycle_array_t * rec_array,
                                             size_t position);
 
SC_EXTERN_C_END;
 
#endif /* !SC_CONTAINERS_H */