PERFORCE change 141985 for review

[Vincenzo Iozzo]

http://perforce.freebsd.org/chv.cgi?CH=141985

Change 141985 by snagg at snagg_macosx on 2008/05/21 20:10:25

	Modify the sort and search function in order to use bsearch and
	qsort instead of bubblesort and my "home-made" binary search

Affected files ...

.. //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_ioctl.h#11 edit
.. //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#13 edit

Differences ...

==== //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_ioctl.h#11 (text) ====

@@ -63,6 +63,7 @@
 #define	AUDITPIPE_PRESELECT_MODE_LOCAL	2	/* Local audit trail. */
 #define	AUDITPIPE_PRESELECT_MODE_EVENT	3 /* Events-pid based audit trail */
 #define AUDITPIPE_PRESELECT_MODE_PID	4 /*Pid based audit trail*/
+
 /*
  * Ioctls to read and control the behavior of individual audit pipe devices.
  */

==== //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#13 (text) ====

@@ -230,61 +230,21 @@
 /*
  * The event array is sorted in ascending order, needed for the binary search
  */
-static void audit_pipe_sort_preselect_event(struct audit_pipe_preselect_event *app_auevents, 
-	int app_event_len) 
+static int 
+audit_pipe_compare_preselect_event(const void *a, const void *b)
 {
-	int sorted;
-	int i;
-	struct audit_pipe_preselect_event *entry;
-	
-	sorted = 0;
-	entry = NULL;
-	while(!sorted) {
-		sorted = 1;
-		for(i = 1; i < app_event_len; i++) {
-			if((app_auevents + i - 1)->app_event > (app_auevents + i)->app_event) {
-				*entry = *(app_auevents + i);
-				*(app_auevents + i) = *(app_auevents + i -1);
-				*(app_auevents + i -1) = *entry;
-				sorted = 0;
-			}
-		}
-	}
-}	
+	const struct audit_pipe_preselect_event *entrya = a;
+	const struct audit_pipe_preselect_event *entryb = b;
+
+	if(entrya->app_event > entryb->app_event)
+		return 1;
+	else if (entrya->app_event < entryb->app_event)
+		return -1;
+	else
+		return 0;
+}
+
 
-/*
- * This is a basic implementation of the binary seach algorithm
- */
-static struct audit_pipe_preselect_event 
-	*audit_pipe_find_preselect_event(struct audit_pipe_preselect_event *app_auevents, 
-	int app_event_len, int app_event, int app_flag) 
-{
-	int bottom; 
-	int top;
-	int curr;
-	
-	bottom = (app_auevents)->app_event;
-	top = (app_auevents + app_event_len -1)->app_event;
-	curr = 0;
-	
-	while(bottom <= top) {
-		curr = (bottom + top)/2;
-		if((app_auevents + curr)->app_event > app_event)
-			top = curr -1;
-		else if((app_auevents + curr)->app_event < app_event)
-			bottom = curr +1;
-		else {
-			if((app_auevents+curr)->app_flag == app_flag)
-				return (app_auevents + curr);
-			else if( app_flag == -1)
-				return (app_auevents + curr);
-			else	
-				return (NULL);
-		}
-	}
-	
-	return (NULL);
-}	
 			
 /*
  * Find an audit pipe preselection specification for an event and flag, if any.
@@ -294,21 +254,32 @@
 	pid_t app_pid, int event_flag)
 {
 	struct audit_pipe_preselect *app;
+	struct audit_pipe_preselect_event *event;
+	struct audit_pipe_preselect_event *ev_a;
+	
+	ev_a = malloc(sizeof(struct audit_pipe_preselect_event), M_AUDIT_PIPE_PRESELECT_EVENT, M_WAITOK);
+	ev_a->app_event = app_event;
+	ev_a->app_flag = event_flag;
 	
 	mtx_assert(&audit_pipe_mtx, MA_OWNED);
 	
 	TAILQ_FOREACH(app, &ap->ap_preselect_list, app_list) {
 		if(app->app_pid == app_pid) {
-			if(app_event == -1) /* Just return the entry for a given pid*/
-				return (app);
-			else {
-				if(audit_pipe_find_preselect_event(app->app_auevents, 
-					app->app_event_len, app_event, event_flag) != NULL)
-						return (app);
+			if(app_event != -1)  { /* Just skip if we are interested only in the pid*/
+				event = bsearch(ev_a, (app->app_auevents), app->app_event_len,
+						sizeof(struct audit_pipe_preselect_event), 
+						audit_pipe_compare_preselect_event);
+				if(event != NULL) {
+					if(event_flag != -1)
+						 if (event->app_flag != event_flag)
+							app = NULL;
+				} else
+					app = NULL;
 			}
 		}
 	}
-	return (NULL);
+	free(ev_a, M_AUDIT_PIPE_PRESELECT_EVENT);
+	return (app);
 }
 
 /*
@@ -403,7 +374,7 @@
 			(app->app_auevents + i)->app_event = (events + i)->app_event;
 			(app->app_auevents + i)->app_flag  = (events + i)->app_flag;
 		}
-		audit_pipe_sort_preselect_event(app->app_auevents, app->app_event_len);
+		qsort((app->app_auevents), app->app_event_len, sizeof(struct audit_pipe_preselect_event), audit_pipe_compare_preselect_event);
 	} else {	
 		app = app_new;
 		app_new = NULL;
@@ -413,7 +384,7 @@
 			(app->app_auevents + i)->app_event = (events + i)->app_event;
 			(app->app_auevents + i)->app_flag  = (events + i)->app_flag;
 		}
-		audit_pipe_sort_preselect_event(app->app_auevents, app->app_event_len);
+		qsort((app->app_auevents), app->app_event_len, sizeof(struct audit_pipe_preselect_event), audit_pipe_compare_preselect_event);
 		TAILQ_INSERT_TAIL(&ap->ap_preselect_list, app, app_list);
 	}