[Spread-cvs] commit: r251 - trunk/daemon
jschultz at spread.org
jschultz at spread.org
Fri Jul 22 04:40:35 EDT 2005
Author: jschultz
Date: 2005-07-22 04:40:34 -0400 (Fri, 22 Jul 2005)
New Revision: 251
Removed:
trunk/daemon/skiplist.c
trunk/daemon/skiplist.h
trunk/daemon/skiplist_p.h
Modified:
trunk/daemon/Makefile.in
trunk/daemon/groups.c
trunk/daemon/sess_body.h
Log:
Major changes to groups.c -- converted to use stdutil skiplists rather than Theo's. Removed old skiplist code. Compiles but not tested yet.
Modified: trunk/daemon/Makefile.in
===================================================================
--- trunk/daemon/Makefile.in 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/Makefile.in 2005-07-22 08:40:34 UTC (rev 251)
@@ -33,7 +33,7 @@
CC=@CC@
LD=@LD@
CFLAGS=@CFLAGS@
-CPPFLAGS=-I. -I$(srcdir) -I$(top_srcdir)/include @CPPFLAGS@ $(PATHS) @DEFS@
+CPPFLAGS=-I. -I$(srcdir) -I$(top_srcdir)/include -I../stdutil/src @CPPFLAGS@ $(PATHS) @DEFS@
LDFLAGS=@LDFLAGS@
LIBS=@LIBS@
THLDFLAGS=@THLDFLAGS@
Modified: trunk/daemon/groups.c
===================================================================
--- trunk/daemon/groups.c 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/groups.c 2005-07-22 08:40:34 UTC (rev 251)
@@ -31,7 +31,6 @@
*
*/
-
#include "arch.h"
#include <string.h>
#include <stdio.h>
@@ -53,7 +52,6 @@
#if ( SPREAD_PROTOCOL > 3 )
#include "queues.h"
#endif
-#include "skiplist.h"
#include "alarm.h"
#include "message.h"
@@ -125,7 +123,7 @@
static int Groups_control_down_queue;
-static Skiplist GroupsList;
+static stdskl GroupsList; /* (char*) -> (group*) */
static synced_set MySyncedSet;
static membership_id unknown_memb_id = { -1, -1 }; /* See explanation above. */
@@ -151,8 +149,7 @@
static message_link *G_build_trans_mess( group *grp );
static void G_build_groups_msg_hdr( message_obj *msg, int groups_bytes );
-static int G_build_groups_buf( char buf[], struct skiplistnode **giter_ptr,
- struct skiplistnode **diter_ptr );
+static int G_build_groups_buf( char buf[], stdit *git, stdit *dit, int first_time );
static void G_build_new_groups_bufs(void);
static int G_send_groups_messages(void);
static void G_stamp_groups_bufs(void);
@@ -171,25 +168,39 @@
static void G_remove_daemon( group *grp, daemon_members *dmn );
static void G_remove_group( group *grp );
-static int G_compare(void *, void *);
+static int G_compare_cstrptr(const void *, const void *);
+static int G_compare_proc_ids_by_conf( const void *, const void * );
+static int G_compare_daemon_vs_set( const void *, const void * );
static int G_compare_memb_ids( const membership_id *mid1,
const membership_id *mid2 );
-static int G_compare_proc_ids_by_conf( int32 pid1, int32 pid2 );
-static int G_daemon_recordcompare( void *a, void *b );
-static int G_daemon_keycompare( void *key, void *b );
-static int G_daemon_vs_set_recordcompare( void *a, void *b );
-/* Comparator function for anything that starts with a null-terminated char[] which
- * is also the key. This applies to group and member objects, and so this function
- * is used as the comparator for their records and keys. */
-static int G_compare(void *a, void *b)
+static int G_compare_cstrptr(const void *a, const void *b)
{
- assert(a);
- assert(b);
- return strcmp((char *)a, (char *)b);
+ return strcmp(*(const char**) a, *(const char**) b);
}
+static int G_compare_proc_ids_by_conf(const void *a, const void *b)
+{
+ proc dummy_proc;
+ int ia = Conf_proc_by_id( *(const int32*) a, &dummy_proc );
+ int ib = Conf_proc_by_id( *(const int32*) b, &dummy_proc );
+
+ assert( ia > -1 );
+ assert( ib > -1 );
+
+ return ia - ib;
+}
+
+static int G_compare_daemon_vs_set(const void *a, const void *b)
+{
+ const daemon_members *da = *(const daemon_members**) a;
+ const daemon_members *db = *(const daemon_members**) b;
+ int cmp = G_compare_memb_ids(&da->memb_id, &db->memb_id);
+
+ return (cmp != 0 ? cmp : G_compare_proc_ids_by_conf(&da->proc_id, &db->proc_id));
+}
+
/* Compares two memb_ids. Arbitrary, but deterministic. A memb_id with a proc_id
* of -1 compares after ANY other memb_id, by definition. */
static int G_compare_memb_ids( const membership_id *mid1, const membership_id *mid2 )
@@ -212,55 +223,6 @@
return 0;
}
-/* Compares two daemon proc_ids, by their order in the conf. */
-static int G_compare_proc_ids_by_conf( int32 pid1, int32 pid2 )
-{
- int ia, ib;
- proc dummy_proc;
- ia = Conf_proc_by_id( pid1, &dummy_proc );
- ib = Conf_proc_by_id( pid2, &dummy_proc );
- assert( ia > -1 );
- assert( ib > -1 );
- return ia - ib;
-}
-
-/* Takes two daemons and compares them based on their indexes in the
- * configuration. */
-static int G_daemon_recordcompare( void *a, void *b )
-{
- daemon_members *da, *db;
- da = (daemon_members *) a;
- db = (daemon_members *) b;
- assert(da);
- assert(db);
- return G_compare_proc_ids_by_conf( da->proc_id, db->proc_id );
-}
-
-/* Compares in the same way. */
-static int G_daemon_keycompare( void *key, void *b )
-{
- int32 *pida = (int32 *)key;
- daemon_members *db = (daemon_members *)b;
- assert(pida);
- assert(db);
- return G_compare_proc_ids_by_conf( *pida, db->proc_id );
-}
-
-/* Compares two daemons by gid. Conf order is used to break ties. */
-static int G_daemon_vs_set_recordcompare( void *a, void *b )
-{
- int compared;
- daemon_members *da, *db;
- da = (daemon_members *) a;
- db = (daemon_members *) b;
- assert(da);
- assert(db);
- compared = G_compare_memb_ids( &(da->memb_id), &(db->memb_id) );
- if( compared )
- return compared;
- return G_compare_proc_ids_by_conf( da->proc_id, db->proc_id );
-}
-
void G_init()
{
int ret;
@@ -269,20 +231,15 @@
Num_groups = 0;
GlobalStatus.num_groups = Num_groups;
-
- sl_init(&GroupsList);
- /* Key's address is the same as records address and is a null
- terminated string, so we can use the same function to compare
- record<->record
- key<->record */
- sl_set_compare(&GroupsList,
- G_compare,
- G_compare);
-
+
MySyncedSet.size = 1;
MySyncedSet.proc_ids[0] = My.id;
G_print_synced_set( SPLOG_INFO, &MySyncedSet, "G_init" );
+ ret = stdskl_construct(&GroupsList, sizeof(char*), sizeof(group*), G_compare_cstrptr);
+ if (ret != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_init: Failure to Initialize GroupsList\n");
+ }
ret = Mem_init_object(GROUP, sizeof(group), 1000, 0);
if (ret < 0)
{
@@ -328,14 +285,14 @@
void G_handle_reg_memb( configuration reg_memb, membership_id reg_memb_id )
{
- group *grp, *nextgroup;
- struct skiplistnode *giter;
+ group *grp;
groups_message_link *grp_mlink;
message_link *mess_link;
synced_set sset;
int ret;
char ip_string[16];
int group_changed, synced_set_changed;
+ stdit it;
IP_to_STR( reg_memb_id.proc_id, ip_string );
Alarmp( SPLOG_INFO, GROUPS, "G_handle_reg_memb: with (%s, %d) id\n",
@@ -375,42 +332,43 @@
if( Conf_num_procs( &Trans_memb ) == Conf_num_procs( &Reg_memb ) )
{
- giter = sl_getlist( &GroupsList );
- grp = (giter) ? (group *)giter->data : NULL;
- for( ; grp != NULL ; grp = nextgroup )
- {
- nextgroup = sl_next( &GroupsList, &giter );
- if( grp->changed )
- {
- /* The group has changed */
- /* eliminating partitioned daemons */
- G_eliminate_partitioned_daemons( grp );
- if( grp->num_members == 0 )
- {
- /* discard this empty group */
- G_remove_group( grp );
- }else{
- Alarmp( SPLOG_INFO, GROUPS,
- "G_handle_reg_memb: no state transfer needed for group %s.\n",
- grp->name );
- Alarmp( SPLOG_DEBUG, GROUPS,
- "G_handle_reg_memb: changing group_id for group %s\n", grp->name );
- G_print_group_id( SPLOG_DEBUG, grp->grp_id, "G_handle_reg_memb" );
- grp->grp_id.memb_id = Reg_memb_id;
- grp->grp_id.index = 1;
- grp->changed = 0;
- G_print_group_id( SPLOG_DEBUG, grp->grp_id, "G_handle_reg_memb" );
- G_update_daemon_memb_ids( grp );
- if( grp->num_local > 0 )
- {
- G_send_heavyweight_memb( grp );
- }
- }
+ for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
+ {
+ grp = *(group**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
+ if( grp->changed )
+ {
+ /* The group has changed */
+ /* eliminating partitioned daemons */
+ G_eliminate_partitioned_daemons( grp );
+ if( grp->num_members == 0 )
+ {
+ /* discard this empty group */
+ G_remove_group( grp );
+ }else{
+ Alarmp( SPLOG_INFO, GROUPS,
+ "G_handle_reg_memb: no state transfer needed for group %s.\n",
+ grp->name );
+ Alarmp( SPLOG_DEBUG, GROUPS,
+ "G_handle_reg_memb: changing group_id for group %s\n", grp->name );
+ G_print_group_id( SPLOG_DEBUG, grp->grp_id, "G_handle_reg_memb" );
+ grp->grp_id.memb_id = Reg_memb_id;
+ grp->grp_id.index = 1;
+ grp->changed = 0;
+ G_print_group_id( SPLOG_DEBUG, grp->grp_id, "G_handle_reg_memb" );
+ G_update_daemon_memb_ids( grp );
+ if( !stdskl_empty(&grp->mboxes) )
+ {
+ G_send_heavyweight_memb( grp );
+ }
+ }
+ }
}
- }
- Gstate = GOP;
- GlobalStatus.gstate = Gstate;
+ Gstate = GOP;
+ GlobalStatus.gstate = Gstate;
+
} else {
/*
* else
@@ -424,11 +382,12 @@
* Shift to GGATHER
*/
- giter = sl_getlist( &GroupsList );
- grp = (giter)?(group *)giter->data:NULL;
- for( ; grp != NULL ; grp = nextgroup )
- {
- nextgroup = sl_next( &GroupsList, &giter );
+
+ for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
+ {
+ grp = *(group**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
if( grp->changed )
{
/* The group has changed */
@@ -526,23 +485,23 @@
* so as to not deliver potentially inconsistent groups messages
* if we completed the old state exchange. Now, prepare for the next one.
*/
- giter = sl_getlist( &GroupsList );
- grp = (giter)?(group *)giter->data:NULL;
- for( ; grp != NULL ; grp = nextgroup )
- {
- nextgroup = sl_next( &GroupsList, &giter );
- group_changed = G_eliminate_partitioned_daemons( grp );
- if( group_changed )
- {
- Groups_bufs_fresh = 0;
- if( grp->num_members == 0 )
- {
- /* discard this empty group */
- G_remove_group( grp );
- } else {
- grp->changed = 1;
- }
- }
+ for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
+ {
+ grp = *(group**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
+ group_changed = G_eliminate_partitioned_daemons( grp );
+ if( group_changed )
+ {
+ Groups_bufs_fresh = 0;
+ if( grp->num_members == 0 )
+ {
+ /* discard this empty group */
+ G_remove_group( grp );
+ } else {
+ grp->changed = 1;
+ }
+ }
}
synced_set_changed = G_check_synced_set( &MySyncedSet, &Trans_memb );
G_print_synced_set( SPLOG_INFO, &MySyncedSet, "G_handle_reg_memb" );
@@ -577,11 +536,11 @@
void G_handle_trans_memb( configuration trans_memb, membership_id trans_memb_id )
{
- group *grp, *nextgroup;
- daemon_members *dmn, *nextdaemon;
- struct skiplistnode *giter, *diter;
+ group *grp;
+ daemon_members *dmn;
int group_changed;
char ip_string[16];
+ stdit git, dit;
IP_to_STR( trans_memb_id.proc_id, ip_string );
Alarmp( SPLOG_INFO, GROUPS, "G_handle_trans_memb: with (%s, %d) id\n",
@@ -604,16 +563,18 @@
Trans_memb = trans_memb;
Trans_memb_id = trans_memb_id;
- giter = sl_getlist( &GroupsList );
- grp = (giter) ? (group *)giter->data : NULL;
- for( ; grp != NULL ; grp = nextgroup )
- {
- nextgroup = sl_next( &GroupsList, &giter );
+ for (stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); )
+ {
+ grp = *(group**) stdskl_it_val(&git);
+ stdskl_it_next(&git); /* NOTE: need to do advancement before potential erasure below */
+
group_changed = 0;
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL; dmn = nextdaemon ) {
- nextdaemon = sl_next( &grp->DaemonsList, &diter );
+
+ for (stdskl_begin(&grp->DaemonsList, &dit); !stdskl_is_end(&grp->DaemonsList, &dit); )
+ {
+ dmn = *(daemon_members**) stdskl_it_val(&dit);
+ stdskl_it_next(&dit); /* NOTE: need to do advancement before potential erasure below */
+
if( Conf_id_in_conf( &Trans_memb, dmn->proc_id ) == -1 )
{
/* mark this daemon as partitioned - proc no longer in membership */
@@ -623,7 +584,7 @@
}
if( group_changed )
{
- if( grp->num_local > 0 )
+ if( !stdskl_empty(&grp->mboxes) )
{
G_send_trans_memb( grp );
}
@@ -686,14 +647,15 @@
* Cons: This isn't strictly required by EVS.
*/
- giter = sl_getlist( &GroupsList );
- grp = (giter)?(group *)giter->data:NULL;
- for( ; grp != NULL ; grp = nextgroup )
- {
- nextgroup = sl_next( &GroupsList, &giter );
+ for (stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); )
+ {
+ grp = *(group**) stdskl_it_val(&git);
+ stdskl_it_next(&git); /* NOTE: need to do advancement before potential erasure below */
+
group_changed = G_check_if_changed_by_cascade( grp );
- if( group_changed )
+ if( group_changed ) {
grp->changed = 1;
+ }
}
Gstate = GGT;
@@ -770,10 +732,15 @@
new_grp = new( GROUP );
memset( new_grp->name, 0, MAX_GROUP_NAME );
strcpy( new_grp->name, group_name );
- sl_init( &new_grp->DaemonsList );
- sl_set_compare( &new_grp->DaemonsList,
- G_daemon_recordcompare,
- G_daemon_keycompare );
+
+ if (stdskl_construct(&new_grp->DaemonsList, sizeof(int32), sizeof(daemon_members*), G_compare_proc_ids_by_conf) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ if (stdskl_construct(&new_grp->mboxes, sizeof(mailbox), 0, NULL) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
/* NOTE: Older versions of groups do mark a new group as changed if it's
* created in GTRANS. This is only needed if the joiner is partitioned
* from us [handled below]. */
@@ -789,10 +756,12 @@
G_print_group_id( SPLOG_DEBUG, new_grp->grp_id, "G_handle_join" );
new_grp->num_members = 0;
- new_grp->num_local = 0;
- sl_insert( &GroupsList, new_grp );
- Num_groups++; /*sl need this? No, but its nice to have, kept global. */
+ if (stdskl_insert(&GroupsList, &new_grp->GroupsListIt, &new_grp->name, &new_grp, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ Num_groups++;
GlobalStatus.num_groups = Num_groups;
grp = new_grp;
}
@@ -801,15 +770,22 @@
if( dmn == NULL ) {
new_dmn = new( DAEMON_MEMBERS );
new_dmn->proc_id = new_p.id;
- sl_init( &new_dmn->MembersList );
- sl_set_compare( &new_dmn->MembersList, G_compare, G_compare );
- sl_insert( &grp->DaemonsList, new_dmn );
+
+ if (stdskl_construct(&new_dmn->MembersList, sizeof(member*), 0, G_compare_cstrptr) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
/* Are we partitioned from this daemon? */
if( Gstate == GOP || ( Conf_id_in_conf( &Trans_memb, new_p.id ) != -1 ) ) {
new_dmn->memb_id = grp->grp_id.memb_id;
} else {
new_dmn->memb_id = unknown_memb_id;
}
+
+ if (stdskl_insert(&grp->DaemonsList, &new_dmn->DaemonsListIt, &new_dmn->proc_id, &new_dmn, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
dmn = new_dmn;
}
@@ -825,7 +801,10 @@
memset( new_mbr->name, 0, MAX_GROUP_NAME );
strcpy( new_mbr->name, private_group_name );
- sl_insert( &dmn->MembersList, new_mbr );
+ if (stdskl_insert(&dmn->MembersList, &new_mbr->MembersListIt, &new_mbr, NULL, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
grp->num_members++;
grp->grp_id.index++;
@@ -834,16 +813,19 @@
{
ses = Sess_get_session( private_name );
if( ses < 0 ) Alarmp( SPLOG_FATAL, GROUPS, "G_handle_join: local session does not exist\n" );
- grp->mbox[ grp->num_local ] = Sessions[ ses ].mbox;
- grp->num_local++;
+
new_mbox = Sessions[ ses ].mbox;
+
+ if (stdskl_put(&grp->mboxes, NULL, &new_mbox, NULL, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
} else
new_mbox = -1;
if( Is_partitioned_daemon( dmn ) && !grp->changed )
grp->changed = 1;
- if( grp->num_local > 0 ) {
+ if( !stdskl_empty(&grp->mboxes) ) {
if( grp->changed )
{
G_send_heavyweight_join( grp, new_mbr, new_mbox );
@@ -882,7 +864,6 @@
group *grp;
daemon_members *dmn;
member *mbr;
- int i,j;
Alarmp( SPLOG_INFO, GROUPS, "G_handle_leave: %s leaves group %s\n", private_group_name, group_name );
@@ -942,18 +923,13 @@
/* notify this local member and extract its mbox from group */
ses = Sess_get_session( private_name );
G_send_self_leave( grp, ses );
- /* extract this mbox */
- for( i=0, j=0; i < grp->num_local; i++,j++ )
- {
- if( grp->mbox[i] == Sessions[ses].mbox ) j--;
- else grp->mbox[j] = grp->mbox[i];
- }
- grp->num_local--;
+ stdskl_erase_key(&grp->mboxes, &Sessions[ses].mbox);
}
/* extract this member from group */
memcpy( departing_private_group_name, mbr->name, MAX_GROUP_NAME );
- sl_remove( &dmn->MembersList, mbr->name, dispose );
+ stdskl_erase(&dmn->MembersList, &mbr->MembersListIt);
+ dispose(mbr);
grp->num_members--;
if( dmn->MembersList.size == 0 )
{
@@ -973,7 +949,7 @@
* We never need to mark a group as changed here, or in G_handle_kill.
*/
- if( grp->num_local > 0 )
+ if( !stdskl_empty(&grp->mboxes) )
{
if( grp->changed )
{
@@ -1008,12 +984,11 @@
char departing_private_group_name[MAX_GROUP_NAME];
int p_ind;
proc p;
- group *grp, *nextgroup;
+ group *grp;
daemon_members *dmn;
member *mbr;
int ses = -1; /* Fool compiler */
- int i, j;
- struct skiplistnode *giter;
+ stdit it;
Alarmp( SPLOG_INFO, GROUPS, "G_handle_kill: %s is killed\n", private_group_name );
@@ -1048,14 +1023,11 @@
if( p.id == My.id ) ses = Sess_get_session( private_name );
- giter = sl_getlist( &GroupsList );
- grp = (giter)?(group *)giter->data:NULL;
- for( ; grp != NULL ; grp = nextgroup)
+ for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- /* This is confusing... get the nextgroup so that if we
- choose to remove it it doesn't screw up the iterator.
- Then next time through use this "next" value */
- nextgroup = sl_next( &GroupsList, &giter );
+ grp = *(group**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
dmn = G_get_daemon( grp, p.id );
if( dmn == NULL ) continue; /* member's daemon not in group */
mbr = G_get_member( dmn, private_group_name );
@@ -1064,16 +1036,11 @@
/* Extract this member from group */
if( p.id == My.id )
{
- /* extract the mbox if local member */
- for( i=0, j=0; i < grp->num_local; i++, j++ )
- {
- if( grp->mbox[i] == Sessions[ses].mbox ) j--;
- else grp->mbox[j] = grp->mbox[i];
- }
- grp->num_local--;
+ stdskl_erase_key(&grp->mboxes, &Sessions[ses].mbox);
}
memcpy( departing_private_group_name, mbr->name, MAX_GROUP_NAME );
- sl_remove( &dmn->MembersList, mbr->name, dispose );
+ stdskl_erase(&dmn->MembersList, &mbr->MembersListIt);
+ dispose(mbr);
grp->num_members--;
if( dmn->MembersList.size == 0 )
{
@@ -1089,7 +1056,7 @@
/* Increment group id */
grp->grp_id.index++;
- if( grp->num_local > 0 )
+ if( !stdskl_empty(&grp->mboxes) )
{
if( grp->changed )
{
@@ -1126,12 +1093,12 @@
message_link *mess_link;
message_header *head_ptr;
message_obj *msg;
- int i;
int32u temp;
char *num_vs_sets_ptr; /* number of vs_sets */
char *vs_set_offset_ptr; /* Byte offset into the vs_set region of my vs_set */
char *num_vs_ptr; /* num members in virtual-synchrony/failure-atomicity set */
char *vs_ptr; /* the virtual synchrony set */
+ stdit it;
msg = Message_new_message();
num_bytes = G_build_memb_buf( grp, msg, Mess_buf, caused );
@@ -1165,9 +1132,9 @@
Obj_Inc_Refcount(mess_link->mess);
needed = 0;
- for( i=0; i < grp->num_local; i++ )
- {
- ses = Sess_get_session_index ( grp->mbox[i] );
+ for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+ {
+ ses = Sess_get_session_index ( *(mailbox*) stdskl_it_key(&it) );
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1223,7 +1190,7 @@
char *local_vs_set_offset_ptr;
int needed, joiner_needed;
int ses;
- int i;
+ stdit it;
msg = Message_new_message();
num_bytes = G_build_memb_vs_buf( grp, msg, Mess_buf, CAUSED_BY_NETWORK, joiner );
@@ -1236,12 +1203,14 @@
/* notify local members */
needed = 0;
- for( i=0; i < grp->num_local; i++ )
- {
+ for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+ {
+ mailbox m = *(mailbox*) stdskl_it_key(&it);
+
/* if new member is local we do not notify it here. */
- if( joiner != NULL && grp->mbox[i] == new_mbox ) continue;
+ if( joiner != NULL && new_mbox == m) continue;
- ses = Sess_get_session_index ( grp->mbox[i] );
+ ses = Sess_get_session_index ( m );
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1284,14 +1253,16 @@
message_link *mess_link;
int needed;
int ses;
- int i;
+ stdit it;
/* send members transitional membership */
mess_link = G_build_trans_mess( grp );
needed = 0;
- for( i=0; i < grp->num_local; i++ )
- {
- ses = Sess_get_session_index ( grp->mbox[i] );
+ for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+ {
+ mailbox m = *(mailbox*) stdskl_it_key(&it);
+
+ ses = Sess_get_session_index ( m );
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1449,11 +1420,11 @@
static void G_compute_and_notify()
{
group *grp;
- struct skiplistnode *giter;
int ret;
groups_message_link *grp_mlink;
message_link *mess_link;
synced_set sset;
+ stdit it;
Alarmp( SPLOG_INFO, GROUPS, "G_compute_and_notify:\n");
/* Add contents of groups messages from other synced sets to my GroupsList,
@@ -1480,10 +1451,11 @@
/* At this point, our GroupsList is complete, as is our synced_set. */
- giter = sl_getlist( &GroupsList );
- grp = (giter) ? (group *)giter->data : NULL;
- for( ; grp != NULL ; grp = sl_next( &GroupsList, &giter ) )
- {
+ for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
+ {
+ grp = *(group**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
/*
* for every group:
* If the group has changed (*)
@@ -1509,7 +1481,7 @@
grp->grp_id.memb_id = Reg_memb_id;
grp->grp_id.index = 1;
grp->changed = 0;
- if( grp->num_local > 0 )
+ if( !stdskl_empty(&grp->mboxes) )
G_send_heavyweight_memb( grp );
G_update_daemon_memb_ids( grp );
}
@@ -1535,21 +1507,29 @@
static group *G_get_group( char *group_name )
{
- struct skiplistnode *iter;
- return sl_find( &GroupsList, group_name, &iter );
+ stdit it;
+
+ stdskl_find(&GroupsList, &it, &group_name);
+
+ return (!stdskl_is_end(&GroupsList, &it) ? *(group**) stdskl_it_val(&it) : NULL);
}
-static daemon_members *G_get_daemon( group *grp, int32u proc_id ) {
- struct skiplistnode *iter;
- assert(grp);
- return sl_find( &grp->DaemonsList, &proc_id, &iter );
+static daemon_members *G_get_daemon( group *grp, int32u proc_id )
+{
+ stdit it;
+
+ stdskl_find(&grp->DaemonsList, &it, &proc_id);
+
+ return (!stdskl_is_end(&grp->DaemonsList, &it) ? *(daemon_members**) stdskl_it_val(&it) : NULL);
}
static member *G_get_member( daemon_members *dmn, char *private_group_name )
{
- struct skiplistnode *iter;
- assert(dmn);
- return sl_find( &dmn->MembersList, private_group_name, &iter );
+ stdit it;
+
+ stdskl_find(&dmn->MembersList, &it, &private_group_name);
+
+ return (!stdskl_is_end(&dmn->MembersList, &it) ? *(member**) stdskl_it_key(&it) : NULL);
}
static message_link *G_build_trans_mess( group *grp )
@@ -1591,8 +1571,8 @@
char *gid_ptr;
member *mbr;
daemon_members *dmn;
- struct skiplistnode *diter, *iter;
char *memb_ptr;
+ stdit it, mit;
head_ptr = Message_get_message_header(msg);
head_ptr->type = REG_MEMB_MESS;
@@ -1604,14 +1584,16 @@
head_ptr->data_len = sizeof( group_id );
num_bytes = 0;
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL ; dmn = sl_next( &grp->DaemonsList, &diter ) )
- {
- iter = sl_getlist( &dmn->MembersList );
- mbr = (iter) ? (member *)iter->data : NULL;
- for( ; mbr != NULL ; mbr = sl_next( &dmn->MembersList, &iter ) )
- {
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); )
+ {
+ dmn = *(daemon_members**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
+
+ for (stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); )
+ {
+ mbr = *(member**) stdskl_it_val(&mit);
+ stdskl_it_next(&mit); /* NOTE: need to do advancement before potential erasure below */
+
memb_ptr = &buf[num_bytes];
num_bytes += MAX_GROUP_NAME;
memcpy( memb_ptr, mbr->name, MAX_GROUP_NAME );
@@ -1674,13 +1656,13 @@
int32u curr_vs_set_size;
membership_id curr_vs_set_memb_id;
- struct skiplistnode *diter, *iter;
daemon_members *dmn;
member *mbr;
char *membs_ptr;
- Skiplist temp;
+ stdskl temp;
int needed;
int found_joiner = 0;
+ stdit it, mit;
num_bytes = G_build_memb_buf( grp, msg, buf, caused );
head_ptr = Message_get_message_header(msg);
@@ -1701,21 +1683,23 @@
vs_set_region_ptr = &buf[num_bytes];
/* Basically, use the skiplist to do an insertion sort. */
- sl_init(&temp);
- sl_set_compare( &temp, G_daemon_vs_set_recordcompare, G_daemon_keycompare );
- /* FIXME: should I limit the height of the skiplist to 1, or not? */
- /* temp.preheight = 1; */
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL; dmn = sl_next( &grp->DaemonsList, &diter ) )
- sl_insert( &temp, dmn );
+ if (stdskl_construct(&temp, sizeof(daemon_members*), 0, G_compare_daemon_vs_set) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
+ {
+ if (stdskl_insert(&temp, NULL, (daemon_members**) stdskl_it_val(&it), NULL, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+ }
+
curr_vs_set_memb_id = unknown_memb_id;
curr_vs_set_size_ptr = NULL;
- diter = sl_getlist( &temp );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL; dmn = sl_next( &temp, &diter ) ) {
+ for (stdskl_begin(&temp, &it); !stdskl_is_end(&temp, &it); stdskl_it_next(&it))
+ {
+ dmn = *(daemon_members**) stdskl_it_key(&it);
needed = 0;
if( Is_unknown_memb_id(&curr_vs_set_memb_id) ||
!Memb_is_equal( curr_vs_set_memb_id, dmn->memb_id ) )
@@ -1735,10 +1719,11 @@
local_vs_set_offset = curr_vs_set_size_ptr - vs_set_region_ptr;
memcpy( local_vs_set_offset_ptr, &local_vs_set_offset, sizeof(int32u) );
}
- iter = sl_getlist( &dmn->MembersList );
- mbr = (iter) ? (member *)iter->data : NULL;
- for( ; mbr != NULL ; mbr = sl_next( &dmn->MembersList, &iter ) )
- {
+
+ for (stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); stdskl_it_next(&mit))
+ {
+ mbr = *(member**) stdskl_it_key(&mit);
+
/* Handle changed-group join during transitional. The joiner does not
* get to be listed with everyone else from his daemon, but rather at
* the end, in a self vs set. */
@@ -1774,7 +1759,7 @@
}
/* Make sure we don't leak memory before the stack gets freed and takes
* the skiplist with it. We don't actually want to free the daemons. */
- sl_destruct( &temp, (FreeFunc)NULL );
+ stdskl_destruct(&temp);
memcpy( num_vs_sets_ptr, &num_vs_sets, sizeof(int32u) );
return( num_bytes );
@@ -1803,7 +1788,7 @@
/* This function guarantees that each daemon's data about a given group appears in only one buffer in
* a sequence, and that the sorted order is preserved from the GroupsList. */
-static int G_build_groups_buf( char buf[], struct skiplistnode **giter_ptr, struct skiplistnode **diter_ptr )
+static int G_build_groups_buf( char buf[], stdit *git, stdit *dit, int first_time)
{
int num_bytes;
@@ -1817,7 +1802,6 @@
char *proc_id_ptr; /* int32 */
char *dmn_memb_id_ptr; /* membership_id */
member *mbr;
- struct skiplistnode *iter;
char *num_dmns_ptr; /* int16u */
int16u num_dmns;
char *num_memb_ptr; /* int16u */
@@ -1826,6 +1810,7 @@
int32u size_needed;
int couldnt_fit_daemon;
+ stdit mit;
/* A GROUPS message looks like this:
* (Representative's name is in header, so we can get his proc id)
@@ -1860,27 +1845,32 @@
flag_ptr = &buf[num_bytes];
num_bytes += sizeof(char);
- if( *giter_ptr )
+
+ if (!first_time) {
Set_later_message(flag_ptr);
- else
- Set_first_message(flag_ptr);
- if( Is_first_message(flag_ptr) )
- {
+ } else {
+ Set_first_message(flag_ptr);
synced_set_size_ptr = &buf[num_bytes];
num_bytes += sizeof(int32u);
memcpy( synced_set_size_ptr, &(MySyncedSet.size), sizeof(int32u) );
synced_set_procs_ptr = &buf[num_bytes];
num_bytes += MySyncedSet.size * sizeof(int32);
memcpy( synced_set_procs_ptr, &MySyncedSet.proc_ids, MySyncedSet.size*sizeof(int32) );
- }
+
+ stdskl_begin(&GroupsList, git);
+ }
/* Resume where we left off in the GroupsList */
couldnt_fit_daemon = 0;
- *giter_ptr = (*giter_ptr)? (*giter_ptr) : (sl_getlist(&GroupsList));
- grp = (*giter_ptr)? (group *) (*giter_ptr)->data : NULL;
- for( ; grp != NULL ; grp = sl_next(&GroupsList, giter_ptr) )
+ while (!stdskl_is_end(&GroupsList, git))
{
+ grp = *(group**) stdskl_it_val(git);
+
+ if (first_time) { /* initialize dit on first call to this fcn */
+ stdskl_begin(&grp->DaemonsList, dit);
+ }
+
/* To have information about this group, we need to be able to fit
* its name, ID, and the number of daemons it has in this message. */
size_needed = MAX_GROUP_NAME + sizeof(group_id) + sizeof(int16u) + Message_get_data_header_size();
@@ -1896,10 +1886,9 @@
num_bytes += sizeof(int16u);
num_dmns = 0;
- *diter_ptr = (*diter_ptr)? (*diter_ptr) : (sl_getlist(&grp->DaemonsList));
- dmn = (*diter_ptr)? (daemon_members *) (*diter_ptr)->data : NULL;
- for( ; dmn != NULL; dmn = sl_next(&grp->DaemonsList, diter_ptr) )
- {
+ for (; !stdskl_is_end(&grp->DaemonsList, dit); stdskl_it_next(dit))
+ {
+ dmn = *(daemon_members**) stdskl_it_val(dit);
/* To store this daemon's information about the current group,
* we need to be able to store its proc_id, memb_id, number of
* local members, and the private group names of its local members. */
@@ -1923,10 +1912,9 @@
num_bytes += sizeof(int16u);
num_memb = 0;
- iter = sl_getlist( &dmn->MembersList );
- mbr = (iter)? (member *) iter->data : NULL;
- for( ; mbr != NULL ; mbr = sl_next(&dmn->MembersList, &iter) )
- {
+ for (stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); stdskl_it_next(&mit))
+ {
+ mbr = *(member**) stdskl_it_key(&mit);
/* Add to the buffer all group members from this daemon. */
memb_ptr = &buf[num_bytes];
num_bytes += MAX_GROUP_NAME;
@@ -1943,24 +1931,31 @@
memcpy( num_dmns_ptr, &num_dmns, sizeof(int16u) );
if( couldnt_fit_daemon )
break;
+
+ stdskl_it_next(git); /* advance group iterator */
+
+ if (!stdskl_is_end(&GroupsList, git)) { /* if loop not done, then init dit iterator for the advanced git */
+ grp = *(group**) stdskl_it_val(git);
+ stdskl_begin(&grp->DaemonsList, dit);
+ }
}
return( num_bytes );
}
static void G_build_new_groups_bufs()
{
- struct skiplistnode *passed_giter, *passed_diter;
+ stdit git, dit;
+ int first_time = 1;
groups_buf_link *grps_buf_link;
- passed_giter = NULL;
- passed_diter = NULL;
do {
grps_buf_link = new( GROUPS_BUF_LINK );
grps_buf_link->next = Groups_bufs;
Groups_bufs = grps_buf_link;
- grps_buf_link->bytes = G_build_groups_buf( grps_buf_link->buf,
- &passed_giter, &passed_diter );
- } while( passed_giter != NULL );
+ grps_buf_link->bytes = G_build_groups_buf(grps_buf_link->buf, &git, &dit, first_time);
+ first_time = 0;
+
+ } while (!stdskl_is_end(&GroupsList, &git));
}
/* This function used to be called G_refresh_groups_msg. */
@@ -2042,6 +2037,7 @@
member *mbr;
int i,j;
char ip_string[16];
+ stdit it;
total_bytes = 0;
msg = mess_link->mess;
@@ -2090,16 +2086,18 @@
grp = new( GROUP );
memset( grp->name, 0, MAX_GROUP_NAME );
strcpy( grp->name, group_name_ptr );
- sl_init( &grp->DaemonsList );
- sl_set_compare( &grp->DaemonsList,
- G_daemon_recordcompare,
- G_daemon_keycompare );
+
+ if (stdskl_construct(&grp->DaemonsList, sizeof(int32), sizeof(daemon_members*), G_compare_proc_ids_by_conf) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ if (stdskl_construct(&grp->mboxes, sizeof(mailbox), 0, NULL) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
grp->changed = 0;
grp->num_members = 0;
- grp->num_local = 0;
- sl_insert( &GroupsList, grp );
- Num_groups++;
- GlobalStatus.num_groups = Num_groups;
+
/* Set a group id here, so that if the group isn't changed,
* everyone will have the right ID (because all must have same). */
memcpy( &grp->grp_id, &Temp_buf[num_bytes], sizeof(group_id) );
@@ -2110,6 +2108,13 @@
grp->grp_id.memb_id.time = Flip_int32( grp->grp_id.memb_id.time );
grp->grp_id.index = Flip_int32( grp->grp_id.index );
}
+
+ if (stdskl_insert(&GroupsList, &grp->GroupsListIt, &grp->name, &grp, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ Num_groups++;
+ GlobalStatus.num_groups = Num_groups;
}
num_bytes += sizeof(group_id);
@@ -2146,20 +2151,32 @@
Alarmp( SPLOG_DEBUG, GROUPS, "G_mess_to_groups: \t\twith memb_id (%s, %d)\n",
ip_string, dmn->memb_id.time );
Alarmp( SPLOG_DEBUG, GROUPS, "G_mess_to_groups: \t\twith %u members:\n", num_memb );
- sl_init( &dmn->MembersList );
- sl_set_compare( &dmn->MembersList, G_compare, G_compare );
- sl_insert( &grp->DaemonsList, dmn );
+
+ if (stdskl_construct(&dmn->MembersList, sizeof(member*), 0, G_compare_cstrptr) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ if (stdskl_insert(&grp->DaemonsList, &dmn->DaemonsListIt, &dmn->proc_id, &dmn, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
if( !grp->changed &&
!Memb_is_equal( dmn->memb_id, grp->grp_id.memb_id ) )
grp->changed = 1;
+
+ stdskl_end(&dmn->MembersList, &it);
+
/* creating members */
- for( j = 0; j < num_memb; ++j )
+ for( j = 0, stdskl_end(&dmn->MembersList, &it); j < num_memb; ++j, stdskl_it_next(&it))
{
mbr = new( MEMBER );
memcpy( mbr->name, &Temp_buf[num_bytes], MAX_GROUP_NAME );
Alarmp( SPLOG_DEBUG, GROUPS, "G_mess_to_groups: \t\t%s\n", mbr->name );
num_bytes += MAX_GROUP_NAME;
- sl_append( &dmn->MembersList, mbr );
+
+ if (stdskl_insert(&dmn->MembersList, &it, &mbr, NULL, STDTRUE) != 0) { /* NOTE: hint insert at end */
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
}
grp->num_members += num_memb;
}
@@ -2169,20 +2186,20 @@
int G_analize_groups( int num_groups, char target_groups[][MAX_GROUP_NAME], int target_sessions[] )
{
-static mailbox mbox[MAX_SESSIONS];
-static mailbox current[MAX_SESSIONS];
-static mailbox *current_ptr;
int num_mbox;
- int num_mbox_pre;
- int num_current;
group *grp;
char proc_name[MAX_PROC_NAME];
char private_name[MAX_PRIVATE_NAME+1];
- int found;
int ses;
int ret;
- int i, j, k;
-
+ int i;
+ stdskl mboxes;
+ stdit it;
+
+ if (stdskl_construct(&mboxes, sizeof(mailbox), 0, NULL) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
/* get the mbox */
num_mbox = 0;
for( i=0; i < num_groups; i++ )
@@ -2203,44 +2220,35 @@
/* we have no such session */
if( ses < 0 ) continue;
- current[0] = Sessions[ ses ].mbox;
- current_ptr = current;
- num_current = 1;
- }else{
+ if (stdskl_put(&mboxes, NULL, &Sessions[ ses ].mbox, NULL, STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ } else {
/* regular group */
grp = G_get_group( target_groups[i] );
if( grp == NULL ) continue;
if( Gstate == GOP || Gstate == GTRANS ) {
- current_ptr = grp->mbox;
- num_current = grp->num_local;
- }else {
- num_current = 0; /* fool compiler warnings */
+
+ if (stdskl_put_seq_n(&mboxes, NULL, stdskl_begin(&grp->mboxes, &it), stdskl_size(&grp->mboxes), STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ }
+
+ } else {
Alarmp( SPLOG_FATAL, GROUPS, "G_analize_groups: Gstate is %d\n", Gstate );
}
}
- num_mbox_pre = num_mbox;
- for( j=0; j < num_current; j++ )
- {
- found = 0;
- for( k=0; k < num_mbox_pre; k++ )
- {
- if( mbox[k] == current_ptr[j] )
- {
- found = 1;
- break;
- }
- }
- if( !found )
- {
- mbox[num_mbox] = current_ptr[j];
- num_mbox++;
- }
- }
}
/* convert mbox to sessions */
- for( i=0; i < num_mbox; i++ ) target_sessions[i] = Sess_get_session_index ( mbox[ i ] );
- return( num_mbox );
+ for (i = 0, stdskl_begin(&mboxes, &it); !stdskl_is_end(&mboxes, &it); ++i, stdskl_it_next(&it))
+ {
+ target_sessions[i] = Sess_get_session_index( *(mailbox*) stdskl_it_key(&it) );
+ }
+
+ stdskl_destruct(&mboxes); /* TODO: old code of array searching probably faster at least for small groups/memberships */
+
+ return i;
}
static void G_compute_group_mask( group *grp, char *func_name )
@@ -2248,18 +2256,17 @@
#if (SPREAD_PROTOCOL == 4)
int i;
int temp;
- struct skiplistnode *iter;
daemon_members *dmn;
proc p;
-
+ stdit it;
+
for(i=0; i<4; i++)
{
grp->grp_mask[i] = 0;
}
- for( iter = sl_getlist( &grp->DaemonsList ), dmn = (daemon_members *)iter->data;
- iter != NULL;
- dmn = (daemon_members *)sl_next( &grp->DaemonsList, &iter ))
- {
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
+ {
+ dmn = *(daemon_members**) stdskl_it_val(&it);
Conf_proc_by_id( dmn->proc_id, &p );
temp = 1;
for( i = 0; i < p.seg_index%32; i++ )
@@ -2402,24 +2409,24 @@
group *grp;
daemon_members *dmn;
member *mbr;
- struct skiplistnode *giter, *diter, *iter;
int i, j, k;
+ stdit git, dit, mit;
Alarmp( SPLOG_PRINT, GROUPS, "++++++++++++++++++++++\n" );
Alarmp( SPLOG_PRINT, GROUPS, "Num of groups: %d\n", Num_groups );
- giter = sl_getlist( &GroupsList );
- grp = (giter) ? (group *)giter->data : NULL;
- for( i = 0; grp != NULL ; i++, grp = sl_next( &GroupsList, &giter ) )
+
+ for (i = 0, stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); ++i, stdskl_it_next(&git))
{
+ grp = *(group**) stdskl_it_val(&git);
Alarmp( SPLOG_PRINT, GROUPS, "[%d] group %s with %d members:\n", i+1, grp->name, grp->num_members );
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( j = 0; dmn != NULL ; j++, dmn = sl_next( &grp->DaemonsList, &diter ) )
+
+ for (j = 0, stdskl_begin(&grp->DaemonsList, &dit); !stdskl_is_end(&grp->DaemonsList, &dit); ++j, stdskl_it_next(&dit))
{
- iter = sl_getlist( &dmn->MembersList );
- mbr = (iter) ? (member *)iter->data : NULL;
- for( k = 0; mbr != NULL ; k++, mbr = sl_next( &dmn->MembersList, &iter ) )
- {
+ dmn = *(daemon_members**) stdskl_it_val(&dit);
+
+ for (k = 0, stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); ++k, stdskl_it_next(&mit))
+ {
+ mbr = *(member**) stdskl_it_key(&mit);
Alarmp( SPLOG_PRINT, GROUPS, "\t[%d] %s\n", k+1, mbr->name );
}
}
@@ -2431,7 +2438,7 @@
{
group *grp = G_get_group( group_name );
if( grp == NULL ) return 0;
- return grp->num_local;
+ return stdskl_size(&grp->mboxes);
}
/* Add new members to my synced set. */
@@ -2497,17 +2504,18 @@
/* Eliminate the partitioned daemons of a group. Return true if we changed the
* group. */
-static int G_eliminate_partitioned_daemons( group *grp ) {
- struct skiplistnode *diter;
- daemon_members *dmn, *nextdaemon;
+static int G_eliminate_partitioned_daemons( group *grp )
+{
+ daemon_members *dmn;
int group_changed = 0;
int needed;
+ stdit it;
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL ; dmn = nextdaemon )
- {
- nextdaemon = sl_next( &grp->DaemonsList, &diter );
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); )
+ {
+ dmn = *(daemon_members**) stdskl_it_val(&it);
+ stdskl_it_next(&it); /* NOTE: advance here to protect against potential removal below */
+
needed = 0;
/* The first condition is sufficient, but we can optimize a bit this way. */
if( Gstate == GGT ) /* Called in G_handle_reg_memb after we got a cascading transitional */
@@ -2538,16 +2546,15 @@
/* This function is only called when we handle a cascading transitional membership.
* Gstate should be GGATHER, about to change to GGT */
-static int G_check_if_changed_by_cascade( group *grp ) {
- struct skiplistnode *diter;
- daemon_members *dmn, *nextdaemon;
+static int G_check_if_changed_by_cascade( group *grp )
+{
+ daemon_members *dmn;
int group_changed = 0;
+ stdit it;
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL ; dmn = nextdaemon )
- {
- nextdaemon = sl_next( &grp->DaemonsList, &diter );
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
+ {
+ dmn = *(daemon_members**) stdskl_it_val(&it);
if( Conf_id_in_conf( &Trans_memb, dmn->proc_id ) == -1 )
{
group_changed = 1;
@@ -2559,34 +2566,45 @@
static void G_remove_daemon( group *grp, daemon_members *dmn )
{
- grp->num_members -= dmn->MembersList.size;
- sl_destruct( &dmn->MembersList, dispose );
- sl_remove( &grp->DaemonsList, &dmn->proc_id, dispose );
+ stdit it;
+
+ grp->num_members -= stdskl_size(&dmn->MembersList);
+
+ for (stdskl_begin(&dmn->MembersList, &it); !stdskl_is_end(&dmn->MembersList, &it); stdskl_it_next(&it)) {
+ dispose(*(member**) stdskl_it_val(&it)); /* NOTE: this is only safe because we do destruct immediately after */
+ }
+
+ stdskl_destruct(&dmn->MembersList);
+ stdskl_erase(&grp->DaemonsList, &dmn->DaemonsListIt);
+ dispose(dmn);
}
/* Remove a group that is known to be empty. */
-static void G_remove_group( group *grp ) {
- assert( grp->DaemonsList.size == 0 );
- sl_destruct( &grp->DaemonsList, dispose );
- sl_remove( &GroupsList, grp->name, dispose );
- Num_groups--;
+static void G_remove_group( group *grp )
+{
+ assert( stdskl_empty(&grp->DaemonsList) );
+ stdskl_destruct(&grp->DaemonsList);
+ stdskl_destruct(&grp->mboxes);
+ stdskl_erase(&GroupsList, &grp->GroupsListIt);
+ dispose(grp);
+ Num_groups--;
GlobalStatus.num_groups = Num_groups;
}
/* All non-partitioned daemons get the membership ID component of the
* groups current group ID. */
-static void G_update_daemon_memb_ids( group *grp ) {
- struct skiplistnode *diter;
- daemon_members *dmn, *nextdaemon;
+static void G_update_daemon_memb_ids( group *grp )
+{
+ stdit it;
- diter = sl_getlist( &grp->DaemonsList );
- dmn = (diter) ? (daemon_members *)diter->data : NULL;
- for( ; dmn != NULL ; dmn = nextdaemon )
- {
- nextdaemon = sl_next( &grp->DaemonsList, &diter );
- if( Is_established_daemon( dmn ) )
+ for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
+ {
+ daemon_members *dmn = *(daemon_members**) stdskl_it_val(&it);
+
+ if( Is_established_daemon( dmn ) ) {
dmn->memb_id = grp->grp_id.memb_id;
- }
+ }
+ }
}
static void G_print_group_id( int priority, group_id g, char *func_name )
Modified: trunk/daemon/sess_body.h
===================================================================
--- trunk/daemon/sess_body.h 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/sess_body.h 2005-07-22 08:40:34 UTC (rev 251)
@@ -49,8 +49,10 @@
#include "arch.h"
#include "protocol.h"
#include "session.h"
-#include "skiplist.h"
+#include <stdutil/stdskl.h>
+#include <stdutil/stdarr.h>
+
#define MEMB_SESSION 0x00000001
#define OP_SESSION 0x00000010
#define PRE_AUTH_SESSION 0x00000100
@@ -70,25 +72,26 @@
/* All the information we need to maintain per group member is its private
* group name. */
typedef struct dummy_member {
- char name[MAX_GROUP_NAME];
+ char name[MAX_GROUP_NAME];
+ stdit MembersListIt;
} member;
typedef struct dummy_daemon_members {
int32 proc_id;
- membership_id memb_id; /* Used for vs_set sorting.
- * == unknown_memb_id means partitioned. */
- Skiplist MembersList;
+ membership_id memb_id; /* Used for vs_set sorting; unknown_memb_id means partitioned. */
+ stdskl MembersList; /* (member*) -> nil */
+ stdit DaemonsListIt;
} daemon_members;
typedef struct dummy_group {
char name[MAX_GROUP_NAME];
group_id grp_id;
int changed;
- int num_members;
- Skiplist DaemonsList;
- int num_local;
- mailbox mbox[MAX_SESSIONS];
+ int num_members; /* sums over all daemons in DaemonsList */
+ stdskl DaemonsList; /* (int32) -> (daemon_members*) */
+ stdskl mboxes; /* (mailbox) -> nil: mailboxes of local clients */
route_mask grp_mask;
+ stdit GroupsListIt;
} group;
#undef ext
Deleted: trunk/daemon/skiplist.c
===================================================================
--- trunk/daemon/skiplist.c 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/skiplist.c 2005-07-22 08:40:34 UTC (rev 251)
@@ -1,569 +0,0 @@
-/*
- * The Spread Toolkit.
- *
- * The contents of this file are subject to the Spread Open-Source
- * License, Version 1.0 (the ``License''); you may not use
- * this file except in compliance with the License. You may obtain a
- * copy of the License at:
- *
- * http://www.spread.org/license/
- *
- * or in the file ``license.txt'' found in this distribution.
- *
- * Software distributed under the License is distributed on an AS IS basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Creators of Spread are:
- * Yair Amir, Michal Miskin-Amir, Jonathan Stanton.
- *
- * Copyright (C) 1993-2004 Spread Concepts LLC <spread at spreadconcepts.com>
- *
- * All Rights Reserved.
- *
- * Major Contributor(s):
- * ---------------
- * Cristina Nita-Rotaru crisn at cs.purdue.edu - group communication security.
- * Theo Schlossnagle jesus at omniti.com - Perl, skiplists, autoconf.
- * Dan Schoenblum dansch at cnds.jhu.edu - Java interface.
- * John Schultz jschultz at cnds.jhu.edu - contribution to process group membership.
- *
- */
-
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <assert.h>
-
-#include "skiplist_p.h"
-#include "alarm.h"
-
-#ifndef MIN
-#define MIN(a,b) ((a<b)?(a):(b))
-#endif
-
-static int get_b_rand() {
- static int ph=32; /* More bits than we will ever use */
- static unsigned long randseq;
- if(ph > 31) { /* Num bits in return of lrand48() */
- ph=0;
- randseq = get_rand();
- }
- ph++;
- return ((randseq & (1 << (ph-1))) >> (ph-1));
-}
-
-void sli_init(Skiplist *sl) {
- sl->compare = (SkiplistComparator)NULL;
- sl->comparek = (SkiplistComparator)NULL;
- sl->height=0;
- sl->preheight=0;
- sl->size=0;
- sl->top = NULL;
- sl->bottom = NULL;
- sl->index = NULL;
-}
-
-static int indexing_comp(const void *a, const void *b)
-{
- void *ak = (void *) (((Skiplist *) a)->compare);
- void *bk = (void *) (((Skiplist *) b)->compare);
- assert(a);
- assert(b);
- if(ak<bk)
- return -1;
- if(ak>bk)
- return 1;
- return 0;
-}
-static int indexing_compk(const void *ak, const void *b)
-{
- void *bk = (void *) (((Skiplist *) b)->compare);
- assert(b);
- if(ak<bk)
- return -1;
- if(ak>bk)
- return 1;
- return 0;
-}
-
-void sl_init(Skiplist *sl) {
- sli_init(sl);
- sl->index = (Skiplist *)malloc(sizeof(Skiplist));
- sli_init(sl->index);
- sl_set_compare(sl->index, indexing_comp, indexing_compk);
-}
-
-void sl_set_compare(Skiplist *sl,
- SkiplistComparator comp,
- SkiplistComparator compk) {
- if(sl->compare && sl->comparek) {
- sl_add_index(sl, comp, compk);
- } else {
- sl->compare = comp;
- sl->comparek = compk;
- }
-}
-
-void sl_add_index(Skiplist *sl,
- SkiplistComparator comp,
- SkiplistComparator compk) {
- struct skiplistnode *m;
- Skiplist *ni;
- int icount=0;
- Alarm(SKIPLIST, "Adding index to %p\n", sl);
- sl_find(sl->index, (void *)comp, &m);
- if(m) return; /* Index already there! */
- ni = (Skiplist *)malloc(sizeof(Skiplist));
- sli_init(ni);
- sl_set_compare(ni, comp, compk);
- /* Build the new index... This can be expensive! */
- m = sl_insert(sl->index, ni);
- while(m->prev) m=m->prev, icount++;
- for(m=sl_getlist(sl); m; sl_next(sl, &m)) {
- int j=icount-1;
- struct skiplistnode *nsln;
- nsln = sl_insert(ni, m->data);
- /* skip from main index down list */
- while(j>0) m=m->nextindex, j--;
- /* insert this node in the indexlist after m */
- nsln->nextindex = m->nextindex;
- if(m->nextindex) m->nextindex->previndex = nsln;
- nsln->previndex = m;
- m->nextindex = nsln;
- }
-}
-
-struct skiplistnode *sl_getlist(Skiplist *sl) {
- if(!sl->bottom) return NULL;
- return sl->bottom->next;
-}
-
-void *sl_find(Skiplist *sl,
- void *data,
- struct skiplistnode **iter) {
- void *ret;
- if(!sl->compare) return 0;
- ret = sl_find_compare(sl, data, iter, sl->compare);
- return ret;
-}
-void *sl_find_compare(Skiplist *sli,
- void *data,
- struct skiplistnode **iter,
- SkiplistComparator comp) {
- struct skiplistnode *m = NULL;
- Skiplist *sl;
- if(comp==sli->compare || !sli->index) {
- sl = sli;
- } else {
- sl_find(sli->index, (void *)comp, &m);
- assert(m);
- sl=m->data;
- }
- sli_find_compare(sl, data, iter, sl->comparek);
- return (*iter)?((*iter)->data):(*iter);
-}
-int sli_find_compare(Skiplist *sl,
- void *data,
- struct skiplistnode **ret,
- SkiplistComparator comp) {
- struct skiplistnode *m = NULL;
- int count=0;
- m = sl->top;
- while(m) {
- int compared = 1;
- if(m->next) compared=comp(data, m->next->data);
- if(compared == 0) {
-#ifdef SL_DEBUG
- Alarm(SKIPLIST, "Looking -- found in %d steps\n", count);
-#endif
- m=m->next;
- while(m->down) m=m->down;
- *ret = m;
- return count;
- }
- if((m->next == NULL) || (compared<0))
- m = m->down, count++;
- else
- m = m->next, count++;
- }
-#ifdef SL_DEBUG
- Alarm(SKIPLIST, "Looking -- not found in %d steps\n", count);
-#endif
- *ret = NULL;
- return count;
-}
-void *sl_next(Skiplist *sl, struct skiplistnode **iter) {
- if(!*iter) return NULL;
- *iter = (*iter)->next;
- return (*iter)?((*iter)->data):NULL;
-}
-void *sl_previous(Skiplist *sl, struct skiplistnode **iter) {
- if(!*iter) return NULL;
- *iter = (*iter)->prev;
- return (*iter)?((*iter)->data):NULL;
-}
-struct skiplistnode *sl_insert(Skiplist *sl,
- void *data) {
- if(!sl->compare) return 0;
- return sl_insert_compare(sl, data, sl->compare);
-}
-
-struct skiplistnode *sl_insert_compare(Skiplist *sl,
- void *data,
- SkiplistComparator comp) {
- struct skiplistnode *m, *p, *tmp, *ret, **stack;
- int nh=1, ch, stacki;
- ret = NULL;
-/*sl_print_struct(sl, "BI: ");*/
- if(!sl->top) {
- sl->height = 1;
- sl->topend = sl->bottomend = sl->top = sl->bottom =
- (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
- assert(sl->top);
- sl->top->next = sl->top->data = sl->top->prev =
- sl->top->up = sl->top->down =
- sl->top->nextindex = sl->top->previndex = NULL;
- sl->top->sl = sl;
- }
- if(sl->preheight) {
- while(nh < sl->preheight && get_b_rand()) nh++;
- } else {
- while(nh <= sl->height && get_b_rand()) nh++;
- }
- /* Now we have the new height at which we wish to insert our new node */
- /* Let us make sure that our tree is a least that tall (grow if necessary)*/
- for(;sl->height<nh;sl->height++) {
- sl->top->up =
- (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
- assert(sl->top->up);
- sl->top->up->down = sl->top;
- sl->top = sl->topend = sl->top->up;
- sl->top->prev = sl->top->next = sl->top->nextindex =
- sl->top->previndex = sl->top->up = NULL;
- sl->top->data = NULL;
- sl->top->sl = sl;
- }
- ch = sl->height;
- /* Find the node (or node after which we would insert) */
- /* Keep a stack to pop back through for insertion */
- m = sl->top;
- stack = (struct skiplistnode **)malloc(sizeof(struct skiplistnode *)*(nh));
- stacki=0;
- while(m) {
- int compared=-1;
- if(m->next) compared=comp(data, m->next->data);
- if(compared == 0) {
- free(stack);
- return 0;
- }
- if((m->next == NULL) || (compared<0)) {
- /* FIXME: This if ch<=nh test looks unnecessary. ch==nh at beginning of while(m)
- */
- if(ch<=nh) {
- /* push on stack */
- stack[stacki++] = m;
- }
- m = m->down;
- ch--;
- } else {
- m = m->next;
- }
- }
- /* Pop the stack and insert nodes */
- p = tmp = NULL;
- for(;stacki>0;stacki--) {
- m = stack[stacki-1];
- tmp = (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
- tmp->next = m->next;
- if(m->next) m->next->prev=tmp;
- tmp->prev = m;
- tmp->up = NULL;
- tmp->nextindex = tmp->previndex = NULL;
- tmp->down = p;
- if(p) p->up=tmp;
- tmp->data = data;
- tmp->sl = sl;
- m->next = tmp;
- /* This sets ret to the bottom-most node we are inserting */
- if(!p)
- {
- ret=tmp;
- sl->size++;
- }
- p = tmp;
- }
- free(stack);
- if(tmp && (tmp->prev == sl->topend)) {
- /* The last element on the top row is the new inserted one */
- sl->topend = tmp;
- }
- if(ret && (ret->prev == sl->bottomend)) {
- /* The last element on the bottom row is the new inserted one */
- sl->bottomend = ret;
- }
- if(sl->index != NULL) {
- /* this is a external insertion, we must insert into each index as well */
- struct skiplistnode *p, *ni, *li;
- li=ret;
- for(p = sl_getlist(sl->index); p; sl_next(sl->index, &p)) {
- ni = sl_insert((Skiplist *)p->data, ret->data);
- assert(ni);
- Alarm(SKIPLIST, "Adding %p to index %p\n", ret->data, p->data);
- li->nextindex = ni;
- ni->previndex = li;
- li = ni;
- }
- }
- /* JRS: move size increment above to where node is inserted
- else {
- sl->size++;
- }
- */
-/*sl_print_struct(sl, "AI: ");*/
- return ret;
-}
-struct skiplistnode *sl_append(Skiplist *sl, void *data) {
- return sl_insert(sl, data);
-}
-#if 0
-struct skiplistnode *sl_append(Skiplist *sl, void *data) {
- int nh=1, ch, compared;
- struct skiplistnode *lastnode, *nodeago;
- if(sl->bottomend != sl->bottom) {
- compared=sl->compare(data, sl->bottomend->prev->data);
- /* If it doesn't belong at the end, then fail */
- if(compared<=0) return NULL;
- }
- if(sl->preheight) {
- while(nh < sl->preheight && get_b_rand()) nh++;
- } else {
- while(nh <= sl->height && get_b_rand()) nh++;
- }
- /* Now we have the new hieght at which we wish to insert our new node */
- /* Let us make sure that our tree is a least that tall (grow if necessary)*/
- lastnode = sl->bottomend;
- nodeago = NULL;
-
- if(!lastnode) return sl_insert(sl, data);
-
- for(;sl->height<nh;sl->height++) {
- assert(sl->top);
- sl->top->up =
- (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
- sl->top->up->down = sl->top;
- sl->top = sl->topend = sl->top->up;
- sl->top->prev = sl->top->next = sl->top->nextindex =
- sl->top->previndex = NULL;
- sl->top->data = NULL;
- sl->top->sl = sl;
- }
- ch = sl->height;
- while(nh) {
- struct skiplistnode *anode;
- anode =
- (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
- anode->next = lastnode;
- anode->prev = lastnode->prev;
- anode->up = NULL;
- anode->down = nodeago;
- /* If this the bottom, we are appending, so bottomend should change */
- if(!nodeago) sl->bottomend = anode;
- if(lastnode->prev) {
- if(lastnode == sl->bottom)
- sl->bottom = anode;
- else if (lastnode == sl->top)
- sl->top = anode;
- }
- nodeago = anode;
- lastnode = lastnode->up;
- nh--;
- }
- sl->size++;
- return(nodeago);
-}
-#endif
-Skiplist *sl_concat(Skiplist *sl1, Skiplist *sl2) {
- /* Check integrity! */
- Skiplist temp;
- struct skiplistnode *b2;
- if(sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
- sl_remove_all(sl1, free);
- temp = *sl1;
- *sl1 = *sl2;
- *sl2 = temp;
- /* swap them so that sl2 can be freed normally upon return. */
- return sl1;
- }
- if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
- sl_remove_all(sl2, free);
- return sl1;
- }
- b2 = sl_getlist(sl2);
- while(b2) {
- sl_insert(sl1, b2->data);
- sl_next(sl2, &b2);
- }
- sl_remove_all(sl2, NULL);
- return sl1;
-}
-#if 0
-Skiplist *sl_concat(Skiplist *sl1, Skiplist *sl2) {
- /* Check integrity! */
- int compared, eheight;
- Skiplist temp;
- struct skiplistnode *lbottom, *lbottomend, *b1, *e1, *b2, *e2;
- if(sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
- sl_remove_all(sl1, free);
- temp = *sl1;
- *sl1 = *sl2;
- *sl2 = temp;
- /* swap them so that sl2 can be freed normally upon return. */
- return sl1;
- }
- if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
- sl_remove_all(sl2, free);
- return sl1;
- }
- compared = sl1->compare(sl1->bottomend->prev->data, sl2->bottom->data);
- /* If it doesn't belong at the end, then fail */
- if(compared<=0) return NULL;
-
- /* OK now append sl2 onto sl1 */
- lbottom = lbottomend = NULL;
- eheight = MIN(sl1->height, sl2->height);
- b1 = sl1->bottom; e1 = sl1->bottomend;
- b2 = sl2->bottom; e2 = sl2->bottomend;
- while(eheight) {
- e1->prev->next = b2;
- b2->prev = e1->prev->next;
- e2->prev->next = e1;
- e1->prev = e2->prev;
- e2->prev = NULL;
- b2 = e2;
- b1->down = lbottom;
- e1->down = lbottomend;
- if(lbottom) lbottom->up = b1;
- if(lbottomend) lbottomend->up = e1;
-
- lbottom = b1;
- lbottomend = e1;
- }
- /* Take the top of the longer one (if it is sl2) and make it sl1's */
- if(sl2->height > sl1->height) {
- b1->up = b2->up;
- e1->up = e2->up;
- b1->up->down = b1;
- e1->up->down = e1;
- sl1->height = sl2->height;
- sl1->top = sl2->top;
- sl1->topend = sl2->topend;
- }
-
- /* move the top pointer to here if it isn't there already */
- sl2->top = sl2->topend = b2;
- sl2->top->up = NULL; /* If it isn't already */
- sl1->size += sl2->size;
- sl_remove_all(sl2, free);
- return sl1;
-}
-#endif
-int sl_remove(Skiplist *sl,
- void *data, FreeFunc myfree) {
- if(!sl->compare) return 0;
- return sl_remove_compare(sl, data, myfree, sl->comparek);
-}
-void sl_print_struct(Skiplist *sl, char *prefix, char *(*printdata)(void *)) {
- struct skiplistnode *p, *q;
- Alarm(SKIPLIST, "Skiplist Structure (height: %d)\n", sl->height);
- p = sl->bottom;
- while(p) {
- q = p;
- Alarm(SKIPLIST, prefix);
- while(q) {
- Alarm(SKIPLIST, "%6s ", printdata(q->data));
- q=q->up;
- }
- Alarm(SKIPLIST, "\n");
- p=p->next;
- }
-}
-int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree) {
- struct skiplistnode *p;
- if(!m) return 0;
- if(m->nextindex) sli_remove(m->nextindex->sl, m->nextindex, NULL);
- else sl->size--;
- /*sl_print_struct(sl, "BR:");*/
- while(m->up) m=m->up;
- while(m) {
- p=m;
- p->prev->next = p->next; /* take me out of the list */
- if(p->next) p->next->prev = p->prev; /* take me out of the list */
- m=m->down;
- /* This only frees the actual data in the bottom one */
- if(!m && myfree && p->data) myfree(p->data);
- free(p);
- }
- while(sl->top && sl->top->next == NULL) {
- /* While the row is empty and we are not on the bottom row */
- p = sl->top;
- sl->top = sl->top->down; /* Move top down one */
- if(sl->top) sl->top->up = NULL; /* Make it think its the top */
- free(p);
- sl->height--;
- }
- if(!sl->top) sl->bottom = NULL;
- assert(sl->height>=0);
- /*sl_print_struct(sl, "AR: ");*/
- return sl->height;
-}
-int sl_remove_compare(Skiplist *sli,
- void *data,
- FreeFunc myfree, SkiplistComparator comp) {
- struct skiplistnode *m;
- Skiplist *sl;
- if(comp==sli->comparek || !sli->index) {
- sl = sli;
- } else {
- sl_find(sli->index, (void *)comp, &m);
- assert(m);
- sl=m->data;
- }
- sli_find_compare(sl, data, &m, comp);
- if (!m) return( 0 );
- while(m->previndex) m=m->previndex;
- return sli_remove(sl, m, myfree);
-}
-void sl_remove_all(Skiplist *sl, FreeFunc myfree) {
- /* This must remove even the place holder nodes (bottom though top)
- because we specify in the API that one can free the Skiplist after
- making this call without memory leaks */
- struct skiplistnode *m, *p, *u;
- m=sl->bottom;
- while(m) {
- p = m->next;
- if(myfree && p && p->data) myfree(p->data);
- while(m) {
- u = m->up;
- free(m);
- m=u;
- }
- m = p;
- }
- sl->top = sl->bottom = NULL;
- sl->height = 0;
- sl->size = 0;
-}
-void sli_destruct_free(Skiplist *sl, FreeFunc myfree) {
- sl_remove_all(sl, NULL);
- free(sl);
-}
-void sl_destruct(Skiplist *sl, FreeFunc myfree) {
- if(sl->index) {
- sl_remove_all(sl->index, (FreeFunc)sli_destruct_free);
- free(sl->index);
- }
- sl_remove_all(sl, myfree);
-}
-
Deleted: trunk/daemon/skiplist.h
===================================================================
--- trunk/daemon/skiplist.h 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/skiplist.h 2005-07-22 08:40:34 UTC (rev 251)
@@ -1,123 +0,0 @@
-/*
- * The Spread Toolkit.
- *
- * The contents of this file are subject to the Spread Open-Source
- * License, Version 1.0 (the ``License''); you may not use
- * this file except in compliance with the License. You may obtain a
- * copy of the License at:
- *
- * http://www.spread.org/license/
- *
- * or in the file ``license.txt'' found in this distribution.
- *
- * Software distributed under the License is distributed on an AS IS basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Creators of Spread are:
- * Yair Amir, Michal Miskin-Amir, Jonathan Stanton.
- *
- * Copyright (C) 1993-2004 Spread Concepts LLC <spread at spreadconcepts.com>
- *
- * All Rights Reserved.
- *
- * Major Contributor(s):
- * ---------------
- * Cristina Nita-Rotaru crisn at cs.purdue.edu - group communication security.
- * Theo Schlossnagle jesus at omniti.com - Perl, skiplists, autoconf.
- * Dan Schoenblum dansch at cnds.jhu.edu - Java interface.
- * John Schultz jschultz at cnds.jhu.edu - contribution to process group membership.
- *
- */
-
-
-#ifndef _SKIPLIST_H
-#define _SKIPLIST_H
-
-/* This is a skiplist implementation to be used for abstract structures
- within the Spread multicast and group communication toolkit
-
- This portion written by -- Theo Schlossnagle <jesus at cnds.jhu.eu>
-*/
-
-/* This is the function type that must be implemented per object type
- that is used in a skiplist for comparisons to maintain order */
-typedef int (*SkiplistComparator)(void *, void *);
-typedef void (*FreeFunc)(void *);
-
-struct skiplistnode {
- void *data;
- void *private_use[7];
-};
-
-typedef struct {
- SkiplistComparator compare;
- SkiplistComparator comparek;
- const int height;
- int preheight;
- const int size;
- void *private_use[5];
-} Skiplist;
-
-/* set up the internals for this skiplist */
-void sl_init(Skiplist *sl);
-
-/* set a compare function to be used by the skiplist */
-/* Pass a skiplist in, a comparator for (record, record) and a
- comparator for (key, record) in the order */
-
-void sl_set_compare(Skiplist *, SkiplistComparator,
- SkiplistComparator);
-void sl_add_index(Skiplist *sl, SkiplistComparator,
- SkiplistComparator);
-
-/* Returns a pointer to the first node in the list
- DO NOT EDIT THIS LIST! It is maintained internally and should not
- be toyed with */
-struct skiplistnode *sl_getlist(Skiplist *sl);
-
-/* Find returns NULL on failure and a point to the data on success */
-/* sl is the skiplist in which you are looking
- data the key you are looking for
- iter is an iterator that is filled out with the found node
- it is then passed into next and previous to iterate through the list */
-void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter);
-void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter,
- SkiplistComparator comp);
-void *sl_next(Skiplist *sl, struct skiplistnode **iter);
-void *sl_previous(Skiplist *sl, struct skiplistnode **iter);
-
-/* Insert returns 0 on failure and a pointer to the skiplistnode on success */
-/* sl is the skiplist in which you are inserting
- data is a record (not necessarily the key) */
-struct skiplistnode *sl_insert(Skiplist *sl, void *data);
-
-/* Append and concatenate are special.. They are used to effeciently create
- a skiplist from presorted data. You MUST be sure that there are not
- multiple indices and that the comparator is the same.
- Both return NULL on error and the skiplistnode inserted and the new
- Skiplist on success, respectively */
-struct skiplistnode *sl_append(Skiplist *sl, void *data);
-/* The return value will match dest on success and appending will be empty and
- thus freeable without leakage */
-Skiplist *sl_concat(Skiplist *dest, Skiplist *appending);
-
-/* Remove returns 0 on failure and the current tree height on success */
-/* sl is the skiplist from which you are removing
- data is the key for the node you wish to remove */
-int sl_remove(Skiplist *sl, void *data, FreeFunc myfree);
-int sl_remove_compare(Skiplist *sl, void *data, FreeFunc myfree,
- SkiplistComparator comp);
-
-/* removes all nodes in a skiplist, the list can still be used */
-/* sl is the skiplist from which you are removing */
-void sl_remove_all(Skiplist *sl, FreeFunc myfree);
-
-/* removes all nodes in a skiplist, you can free the skiplist itself
- without memory leaks after calling this function. After calling
- this function, the list cannot be safely used, it must be freed */
-void sl_destruct(Skiplist *sl, FreeFunc myfree);
-
-
-#endif
Deleted: trunk/daemon/skiplist_p.h
===================================================================
--- trunk/daemon/skiplist_p.h 2005-07-20 22:03:50 UTC (rev 250)
+++ trunk/daemon/skiplist_p.h 2005-07-22 08:40:34 UTC (rev 251)
@@ -1,103 +0,0 @@
-/*
- * The Spread Toolkit.
- *
- * The contents of this file are subject to the Spread Open-Source
- * License, Version 1.0 (the ``License''); you may not use
- * this file except in compliance with the License. You may obtain a
- * copy of the License at:
- *
- * http://www.spread.org/license/
- *
- * or in the file ``license.txt'' found in this distribution.
- *
- * Software distributed under the License is distributed on an AS IS basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Creators of Spread are:
- * Yair Amir, Michal Miskin-Amir, Jonathan Stanton.
- *
- * Copyright (C) 1993-2004 Spread Concepts LLC <spread at spreadconcepts.com>
- *
- * All Rights Reserved.
- *
- * Major Contributor(s):
- * ---------------
- * Cristina Nita-Rotaru crisn at cs.purdue.edu - group communication security.
- * Theo Schlossnagle jesus at omniti.com - Perl, skiplists, autoconf.
- * Dan Schoenblum dansch at cnds.jhu.edu - Java interface.
- * John Schultz jschultz at cnds.jhu.edu - contribution to process group membership.
- *
- */
-
-
-#ifndef _SKIPLIST_P_H
-#define _SKIPLIST_P_H
-
-/* This is a skiplist implementation to be used for abstract structures
- within the Spread multicast and group communication toolkit
-
- This portion written by -- Theo Schlossnagle <jesus at cnds.jhu.eu>
-*/
-
-/* This is the function type that must be implemented per object type
- that is used in a skiplist for comparisons to maintain order */
-typedef int (*SkiplistComparator)(void *, void *);
-typedef void (*FreeFunc)(void *);
-
-struct skiplistnode;
-
-typedef struct _iskiplist {
- SkiplistComparator compare;
- SkiplistComparator comparek;
- int height;
- int preheight;
- int size;
- struct skiplistnode *top;
- struct skiplistnode *bottom;
- /* These two are needed for appending */
- struct skiplistnode *topend;
- struct skiplistnode *bottomend;
- struct _iskiplist *index;
-} Skiplist;
-
-struct skiplistnode {
- void *data;
- struct skiplistnode *next;
- struct skiplistnode *prev;
- struct skiplistnode *down;
- struct skiplistnode *up;
- struct skiplistnode *previndex;
- struct skiplistnode *nextindex;
- Skiplist *sl;
-};
-
-
-void sl_init(Skiplist *sl);
-void sl_set_compare(Skiplist *sl, SkiplistComparator,
- SkiplistComparator);
-void sl_add_index(Skiplist *sl, SkiplistComparator,
- SkiplistComparator);
-struct skiplistnode *sl_getlist(Skiplist *sl);
-void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter,
- SkiplistComparator func);
-void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter);
-void *sl_next(Skiplist *sl, struct skiplistnode **);
-void *sl_previous(Skiplist *sl, struct skiplistnode **);
-
-struct skiplistnode *sl_insert_compare(Skiplist *sl,
- void *data, SkiplistComparator comp);
-struct skiplistnode *sl_insert(Skiplist *sl, void *data);
-int sl_remove_compare(Skiplist *sl, void *data,
- FreeFunc myfree, SkiplistComparator comp);
-int sl_remove(Skiplist *sl, void *data, FreeFunc myfree);
-int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree);
-void sl_remove_all(Skiplist *sl, FreeFunc myfree);
-
-int sli_find_compare(Skiplist *sl,
- void *data,
- struct skiplistnode **ret,
- SkiplistComparator comp);
-
-#endif
More information about the Spread-cvs
mailing list