gbsearcharray.h from EmStar at Krugle
Show gbsearcharray.h syntax highlighted
/*
*
* Copyright (c) 2003 The Regents of the University of California. All
* rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Neither the name of the University nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
/* GObject - GLib Type, Object, Parameter and Signal Library
* Copyright (C) 2000-2001 Tim Janik
*
* This 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 of the License, or (at your option) any later version.
*
* This 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 this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place, Suite 330,
* Boston, MA 02111-1307, USA.
*
* gbsearcharray.h: binary searchable sorted array maintenance
*/
#ifndef __G_BSEARCH_ARRAY_H__
#define __G_BSEARCH_ARRAY_H__
#include <glib/gtypes.h>
#include <glib/gutils.h>
#include <glib/gmem.h>
#include <glib/gmessages.h>
G_BEGIN_DECLS
/* helper macro to avoid signed overflow for value comparisions */
#define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) < (v2) ? -1 : (v1) > (v2))
/* --- typedefs --- */
typedef union _GBSearchArray GBSearchArray;
typedef struct _GBSearchConfig GBSearchConfig;
typedef gint (*GBSearchCompareFunc) (gconstpointer bsearch_node1,
gconstpointer bsearch_node2);
typedef enum
{
G_BSEARCH_ARRAY_ALIGN_POWER2 = 1 << 0,
G_BSEARCH_ARRAY_DEFER_SHRINK = 1 << 1
} GBSearchArrayFlags;
/* --- structures --- */
struct _GBSearchConfig
{
guint16 sizeof_node;
GBSearchCompareFunc cmp_nodes;
guint16 flags;
};
union _GBSearchArray
{
guint n_nodes;
gpointer alignment_dummy1;
glong alignment_dummy2;
gdouble alignment_dummy3;
};
/* --- prototypes --- */
GBSearchArray* g_bsearch_array_new (GBSearchConfig *bconfig);
void g_bsearch_array_destroy (GBSearchArray *barray,
GBSearchConfig *bconfig);
GBSearchArray* g_bsearch_array_insert (GBSearchArray *barray,
GBSearchConfig *bconfig,
gconstpointer key_node,
gboolean replace_existing);
GBSearchArray* g_bsearch_array_remove (GBSearchArray *barray,
GBSearchConfig *bconfig,
gconstpointer key_node);
GBSearchArray* g_bsearch_array_remove_node (GBSearchArray *barray,
GBSearchConfig *bconfig,
gpointer node_in_array);
G_INLINE_FUNC
gpointer g_bsearch_array_lookup (GBSearchArray *barray,
GBSearchConfig *bconfig,
gconstpointer key_node);
G_INLINE_FUNC
gpointer g_bsearch_array_get_nth (GBSearchArray *barray,
GBSearchConfig *bconfig,
guint n);
G_INLINE_FUNC
guint g_bsearch_array_get_index (GBSearchArray *barray,
GBSearchConfig *bconfig,
gpointer node_in_array);
/* initialization of static arrays */
#define G_STATIC_BCONFIG(sizeof_node, cmp_nodes, flags) \
{ (sizeof_node), (cmp_nodes), (flags), }
/* --- implementation details --- */
#define G_BSEARCH_ARRAY_NODES(barray) ((gpointer) (((guint8*) (barray)) + sizeof (GBSearchArray)))
#if defined (G_CAN_INLINE) || defined (__G_BSEARCHARRAY_C__)
G_INLINE_FUNC gpointer
g_bsearch_array_lookup (GBSearchArray *barray,
GBSearchConfig *bconfig,
gconstpointer key_node)
{
if (barray->n_nodes > 0)
{
GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
gint sizeof_node = bconfig->sizeof_node;
guint n_nodes = barray->n_nodes;
guint8 *nodes = G_BSEARCH_ARRAY_NODES (barray);
nodes -= sizeof_node;
do
{
guint8 *check;
guint i;
register gint cmp;
i = (n_nodes + 1) >> 1;
check = nodes + i * sizeof_node;
cmp = cmp_nodes (key_node, check);
if (cmp == 0)
return check;
else if (cmp > 0)
{
n_nodes -= i;
nodes = check;
}
else /* if (cmp < 0) */
n_nodes = i - 1;
}
while (n_nodes);
}
return NULL;
}
G_INLINE_FUNC gpointer
g_bsearch_array_get_nth (GBSearchArray *barray,
GBSearchConfig *bconfig,
guint n)
{
if (n < barray->n_nodes)
{
guint8 *nodes = (guint8*) G_BSEARCH_ARRAY_NODES (barray);
return nodes + n * bconfig->sizeof_node;
}
else
return NULL;
}
G_INLINE_FUNC
guint
g_bsearch_array_get_index (GBSearchArray *barray,
GBSearchConfig *bconfig,
gpointer node_in_array)
{
guint distance = ((guint8*) node_in_array) - ((guint8*) G_BSEARCH_ARRAY_NODES (barray));
distance /= bconfig->sizeof_node;
return MIN (distance, barray->n_nodes);
}
#endif /* G_CAN_INLINE || __G_BSEARCHARRAY_C__ */
G_END_DECLS
#endif /* __G_BSEARCH_ARRAY_H__ */
See more files for this project here