Revision: 1881
http://undernet-ircu.svn.sourceforge.net/undernet-ircu/?rev=1881&view=rev
Author: klmitch
Date: 2008-09-26 04:15:18 +0000 (Fri, 26 Sep 2008)
Log Message:
-----------
Author: Kev <[EMAIL PROTECTED]>
Description:
First, fix a minor bug in ancillary.h. Second, define the concept of
"keys" and "keyspaces" utilizing a small, efficient algorithm for
finding an available integer array index where availability is stored
by a dynamically allocated bitmap. Finally, update mode.h to use a
keyspace in struct ModeList (and update its style to match the rest
of ircu).
Modified Paths:
--------------
ircu2/branches/mode/ChangeLog
ircu2/branches/mode/include/ancillary.h
ircu2/branches/mode/include/mode.h
Added Paths:
-----------
ircu2/branches/mode/include/keyspace.h
ircu2/branches/mode/ircd/keyspace.c
Modified: ircu2/branches/mode/ChangeLog
===================================================================
--- ircu2/branches/mode/ChangeLog 2008-09-22 16:46:42 UTC (rev 1880)
+++ ircu2/branches/mode/ChangeLog 2008-09-26 04:15:18 UTC (rev 1881)
@@ -1,3 +1,18 @@
+2008-09-26 Kevin L. Mitchell <[EMAIL PROTECTED]>
+
+ * include/ancillary.h: correct a minor typo in ancdata_init();
+ this eventually needs to be updated to utilize the new keyspace
+ routines
+
+ * include/mode.h: add keyspaces to ModeList; update style from
+ mine to ircu's
+
+ * include/keyspace.h: types, structures, etc. for allocating and
+ deallocating "keys" from "keyspaces"
+
+ * ircd/keyspace.c: generic routines to allocate and deallocate
+ "keys" from a "keyspace"
+
2008-09-22 Kevin L. Mitchell <[EMAIL PROTECTED]>
* include/mode.h: begin sketching out structures for new, unified
Modified: ircu2/branches/mode/include/ancillary.h
===================================================================
--- ircu2/branches/mode/include/ancillary.h 2008-09-22 16:46:42 UTC (rev
1880)
+++ ircu2/branches/mode/include/ancillary.h 2008-09-26 04:15:18 UTC (rev
1881)
@@ -117,12 +117,12 @@
{ (module), 0, 0 }
/** Dynamically initialize an ancdata_t.
- * @param[in,out] ad The ancdata_t to be initialized.
+ * @param[in,out] ad A pointer to the ancdata_t to be initialized.
* @param[in] module The module the object is in.
*/
#define ancdata_init(ad, module) \
do { \
- ancdata_t _ad = (ad); \
+ ancdata_t *_ad = (ad); \
_ad->ad_module = (module); \
_ad->ad_alloc = 0; \
_ad->ad_data = 0; \
Added: ircu2/branches/mode/include/keyspace.h
===================================================================
--- ircu2/branches/mode/include/keyspace.h (rev 0)
+++ ircu2/branches/mode/include/keyspace.h 2008-09-26 04:15:18 UTC (rev
1881)
@@ -0,0 +1,126 @@
+/*
+ * IRC - Internet Relay Chat, include/keyspace.h
+ * Copyright (C) 2008 Kevin L. Mitchell
+ *
+ * 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, 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+/** @file
+ * @brief Structures and functions for allocating integer keys.
+ * @version $Id$
+ */
+#ifndef INCLUDED_keyspace_h
+#define INCLUDED_keyspace_h
+#ifndef INCLUDED_flagset_h
+#include "flagset.h" /* flagpage_t */
+#endif
+#ifndef INCLUDED_limits_h
+#include <limits.h> /* UINT_MAX */
+#define INCLUDED_limits_h
+#endif
+
+/** Invalid key_t value for returning errors from ks_reserve(). */
+#define KEY_INVKEY UINT_MAX
+
+/** Specifies a key value. */
+typedef unsigned int key_t;
+/** Specifies a space of keys to allocate from. */
+typedef struct KeySpace keyspace_t;
+
+/** Optional growth callback for a key space.
+ * @param[in] space Key space being grown.
+ * @param[in] new New size for key space allocation.
+ */
+typedef void (*keygrow_t)(keyspace_t* space, key_t new);
+
+/** Contains details of the key space. */
+struct KeySpace {
+ unsigned long ks_magic; /**< Magic number */
+ unsigned int ks_alloc; /**< Total number of bitmap entries */
+ key_t ks_count; /**< Current count of keys */
+ key_t ks_highest; /**< Highest allocated key to date */
+ key_t ks_max; /**< Maximum number of keys to allocate
*/
+ key_t ks_extern; /**< External key tracker size */
+ key_t ks_chunk; /**< Chunk to round key tracker size to
*/
+ keygrow_t ks_grow; /**< External routine to signal on growth */
+ flagpage_t* ks_keys; /**< Key allocation bitmap */
+ void* ks_extra; /**< Extra data associated with
keyspace */
+};
+
+/** Magic number for keyspace_t. */
+#define KEYSPACE_MAGIC 0x44368132
+
+/** Initialize a keyspace_t.
+ * @param[in] max Maximum number of keys that can be reserved.
+ * @param[in] chunk Chunk size for calling external routine.
+ * @param[in] grow External routine to call when grown.
+ * @param[in] extra Extra data to be associated with the keyspace.
+ */
+#define KEYSPACE_INIT(max, chunk, grow, extra) \
+ { KEYSPACE_MAGIC, 0, 0, 0, (max), 0, (chunk), (grow), 0, (extra) }
+
+/** Check the keyspace_t magic number. */
+#define KEYSPACE_CHECK(space) ((space) && \
+ (space)->ks_magic == KEYSPACE_MAGIC)
+
+/** Get the number of entries allocated in the keys table. */
+#define ks_alloc(space) ((space)->ks_alloc)
+/** Get the count of the keys currently allocated. */
+#define ks_count(space) ((space)->ks_count)
+/** Get the value of the highest key that's been allocated. */
+#define ks_highest(space) ((space)->ks_highest)
+/** Get the maximum number of keys that can be allocated. */
+#define ks_max(space) ((space)->ks_max)
+/** Get the current size of the external array. */
+#define ks_extern(space) ((space)->ks_extern)
+/** Get the chunk size for allocation of the external array. */
+#define ks_chunk(space) ((space)->ks_chunk)
+/** Get the external array growth function callabck. */
+#define ks_grow(space) ((space)->ks_grow)
+/** Get the \a i entry in the keys table. */
+#define ks_keys(space, i) ((space)->ks_keys[(i)])
+/** Get extra data associated with the keyspace. */
+#define ks_extra(space) ((space)->ks_extra)
+
+/** Dynamically initialize a keyspace_t.
+ * @param[in,out] space A pointer to the keyspace_t to be initialized.
+ * @param[in] max Maximum number of keys that can be reserved.
+ * @param[in] chunk Chunk size for calling external routine.
+ * @param[in] grow External routine to call when grown.
+ */
+#define ks_init(space, max, chunk, grow, extra) \
+ do { \
+ keyspace_t* _ks = (space); \
+ _ks->ks_magic = KEYSPACE_MAGIC; \
+ _ks->ks_alloc = 0; \
+ _ks->ks_count = 0; \
+ _ks->ks_highest = 0; \
+ _ks->ks_max = (max); \
+ _ks->ks_extern = 0; \
+ _ks->ks_chunk = (chunk); \
+ _ks->ks_grow = (grow); \
+ _ks->ks_keys = 0; \
+ _ks->ks_extra = (extra); \
+ } while (0)
+
+/* Reserve a key, optionally a specified one. */
+extern key_t ks_reserve(keyspace_t* space);
+
+/* Release an allocated key. */
+extern void ks_release(keyspace_t* space, key_t key);
+
+/* Clean up a keyspace. */
+extern void ks_clean(keyspace_t* space);
+
+#endif /* INCLUDED_keyspace_h */
Property changes on: ircu2/branches/mode/include/keyspace.h
___________________________________________________________________
Added: svn:keywords
+ Id
Modified: ircu2/branches/mode/include/mode.h
===================================================================
--- ircu2/branches/mode/include/mode.h 2008-09-22 16:46:42 UTC (rev 1880)
+++ ircu2/branches/mode/include/mode.h 2008-09-26 04:15:18 UTC (rev 1881)
@@ -28,6 +28,9 @@
#ifndef INCLUDED_flagset_h
#include "flagset.h"
#endif
+#ifndef INCLUDED_keyspace_h
+#include "keyspace.h"
+#endif
struct Client;
struct Channel;
@@ -38,7 +41,7 @@
#define MAX_MODEPARAMS 6
/** Specifies the numerical value of a mode switch. */
-typedef unsigned int mode_t;
+typedef key_t mode_t;
/** Describes a single mode, including parsing flags and policy flags. */
typedef struct ModeDesc mode_desc_t;
@@ -56,7 +59,7 @@
regent_t md_regent; /**< Registration entry. */
int md_switch; /**< Mode switch (character). */
mode_t md_mode; /**< Numerical value of mode. */
- const char *md_desc; /**< Textual description of mode. */
+ const char* md_desc; /**< Textual description of mode. */
flagpage_t md_flags; /**< Flags affecting mode. */
};
@@ -120,8 +123,10 @@
regtab_t ml_table; /**< Registration table. */
size_t ml_offset; /**< Offset of mode structure
within entity. */
- mode_desc_t *ml_smap[256]; /**< Mode switch map. */
- mode_desc_t *ml_mmap[MAX_MODES];
+ keyspace_t* ml_keyspace; /**< Keyspace for mode value
+ allocation. */
+ mode_desc_t* ml_smap[256]; /**< Mode switch map. */
+ mode_desc_t* ml_mmap[MAX_MODES];
/**< Mode value map. */
};
@@ -139,17 +144,17 @@
/** Contains a set of modes with arguments. */
struct ModeArgs {
- mode_args_t *ma_next; /**< Chain to next set of modes with
+ mode_args_t* ma_next; /**< Chain to next set of modes with
arguments. */
- mode_args_t *ma_prev; /**< Chain to previous set of modes
+ mode_args_t* ma_prev; /**< Chain to previous set of modes
with arguments. */
struct {
- mode_desc_t *mam_mode; /**< The mode. */
+ mode_desc_t* mam_mode; /**< The mode. */
mode_dir_t mam_dir; /**< Direction of mode. */
union {
unsigned int mama_int; /**< Unsigned integer argument. */
- const char *mama_str; /**< String argument (keys). */
- struct Client *mama_cli; /**< Client argument (chanops). */
+ const char* mama_str; /**< String argument (keys). */
+ struct Client* mama_cli; /**< Client argument (chanops). */
} mam_arg; /**< Argument for mode. */
unsigned short mam_oplevel; /**< Oplevel for a bounce. */
} ma_modeargs[MAX_MODEPARAMS];
@@ -158,14 +163,14 @@
/** Describes the difference between two mode_set_t's. */
struct ModeDelta {
- struct Client *md_origin; /**< Origin of delta. */
+ struct Client* md_origin; /**< Origin of delta. */
int md_etype; /**< Type of entity--1 for channel,
0 for client. */
union {
- struct Client *mde_client; /**< Client mode delta applies to. */
- struct Channel *mde_chan; /**< Channel mode delta applies to. */
+ struct Client* mde_client; /**< Client mode delta applies to. */
+ struct Channel* mde_chan; /**< Channel mode delta applies to. */
} md_entity; /**< Entity mode delta applies to. */
- mode_list_t *md_modes; /**< Mode list used by this delta. */
+ mode_list_t* md_modes; /**< Mode list used by this delta. */
mode_set_t md_add; /**< Simple modes to be added. */
mode_set_t md_rem; /**< Simple modes to be removed. */
@@ -173,7 +178,7 @@
flagpage_t md_flags; /**< Flags affecting the delta. */
int md_count; /**< Number of modes with args. */
- mode_args_t *md_tail; /**< Tail of modes-with-args list. */
+ mode_args_t* md_tail; /**< Tail of modes-with-args list. */
mode_args_t md_head; /**< First element of modes-with-args
list. */
};
Added: ircu2/branches/mode/ircd/keyspace.c
===================================================================
--- ircu2/branches/mode/ircd/keyspace.c (rev 0)
+++ ircu2/branches/mode/ircd/keyspace.c 2008-09-26 04:15:18 UTC (rev 1881)
@@ -0,0 +1,241 @@
+/*
+ * IRC - Internet Relay Chat, ircd/keyspace.c
+ * Copyright (C) 2008 Kevin L. Mitchell
+ *
+ * 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, 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+/** @file
+ * @brief Implementation of allocation of integer keys.
+ * @version $Id$
+ */
+#include "config.h"
+
+#include "keyspace.h"
+#include "flagset.h"
+#include "ircd_alloc.h"
+#include "ircd_log.h"
+
+/** @page keyspace Generic keyspace subsystem.
+ *
+ * @section introkey Introduction
+ *
+ * Many subsystems need to allocate small integers, called \em keys.
+ * These keys are typically used as indexes into an array. This
+ * subsystem is a simple but efficient generic key allocation
+ * subsystem. It is modeled on the pthread_key_create() and
+ * pthread_key_delete() routines, which manage keys for use by the
+ * POSIX functions pthread_getspecific() and pthread_setspecific().
+ * The primary difference between these POSIX interfaces and this
+ * subsystem is that, for the POSIX routines, the key type is opaque,
+ * whereas this subsystem provides simple integers.
+ *
+ * @section keyman Managing Keys
+ *
+ * Keys are represented by the type key_t, and they are allocated from
+ * \a keyspaces, which are specified by a keyspace_t object. This
+ * keyspace_t object must be initialized either with KEYSPACE_INIT()
+ * or ks_init()--the latter allowing for dynamic initialization. Once
+ * keys are allocated, the keyspace_t object will contain some
+ * allocated memory, which may be reclaimed by calling the ks_clean()
+ * routine on the keyspace. Note that the keyspace must be
+ * reinitialized by a call to ks_init() before it can be used again.
+ *
+ * Allocation of a key is simple--simply call the ks_reserve()
+ * function, passing it a pointer to the keyspace. If no more keys
+ * can be allocated--there is a provision for setting the maximum
+ * permissible key--ks_reserve() will return KEY_INVKEY. Otherwise,
+ * it returns a newly allocated key. Allocation is done in a
+ * tight-packed manner, so ks_reserve() may return keys that have been
+ * released. Once you're done with a key, simply call ks_release() to
+ * return it to the system.
+ *
+ * @section advkey Advanced Key Management
+ *
+ * Most subsystems need to maintain an array in conjunction with the
+ * keyspace. This array may contain things such as a pointer to a
+ * function to release whatever object the key is referring to.
+ * Additionally, some subsystems need to impose an upper limit on the
+ * keyspace. Both of these are quite simple to accomplish.
+ *
+ * It is also possible, by specifying a non-zero \a extra argument to
+ * KEYSPACE_INIT() or ks_init(), to associate arbitrary data--such as
+ * a pointer to the externally maintained array--with a keyspace.
+ *
+ * @subsection maxkey Maximum Keys
+ *
+ * Both KEYSPACE_INIT() and ks_init() take an argument called \a max,
+ * which specifies the maximum number of keys that the subsystem can
+ * accommodate. Once that number of keys has been allocated,
+ * ks_reserve() will return KEY_INVKEY until a key has been released
+ * by a call to ks_release(). If an upper limit is unnecessary or
+ * undesired, simply pass 0 for \a max.
+ *
+ * @subsection externkey External Keys
+ *
+ * Managing an external array is also fairly simple to accomplish.
+ * The keyspace subsystem will call a user-defined function whenever a
+ * new key allocation requires that the external array (or whatever
+ * the user is maintaining) needs to be resized. This is accomplished
+ * by specifying the \a chunk and \a grow arguments to KEYSPACE_INIT()
+ * or ks_init(). Both of these arguments must be nonzero in order to
+ * enable this advanced feature.
+ *
+ * The \a grow argument simply specifies a routine that will be called
+ * with a pointer to the keyspace and the new size of the external
+ * array. This new size will be a multiple of the \a chunk size
+ * specified when the keyspace was initialized.
+ *
+ * @section infokey Important Subsystem Information
+ *
+ * This subsystem provides one structure--struct KeySpace--and 2
+ * types: key_t, for the value of keys; and keyspace_t, corresponding
+ * to the struct KeySpace. In particular, keyspace_t should be
+ * treated as opaque by all callers, only referenced through the
+ * provided macros, whereas key_t can be treated as an integral type
+ * suitable for use as an array index.
+ *
+ * This subsystem is intentionally designed to pull in as few other
+ * ircu subsystems as possible, in order to minimize issues with
+ * modularity. It is almost completely self-contained in the
+ * keyspace.h and keyspace.c, referencing the assert() macro in
+ * ircd_log.h and making use of the flagpage_t type and some
+ * associated macros from flagset.h. The subsystem itself needs no
+ * initialization, as all data is completely contained in the
+ * keyspace_t types, which are caller-allocated and initialized.
+ *
+ * This subsystem allocates a small amount of memory for tracking
+ * which keys have been allocated and which ones are available. This
+ * memory is directly associated with the keyspaces that have been
+ * utilized, and may be reclaimed by calling ks_clean() on those
+ * keyspaces.
+ */
+
+/** Allocate a key from a keyspace.
+ * @param[in,out] space The keyspace from which to allocate the key.
+ * @return The reserved key, or #KEY_INVKEY if one could not be allocated.
+ */
+key_t
+ks_reserve(keyspace_t* space)
+{
+ key_t key = KEY_INVKEY;
+
+ assert(KEYSPACE_CHECK(space));
+
+ /* Can we even allocate a key? */
+ if (space->ks_count >= (space->ks_max ? space->ks_max : KEY_INVKEY))
+ return KEY_INVKEY;
+
+ /* Do we need to allocate some more keyspace? */
+ if (space->ks_count == (space->ks_alloc * FLAGSET_NBITS)) {
+ /* resize the key space */
+ space->ks_keys = MyRealloc(space->ks_keys, sizeof(flagpage_t) *
+ (space->ks_alloc + 1));
+
+ /* initialize the new element */
+ space->ks_keys[space->ks_alloc++] = 0;
+
+ /* select a key */
+ key = space->ks_count;
+ } else { /* find an empty slot in the bitmap */
+ flagpage_t alloc, mask = ~0;
+ int i = 0, b = FLAGSET_NBITS >> 1;
+
+ /* search for a page with some unallocated bits */
+ for (; i < space->ks_alloc; i++)
+ if (~space->ks_keys[i]) /* if all bits set, == 0 and we go on */
+ break;
+
+ /* Now, find an unallocated key. This algorithm searches the bit
+ * page specified by i for the first zero bit. (It actually
+ * complements the key page in order to search for the first _set_
+ * bit, which is a slightly easier task.) alloc is the
+ * complemented allocation bitmask, mask is the current testing
+ * mask, b is the number of bits by which to shift the mask, and
+ * key is the resultant index of the first clear bit. The
+ * algorithm works by performing a binary search on the allocation
+ * bitmask: If there are no free bits on the right half, the
+ * allocation bitmask is shifted by the appropriate number of
+ * bits, and then the mask is reduced to half the bits it had
+ * previously. Note that the mask starts off with all bits set,
+ * so the first bitmask update reduces it to half of all bits
+ * set...
+ */
+ for (alloc = ~space->ks_keys[i], key = 0; b; b >>= 1) {
+ mask >>= b; /* update the bitmask... */
+ if (!(alloc & mask)) { /* any clear bits on the right? */
+ alloc >>= b; /* nope, shift over some... */
+ key += b; /* and update the bit count */
+ }
+ }
+
+ /* now correct the key to account for the index i */
+ key += i * FLAGSET_NBITS;
+ }
+
+ /* We have a key, let's mark it set and update some statistics */
+ space->ks_count++;
+ space->ks_keys[FLAGSET_INDEX(key)] |= FLAGSET_MASK(key);
+ if (key > space->ks_highest) {
+ space->ks_highest = key; /* keep track of highest key */
+
+ /* inform the external support of a need to resize */
+ if (space->ks_chunk && space->ks_grow &&
+ space->ks_highest > space->ks_extern)
+ (space->ks_grow)(space, space->ks_extern += space->ks_chunk);
+ }
+
+ /* Return the key */
+ return key;
+}
+
+/** Release a key allocated from a keyspace.
+ * @param[in,out] space The keyspace from which the key was allocated.
+ * @param[in] key The key to release.
+ */
+void
+ks_release(keyspace_t* space, key_t key)
+{
+ assert(KEYSPACE_CHECK(space));
+
+ /* if the key was allocated, mark it free and decrement count */
+ if (space->ks_keys[FLAGSET_INDEX(key)] & FLAGSET_MASK(key)) {
+ space->ks_keys[FLAGSET_INDEX(key)] &= ~FLAGSET_MASK(key);
+ space->ks_count--;
+ }
+}
+
+/** Clean up a keyspace.
+ * @param[in,out] space The key space to clean up.
+ */
+void
+ks_clean(keyspace_t* space)
+{
+ assert(KEYSPACE_CHECK(space));
+
+ /* we're just going to release all keys, so just free the key pages */
+ if (space->ks_keys)
+ MyFree(space->ks_keys);
+
+ /* zero everything */
+ space->ks_magic = 0;
+ space->ks_alloc = 0;
+ space->ks_count = 0;
+ space->ks_highest = 0;
+ space->ks_max = 0;
+ space->ks_extern = 0;
+ space->ks_chunk = 0;
+ space->ks_grow = 0;
+ space->ks_keys = 0;
+}
Property changes on: ircu2/branches/mode/ircd/keyspace.c
___________________________________________________________________
Added: svn:keywords
+ Id
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
Patches mailing list
[email protected]
http://undernet.sbg.org/mailman/listinfo/patches
