r644@blue (orig r492): slug | 2006-05-15 23:25:56 +0100

 New unencumbered array code.

diff --git a/lib/array.c b/lib/array.c
index 450084fd0e2ad58487218e49b5ef0e5399b32130..b427fc9d35d98b62a7d0e9226328e9733c231898 100644 (file)
--- a/lib/array.c
+++ b/lib/array.c
@@ -1,96 +1,81 @@
 /*
+  unencumbered array.c
+  dynamic UNORDERED array (yes this got me...)
 
-@GPL
-
-Operservice 2 - array.c
-Arrays are used all over in O2. This .c supplies some functions for handling
-them.
-(C) Michael Meier 2000-2001 - released under GPL
------------------------------------------------------------------------------
-This program is free software; you can redistribute it and/or
-modify it under the terms of the GNU General Public License
-as published by the Free Software Foundation; either version 2
-of the License, or (at your option) any later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
-------------------------------------------------------------------------------
+  will grow by allocchunksize (by default 100) when full and
+  new space is requested.
+
+  will shrink by freechunksize (by default 150) if that many
+  items are not occupied at the end.
+
+  clean written from the function prototypes.
 */
 
 #include <stdio.h>
 #include <stdlib.h>
-#include "array.h"
+#include <string.h>
 #include "../core/error.h"
 
-#ifndef ARLIM1
-#define ARLIM1 100     /* If new memory is needed for an array, this many */
-                       /* records will be allocated. */
-#endif
-#ifndef ARLIM2
-#define ARLIM2 150     /* If more than this number of records are free in an */
-                       /* array, memory is freed. */
-#endif
-
-void array_init(array *a, unsigned int memberlen) {
-  a->cursi=0;
-  a->maxsi=0;
-  a->memberlen=memberlen;
-  a->content=NULL;
-  a->arlim1=ARLIM1;
-  a->arlim2=ARLIM2;
-}
+#include "array.h"
+
+void array_init(array *a, unsigned int itemsize) {
+  a->content = NULL;
+  a->cursi = 0; /* count */
 
-void array_setlim1(array *a, unsigned int lim) {
-  a->arlim1=lim;
+  a->itemsize = itemsize;
+  a->capacity = 0;
+
+  /* allochunksize MUST be <= freechunksize */
+  a->allocchunksize = 100;
+  a->freechunksize = 150;
 }
 
-void array_setlim2(array *a, unsigned int lim) {
-  a->arlim2=lim;
+/* should be called free_and_reinit really */
+void array_free(array *a) {
+  free(a->content);
+
+  array_init(a, a->itemsize);
 }
 
 int array_getfreeslot(array *a) {
-  if ((a->cursi+1)>=a->maxsi) {
-    /* Reallocation needed */
-    a->maxsi+=a->arlim1;
-    a->content=realloc(a->content,a->maxsi*a->memberlen);
-    if (a->content==NULL) {
-      Error("array",ERR_FATAL,"Couldn't allocate memory for growing array");
-      exit(1);
+  if(a->cursi + 1 >= a->capacity) {
+    a->capacity += a->allocchunksize;
+
+    /* we can be evil and use the same pointer as we're gonna exit if we fail */
+    a->content = realloc(a->content, a->capacity * a->itemsize);
+
+    if(!a->content) {
+       Error("array", ERR_FATAL, "Array resize failed.");
+       exit(1);
     }
   }
-  a->cursi++;
-  return (a->cursi-1);
+
+  return a->cursi++;
 }
 
-void array_delslot(array *a, int slotn) {
-  if (slotn >= a->cursi) { return; }
-  a->cursi--;
-  if (a->cursi!=slotn) {
-    memcpy(a->content + (slotn * a->memberlen), a->content + (a->cursi * a->memberlen),a->memberlen);
-  }
-  if ((a->cursi + a->arlim2) < a->maxsi) {
-    /* Let's free some memory */
-    a->maxsi = a->cursi + a->arlim1;
-    a->content=realloc(a->content,a->maxsi*a->memberlen);
-    if (a->content==NULL) {
-      Error("array",ERR_FATAL,"Couldn't allocate memory for shrinking array?!?");
-      exit(1);
+void array_delslot(array *a, unsigned int index) {
+  /* if we're not deleting the end item then swap the last item into the deleted items space */
+  /* unordered so we can do this, and we can also use memcpy */
+  if(--a->cursi != index)
+    memcpy((char *)a->content + index * a->itemsize, (char *)a->content + a->cursi * a->itemsize, a->itemsize);
+
+  if(a->cursi + a->freechunksize < a->capacity) {
+
+    a->capacity = a->cursi + a->allocchunksize;
+
+    if(a->capacity == 0) {
+      free(a->content);
+
+      a->content = NULL;
+    } else {
+      void *newp = realloc(a->content, a->capacity * a->itemsize);
+
+      if(!newp) {
+        Error("array", ERR_WARNING, "Unable to shrink array!");
+      } else {
+        a->content = newp;
+      }
     }
   }
 }
 
-void array_free(array *a) {
-  free(a->content);
-  a->cursi=0;
-  a->maxsi=0;
-  a->memberlen=0;
-  a->content=NULL;
-  a->arlim1=ARLIM1;
-  a->arlim2=ARLIM2;
-}

diff --git a/lib/array.h b/lib/array.h
index 760e817fbd3a453541bd0c26449a0a9bf2474592..902a6b4001191bd3c927d8f9e616417c68b03702 100644 (file)
--- a/lib/array.h
+++ b/lib/array.h
@@ -1,22 +1,24 @@
 /* array.h */
 
-#ifndef __ARRAY_H
-#define __ARRAY_H
+#ifndef _ARRAY_H
 
-typedef struct {
-  unsigned cursi;
-  unsigned maxsi;
-  unsigned memberlen;
-  unsigned arlim1;
-  unsigned arlim2;
-  void *content;
+#define _ARRAY_H
+
+typedef struct array {
+  void *content; /* must be called this */
+  unsigned int cursi; /* must be called this */
+  unsigned int capacity;
+  unsigned int itemsize;
+  unsigned short allocchunksize;
+  unsigned short freechunksize;
 } array;
 
-void array_init(array *a, unsigned int memberlen);
-void array_setlim1(array *a, unsigned int lim);
-void array_setlim2(array *a, unsigned int lim);
-int array_getfreeslot(array *a);
-void array_delslot(array *a, int slotn);
+void array_init(array *a, unsigned int itemsize);
 void array_free(array *a);
+int array_getfreeslot(array *a);
+void array_delslot(array *a, unsigned int index);
+
+#define array_setlim1(a, size) (a)->allocchunksize = size;
+#define array_setlim2(a, size) (a)->freechunksize = size;
 
-#endif
+#endif /* _ARRAY_H */