tt*******@yahoo.com writes:
This post is about how to get generic modules in a C environment. The
aim is to get close to Ada generics. Using C++ is not an option. It
should all run in a simple C compiler.
When I think of a generic module, it is something that can be used
exactly as it is. The generic H-file and/or C-file, should not have to
be edited AT ALL in order to use it. If it has to be changed in just 1
line, it could possibly still have great reusability properties, but it
is not generic in the sense I mean.
I recently created a simple module for circular deques that might
fit your criteria. Here's the header file (there's no .c file).
I don't know whether it generalizes naturally to more complicated
data structures, because I've only tried it with this one so
far. It depends on a few project-specific functions, but I'm
sure you can fill in the blanks:
/* PSPP - computes sample statistics.
Copyright (C) 2007 Free Software Foundation, Inc.
This program 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 of the
License, or (at your option) any later version.
This program 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 this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA. */
#ifndef LIBPSPP_DEQUE_H
#define LIBPSPP_DEQUE_H 1
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <libpspp/compiler.h>
#include "xalloc.h"
/* Declares data and functions for a deque whose elements have
the given ELEMENT_TYPE. Instances of the deque are declared
as "struct NAME", and each function that operates on the deque
has NAME_ as a prefix. */
#define DEQUE_DECLARE(NAME, ELEMENT_TYPE) \
/* An instance of the deque. */ \
struct NAME \
{ \
size_t capacity; /* Capacity, which must be a power of 2. */ \
size_t front; /* One past the front of the queue. */ \
size_t back; /* The back of the queue. */ \
ELEMENT_TYPE *data; /* Pointer to CAPACITY elements. */ \
}; \
\
/* Initializes DEQUE as an empty deque that can store at least \
CAPACITY elements. (The actual capacity may be larger and is \
always a power of 2.) */ \
static inline void \
NAME##_init (struct NAME *deque, size_t capacity) \
{ \
deque->capacity = 1; \
while (deque->capacity < capacity) \
deque->capacity *= 2; \
deque->front = deque->back = 0; \
deque->data = xnmalloc (deque->capacity, sizeof *deque->data); \
} \
\
/* Destroys DEQUE, which must be empty. */ \
static inline void \
NAME##_destroy (struct NAME *deque) \
{ \
free (deque->data); \
} \
\
/* Returns the number of elements currently in DEQUE. */ \
static inline size_t \
NAME##_count (const struct NAME *deque) \
{ \
return deque->front - deque->back; \
} \
\
/* Returns the maximum number of elements that DEQUE can hold at \
any time. */ \
static inline size_t \
NAME##_capacity (const struct NAME *deque) \
{ \
return deque->capacity; \
} \
\
/* Returns true if DEQUE is currently empty (contains no \
elements), false otherwise. */ \
static inline bool \
NAME##_is_empty (const struct NAME *deque) \
{ \
return NAME##_count (deque) == 0; \
} \
\
/* Returns true if DEQUE is currently full (cannot take any more \
elements), false otherwise. */ \
static inline bool \
NAME##_is_full (const struct NAME *deque) \
{ \
return NAME##_count (deque) >= NAME##_capacity (deque); \
} \
\
/* Returns the element in DEQUE that is OFFSET elements from its \
front. A value 0 for OFFSET requests the element at the \
front, a value of 1 the element just behind the front, and so \
on. OFFSET must be less than the current number of elements \
in DEQUE. */ \
static inline ELEMENT_TYPE * \
NAME##_front (const struct NAME *deque, size_t offset) \
{ \
assert (NAME##_count (deque) offset); \
return &deque->data[(deque->front - offset - 1) & (deque->capacity - 1)]; \
} \
\
/* Returns the element in DEQUE that is OFFSET elements from its \
back. A value 0 for OFFSET requests the element at the back, \
a value of 1 the element just ahead of the back, and so on. \
OFFSET must be less than the current number of elements in \
DEQUE. */ \
static inline ELEMENT_TYPE * \
NAME##_back (const struct NAME *deque, size_t offset) \
{ \
assert (NAME##_count (deque) offset); \
return &deque->data[(deque->back + offset) & (deque->capacity - 1)]; \
} \
\
/* Adds and returns the address of a new element at the front of \
DEQUE, which must not be full. The caller is responsible for \
assigning a value to the returned element. */ \
static inline ELEMENT_TYPE * \
NAME##_push_front (struct NAME *deque) \
{ \
assert (!NAME##_is_full (deque)); \
return &deque->data[deque->front++ & (deque->capacity - 1)]; \
} \
\
/* Adds and returns the address of a new element at the back of \
DEQUE, which must not be full. The caller is responsible for \
assigning a value to the returned element. */ \
static inline ELEMENT_TYPE * \
NAME##_push_back (struct NAME *deque) \
{ \
assert (!NAME##_is_full (deque)); \
return &deque->data[--deque->back & (deque->capacity - 1)]; \
} \
\
/* Pops the front element off DEQUE (which must not be empty) and \
returns its address. The element may be reused the next time \
an element is pushed into DEQUE or when DEQUE is expanded. */ \
static inline ELEMENT_TYPE * \
NAME##_pop_front (struct NAME *deque) \
{ \
assert (!NAME##_is_empty (deque)); \
return &deque->data[--deque->front & (deque->capacity - 1)]; \
} \
\
/* Pops the back element off DEQUE (which must not be empty) and \
returns its address. The element may be reused the next time \
an element is pushed into DEQUE or when DEQUE is expanded. */ \
static inline ELEMENT_TYPE * \
NAME##_pop_back (struct NAME *deque) \
{ \
assert (!NAME##_is_empty (deque)); \
return &deque->data[deque->back++ & (deque->capacity - 1)]; \
} \
\
/* Expands DEQUE, doubling its capacity. */ \
static inline void \
NAME##_expand (struct NAME *deque) \
{ \
struct NAME old_deque = *deque; \
NAME##_init (deque, deque->capacity * 2); \
while (!NAME##_is_empty (&old_deque)) \
*NAME##_push_front (deque) = *NAME##_pop_back (&old_deque); \
free (old_deque.data); \
}
#endif /* libpspp/deque.h */
--
"We put [the best] Assembler programmers in a little glass case in the hallway
near the Exit sign. The sign on the case says, `In case of optimization
problem, break glass.' Meanwhile, the problem solvers are busy doing their
work in languages most appropriate to the job at hand." --Richard Riehle
