libedataserver/e-memory.c

   1 /*
   2  * Copyright (c) 2000, 2001 Ximian Inc.
   3  *
   4  * Authors: Michael Zucchi <notzed@ximian.com>
   5  *          Jacob Berkman <jacob@ximian.com>
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of version 2 of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
  19  * USA
  20
  21 */
  22
  23 #include "e-memory.h"
  24
  25 #include <string.h> /* memset() */
  26 #include <stdlib.h> /* alloca() */
  27 #include <glib.h>
  28
  29 #define s(x)                    /* strv debug */
  30 #define p(x)   /* poolv debug */
  31 #define p2(x)   /* poolv assertion checking */
  32
  33 /*#define MALLOC_CHECK*/
  34
  35 /*#define PROFILE_POOLV*/
  36
  37 #ifdef PROFILE_POOLV
  38 #include <time.h>
  39 #define pp(x) x
  40 #else
  41 #define pp(x)
  42 #endif
  43
  44 /*#define TIMEIT*/
  45
  46 #ifdef TIMEIT
  47 #include <sys/time.h>
  48 #include <unistd.h>
  49
  50 struct timeval timeit_start;
  51
  52 static time_start(const char *desc)
  53 {
  54         gettimeofday(&timeit_start, NULL);
  55         printf("starting: %s\n", desc);
  56 }
  57
  58 static time_end(const char *desc)
  59 {
  60         unsigned long diff;
  61         struct timeval end;
  62
  63         gettimeofday(&end, NULL);
  64         diff = end.tv_sec * 1000 + end.tv_usec/1000;
  65         diff -= timeit_start.tv_sec * 1000 + timeit_start.tv_usec/1000;
  66         printf("%s took %ld.%03ld seconds\n",
  67                desc, diff / 1000, diff % 1000);
  68 }
  69 #else
  70 #define time_start(x)
  71 #define time_end(x)
  72 #endif
  73
  74 #ifdef MALLOC_CHECK
  75 #include <mcheck.h>
  76 #include <stdio.h>
  77 static void
  78 checkmem(void *p)
  79 {
  80         if (p) {
  81                 int status = mprobe(p);
  82
  83                 switch (status) {
  84                 case MCHECK_HEAD:
  85                         printf("Memory underrun at %p\n", p);
  86                         abort();
  87                 case MCHECK_TAIL:
  88                         printf("Memory overrun at %p\n", p);
  89                         abort();
  90                 case MCHECK_FREE:
  91                         printf("Double free %p\n", p);
  92                         abort();
  93                 }
  94         }
  95 }
  96 #define MPROBE(x) checkmem((void *)(x))
  97 #else
  98 #define MPROBE(x)
  99 #endif
 100
 101 /* mempool class */
 102
 103 typedef struct _MemChunkFreeNode {
 104         struct _MemChunkFreeNode *next;
 105         unsigned int atoms;
 106 } MemChunkFreeNode;
 107
 108 typedef struct _EMemChunk {
 109         unsigned int blocksize; /* number of atoms in a block */
 110         unsigned int atomsize;  /* size of each atom */
 111         GPtrArray *blocks;      /* blocks of raw memory */
 112         struct _MemChunkFreeNode *free;
 113 } MemChunk;
 114
 115 /**
 116  * e_memchunk_new:
 117  * @atomcount: The number of atoms stored in a single malloc'd block of memory.
 118  * @atomsize: The size of each allocation.
 119  *
 120  * Create a new memchunk header.  Memchunks are an efficient way to allocate
 121  * and deallocate identical sized blocks of memory quickly, and space efficiently.
 122  *
 123  * e_memchunks are effectively the same as gmemchunks, only faster (much), and
 124  * they use less memory overhead for housekeeping.
 125  *
 126  * Return value: The new header.
 127  **/
 128 MemChunk *e_memchunk_new(int atomcount, int atomsize)
 129 {
 130         MemChunk *m = g_malloc(sizeof(*m));
 131
 132         m->blocksize = atomcount;
 133         m->atomsize = MAX(atomsize, sizeof(MemChunkFreeNode));
 134         m->blocks = g_ptr_array_new();
 135         m->free = NULL;
 136
 137         return m;
 138 }
 139
 140 /**
 141  * memchunk_alloc:
 142  * @m:
 143  *
 144  * Allocate a new atom size block of memory from a memchunk.
 145  **/
 146 void *e_memchunk_alloc(MemChunk *m)
 147 {
 148         char *b;
 149         MemChunkFreeNode *f;
 150         void *mem;
 151
 152         f = m->free;
 153         if (f) {
 154                 f->atoms--;
 155                 if (f->atoms > 0) {
 156                         mem = ((char *)f) + (f->atoms*m->atomsize);
 157                 } else {
 158                         mem = f;
 159                         m->free = m->free->next;
 160                 }
 161                 return mem;
 162         } else {
 163                 b = g_malloc(m->blocksize * m->atomsize);
 164                 g_ptr_array_add(m->blocks, b);
 165                 f = (MemChunkFreeNode *)&b[m->atomsize];
 166                 f->atoms = m->blocksize-1;
 167                 f->next = NULL;
 168                 m->free = f;
 169                 return b;
 170         }
 171 }
 172
 173 void *e_memchunk_alloc0(EMemChunk *m)
 174 {
 175         void *mem;
 176
 177         mem = e_memchunk_alloc(m);
 178         memset(mem, 0, m->atomsize);
 179
 180         return mem;
 181 }
 182
 183 /**
 184  * e_memchunk_free:
 185  * @m:
 186  * @mem: Address of atom to free.
 187  *
 188  * Free a single atom back to the free pool of atoms in the given
 189  * memchunk.
 190  **/
 191 void
 192 e_memchunk_free(MemChunk *m, void *mem)
 193 {
 194         MemChunkFreeNode *f;
 195
 196         /* put the location back in the free list.  If we knew if the preceeding or following
 197            cells were free, we could merge the free nodes, but it doesn't really add much */
 198         f = mem;
 199         f->next = m->free;
 200         m->free = f;
 201         f->atoms = 1;
 202
 203         /* we could store the free list sorted - we could then do the above, and also
 204            probably improve the locality of reference properties for the allocator */
 205         /* and it would simplify some other algorithms at that, but slow this one down
 206            significantly */
 207 }
 208
 209 /**
 210  * e_memchunk_empty:
 211  * @m:
 212  *
 213  * Clean out the memchunk buffers.  Marks all allocated memory as free blocks,
 214  * but does not give it back to the system.  Can be used if the memchunk
 215  * is to be used repeatedly.
 216  **/
 217 void
 218 e_memchunk_empty(MemChunk *m)
 219 {
 220         int i;
 221         MemChunkFreeNode *f, *h = NULL;
 222
 223         for (i=0;i<m->blocks->len;i++) {
 224                 f = (MemChunkFreeNode *)m->blocks->pdata[i];
 225                 f->atoms = m->blocksize;
 226                 f->next = h;
 227                 h = f;
 228         }
 229         m->free = h;
 230 }
 231
 232 struct _cleaninfo {
 233         struct _cleaninfo *next;
 234         char *base;
 235         int count;
 236         int size;               /* just so tree_search has it, sigh */
 237 };
 238
 239 static int tree_compare(struct _cleaninfo *a, struct _cleaninfo *b)
 240 {
 241         if (a->base < b->base)
 242                 return -1;
 243         else if (a->base > b->base)
 244                 return 1;
 245         return 0;
 246 }
 247
 248 static int tree_search(struct _cleaninfo *a, char *mem)
 249 {
 250         if (a->base <= mem) {
 251                 if (mem < &a->base[a->size])
 252                         return 0;
 253                 return 1;
 254         }
 255         return -1;
 256 }
 257
 258 /**
 259  * e_memchunk_clean:
 260  * @m:
 261  *
 262  * Scan all empty blocks and check for blocks which can be free'd
 263  * back to the system.
 264  *
 265  * This routine may take a while to run if there are many allocated
 266  * memory blocks (if the total number of allocations is many times
 267  * greater than atomcount).
 268  **/
 269 void
 270 e_memchunk_clean(MemChunk *m)
 271 {
 272         GTree *tree;
 273         int i;
 274         MemChunkFreeNode *f;
 275         struct _cleaninfo *ci, *hi = NULL;
 276
 277         f = m->free;
 278         if (m->blocks->len == 0 || f == NULL)
 279                 return;
 280
 281         /* first, setup the tree/list so we can map free block addresses to block addresses */
 282         tree = g_tree_new((GCompareFunc)tree_compare);
 283         for (i=0;i<m->blocks->len;i++) {
 284                 ci = alloca(sizeof(*ci));
 285                 ci->count = 0;
 286                 ci->base = m->blocks->pdata[i];
 287                 ci->size = m->blocksize * m->atomsize;
 288                 g_tree_insert(tree, ci, ci);
 289                 ci->next = hi;
 290                 hi = ci;
 291         }
 292
 293         /* now, scan all free nodes, and count them in their tree node */
 294         while (f) {
 295                 ci = g_tree_search(tree, (GCompareFunc) tree_search, f);
 296                 if (ci) {
 297                         ci->count += f->atoms;
 298                 } else {
 299                         g_warning("error, can't find free node in memory block\n");
 300                 }
 301                 f = f->next;
 302         }
 303
 304         /* if any nodes are all free, free & unlink them */
 305         ci = hi;
 306         while (ci) {
 307                 if (ci->count == m->blocksize) {
 308                         MemChunkFreeNode *prev = NULL;
 309
 310                         f = m->free;
 311                         while (f) {
 312                                 if (tree_search (ci, (void *) f) == 0) {
 313                                         /* prune this node from our free-node list */
 314                                         if (prev)
 315                                                 prev->next = f->next;
 316                                         else
 317                                                 m->free = f->next;
 318                                 } else {
 319                                         prev = f;
 320                                 }
 321
 322                                 f = f->next;
 323                         }
 324
 325                         g_ptr_array_remove_fast(m->blocks, ci->base);
 326                         g_free(ci->base);
 327                 }
 328                 ci = ci->next;
 329         }
 330
 331         g_tree_destroy(tree);
 332 }
 333
 334 /**
 335  * e_memchunk_destroy:
 336  * @m:
 337  *
 338  * Free the memchunk header, and all associated memory.
 339  **/
 340 void
 341 e_memchunk_destroy(MemChunk *m)
 342 {
 343         int i;
 344
 345         if (m == NULL)
 346                 return;
 347
 348         for (i=0;i<m->blocks->len;i++)
 349                 g_free(m->blocks->pdata[i]);
 350         g_ptr_array_free(m->blocks, TRUE);
 351         g_free(m);
 352 }
 353
 354 typedef struct _MemPoolNode {
 355         struct _MemPoolNode *next;
 356
 357         int free;
 358 } MemPoolNode;
 359
 360 typedef struct _MemPoolThresholdNode {
 361         struct _MemPoolThresholdNode *next;
 362 } MemPoolThresholdNode;
 363
 364 #define ALIGNED_SIZEOF(t)       ((sizeof (t) + G_MEM_ALIGN - 1) & -G_MEM_ALIGN)
 365
 366 typedef struct _EMemPool {
 367         int blocksize;
 368         int threshold;
 369         unsigned int align;
 370         struct _MemPoolNode *blocks;
 371         struct _MemPoolThresholdNode *threshold_blocks;
 372 } MemPool;
 373
 374 /* a pool of mempool header blocks */
 375 static MemChunk *mempool_memchunk;
 376 #ifdef G_THREADS_ENABLED
 377 static GStaticMutex mempool_mutex = G_STATIC_MUTEX_INIT;
 378 #endif
 379
 380 /**
 381  * e_mempool_new:
 382  * @blocksize: The base blocksize to use for all system alocations.
 383  * @threshold: If the allocation exceeds the threshold, then it is
 384  * allocated separately and stored in a separate list.
 385  * @flags: Alignment options: E_MEMPOOL_ALIGN_STRUCT uses native
 386  * struct alignment, E_MEMPOOL_ALIGN_WORD aligns to 16 bits (2 bytes),
 387  * and E_MEMPOOL_ALIGN_BYTE aligns to the nearest byte.  The default
 388  * is to align to native structures.
 389  *
 390  * Create a new mempool header.  Mempools can be used to efficiently
 391  * allocate data which can then be freed as a whole.
 392  *
 393  * Mempools can also be used to efficiently allocate arbitrarily
 394  * aligned data (such as strings) without incurring the space overhead
 395  * of aligning each allocation (which is not required for strings).
 396  *
 397  * However, each allocation cannot be freed individually, only all
 398  * or nothing.
 399  *
 400  * Return value:
 401  **/
 402 MemPool *e_mempool_new(int blocksize, int threshold, EMemPoolFlags flags)
 403 {
 404         MemPool *pool;
 405
 406 #ifdef G_THREADS_ENABLED
 407         g_static_mutex_lock(&mempool_mutex);
 408 #endif
 409         if (mempool_memchunk == NULL) {
 410                 mempool_memchunk = e_memchunk_new(8, sizeof(MemPool));
 411         }
 412         pool = e_memchunk_alloc(mempool_memchunk);
 413 #ifdef G_THREADS_ENABLED
 414         g_static_mutex_unlock(&mempool_mutex);
 415 #endif
 416         if (threshold >= blocksize)
 417                 threshold = blocksize * 2 / 3;
 418         pool->blocksize = blocksize;
 419         pool->threshold = threshold;
 420         pool->blocks = NULL;
 421         pool->threshold_blocks = NULL;
 422
 423         switch (flags & E_MEMPOOL_ALIGN_MASK) {
 424         case E_MEMPOOL_ALIGN_STRUCT:
 425         default:
 426                 pool->align = G_MEM_ALIGN-1;
 427                 break;
 428         case E_MEMPOOL_ALIGN_WORD:
 429                 pool->align = 2-1;
 430                 break;
 431         case E_MEMPOOL_ALIGN_BYTE:
 432                 pool->align = 1-1;
 433         }
 434         return pool;
 435 }
 436
 437 /**
 438  * e_mempool_alloc:
 439  * @pool:
 440  * @size:
 441  *
 442  * Allocate a new data block in the mempool.  Size will
 443  * be rounded up to the mempool's alignment restrictions
 444  * before being used.
 445  **/
 446 void *e_mempool_alloc(MemPool *pool, register int size)
 447 {
 448         size = (size + pool->align) & (~(pool->align));
 449         if (size>=pool->threshold) {
 450                 MemPoolThresholdNode *n;
 451
 452                 n = g_malloc(ALIGNED_SIZEOF(*n) + size);
 453                 n->next = pool->threshold_blocks;
 454                 pool->threshold_blocks = n;
 455                 return (char *) n + ALIGNED_SIZEOF(*n);
 456         } else {
 457                 register MemPoolNode *n;
 458
 459                 n = pool->blocks;
 460                 if (n && n->free >= size) {
 461                         n->free -= size;
 462                         return (char *) n + ALIGNED_SIZEOF(*n) + n->free;
 463                 }
 464
 465                 /* maybe we could do some sort of the free blocks based on size, but
 466                    it doubt its worth it at all */
 467
 468                 n = g_malloc(ALIGNED_SIZEOF(*n) + pool->blocksize);
 469                 n->next = pool->blocks;
 470                 pool->blocks = n;
 471                 n->free = pool->blocksize - size;
 472                 return (char *) n + ALIGNED_SIZEOF(*n) + n->free;
 473         }
 474 }
 475
 476 char *e_mempool_strdup(EMemPool *pool, const char *str)
 477 {
 478         char *out;
 479
 480         out = e_mempool_alloc(pool, strlen(str)+1);
 481         strcpy(out, str);
 482
 483         return out;
 484 }
 485
 486 /**
 487  * e_mempool_flush:
 488  * @pool:
 489  * @freeall: Free all system allocated blocks as well.
 490  *
 491  * Flush used memory and mark allocated blocks as free.
 492  *
 493  * If @freeall is #TRUE, then all allocated blocks are free'd
 494  * as well.  Otherwise only blocks above the threshold are
 495  * actually freed, and the others are simply marked as empty.
 496  **/
 497 void e_mempool_flush(MemPool *pool, int freeall)
 498 {
 499         MemPoolThresholdNode *tn, *tw;
 500         MemPoolNode *pw, *pn;
 501
 502         tw = pool->threshold_blocks;
 503         while (tw) {
 504                 tn = tw->next;
 505                 g_free(tw);
 506                 tw = tn;
 507         }
 508         pool->threshold_blocks = NULL;
 509
 510         if (freeall) {
 511                 pw = pool->blocks;
 512                 while (pw) {
 513                         pn = pw->next;
 514                         g_free(pw);
 515                         pw = pn;
 516                 }
 517                 pool->blocks = NULL;
 518         } else {
 519                 pw = pool->blocks;
 520                 while (pw) {
 521                         pw->free = pool->blocksize;
 522                         pw = pw->next;
 523                 }
 524         }
 525 }
 526
 527 /**
 528  * e_mempool_destroy:
 529  * @pool:
 530  *
 531  * Free all memory associated with a mempool.
 532  **/
 533 void e_mempool_destroy(MemPool *pool)
 534 {
 535         if (pool) {
 536                 e_mempool_flush(pool, 1);
 537 #ifdef G_THREADS_ENABLED
 538                 g_static_mutex_lock(&mempool_mutex);
 539 #endif
 540                 e_memchunk_free(mempool_memchunk, pool);
 541 #ifdef G_THREADS_ENABLED
 542                 g_static_mutex_unlock(&mempool_mutex);
 543 #endif
 544         }
 545 }
 546
 547
 548 /*
 549   string array classes
 550 */
 551
 552 #define STRV_UNPACKED ((unsigned char)(~0))
 553
 554 struct _EStrv {
 555         unsigned char length;   /* how many entries we have (or the token STRV_UNPACKED) */
 556         char data[1];           /* data follows */
 557 };
 558
 559 struct _s_strv_string {
 560         char *string;           /* the string to output */
 561         char *free;             /* a string to free, if we referenced it */
 562 };
 563
 564 struct _e_strvunpacked {
 565         unsigned char type;     /* we overload last to indicate this is unpacked */
 566         MemPool *pool;          /* pool of memory for strings */
 567         struct _EStrv *source;  /* if we were converted from a packed one, keep the source around for a while */
 568         unsigned int length;
 569         struct _s_strv_string strings[1]; /* the string array data follows */
 570 };
 571
 572 /**
 573  * e_strv_new:
 574  * @size: The number of elements in the strv.  Currently this is limited
 575  * to 254 elements.
 576  *
 577  * Create a new strv (string array) header.  strv's can be used to
 578  * create and work with arrays of strings that can then be compressed
 579  * into a space-efficient static structure.  This is useful
 580  * where a number of strings are to be stored for lookup, and not
 581  * generally edited afterwards.
 582  *
 583  * The size limit is currently 254 elements.  This will probably not
 584  * change as arrays of this size suffer significant performance
 585  * penalties when looking up strings with high indices.
 586  *
 587  * Return value:
 588  **/
 589 struct _EStrv *
 590 e_strv_new(int size)
 591 {
 592         struct _e_strvunpacked *s;
 593
 594         g_assert(size<255);
 595
 596         s = g_malloc(sizeof(*s) + (size-1)*sizeof(s->strings[0]));
 597         s(printf("new strv=%p, size = %d bytes\n", s, sizeof(*s) + (size-1)*sizeof(char *)));
 598         s->type = STRV_UNPACKED;
 599         s->pool = NULL;
 600         s->length = size;
 601         s->source = NULL;
 602         memset(s->strings, 0, size*sizeof(s->strings[0]));
 603
 604         return (struct _EStrv *)s;
 605 }
 606
 607 static struct _e_strvunpacked *
 608 strv_unpack(struct _EStrv *strv)
 609 {
 610         struct _e_strvunpacked *s;
 611         register char *p;
 612         int i;
 613
 614         s(printf("unpacking\n"));
 615
 616         s = (struct _e_strvunpacked *)e_strv_new(strv->length);
 617         p = strv->data;
 618         for (i=0;i<s->length;i++) {
 619                 if (i>0)
 620                         while (*p++)
 621                                 ;
 622                 s->strings[i].string = p;
 623         }
 624         s->source = strv;
 625         s->type = STRV_UNPACKED;
 626
 627         return s;
 628 }
 629
 630 /**
 631  * e_strv_set_ref:
 632  * @strv:
 633  * @index:
 634  * @str:
 635  *
 636  * Set a string array element by reference.  The string
 637  * is not copied until the array is packed.
 638  *
 639  * If @strv has been packed, then it is unpacked ready
 640  * for more inserts, and should be packed again once finished with.
 641  * The memory used by the original @strv is not freed until
 642  * the new strv is packed, or freed itself.
 643  *
 644  * Return value: A new EStrv if the strv has already
 645  * been packed, otherwise @strv.
 646  **/
 647 struct _EStrv *
 648 e_strv_set_ref(struct _EStrv *strv, int index, char *str)
 649 {
 650         struct _e_strvunpacked *s;
 651
 652         s(printf("set ref %d '%s'\nawkmeharder: %s\n ", index, str, str));
 653
 654         if (strv->length != STRV_UNPACKED)
 655                 s = strv_unpack(strv);
 656         else
 657                 s = (struct _e_strvunpacked *)strv;
 658
 659         g_assert(index>=0 && index < s->length);
 660
 661         s->strings[index].string = str;
 662
 663         return (struct _EStrv *)s;
 664 }
 665
 666 /**
 667  * e_strv_set_ref_free:
 668  * @strv:
 669  * @index:
 670  * @str:
 671  *
 672  * Set a string by reference, similar to set_ref, but also
 673  * free the string when finished with it.  The string
 674  * is not copied until the strv is packed, and not at
 675  * all if the index is overwritten.
 676  *
 677  * Return value: @strv if already unpacked, otherwise an packed
 678  * EStrv.
 679  **/
 680 struct _EStrv *
 681 e_strv_set_ref_free(struct _EStrv *strv, int index, char *str)
 682 {
 683         struct _e_strvunpacked *s;
 684
 685         s(printf("set ref %d '%s'\nawkmeevenharder: %s\n ", index, str, str));
 686
 687         if (strv->length != STRV_UNPACKED)
 688                 s = strv_unpack(strv);
 689         else
 690                 s = (struct _e_strvunpacked *)strv;
 691
 692         g_assert(index>=0 && index < s->length);
 693
 694         s->strings[index].string = str;
 695         if (s->strings[index].free)
 696                 g_free(s->strings[index].free);
 697         s->strings[index].free = str;
 698
 699         return (struct _EStrv *)s;
 700 }
 701
 702 /**
 703  * e_strv_set:
 704  * @strv:
 705  * @index:
 706  * @str:
 707  *
 708  * Set a string array reference.  The string @str is copied
 709  * into the string array at location @index.
 710  *
 711  * If @strv has been packed, then it is unpacked ready
 712  * for more inserts, and should be packed again once finished with.
 713  *
 714  * Return value: A new EStrv if the strv has already
 715  * been packed, otherwise @strv.
 716  **/
 717 struct _EStrv *
 718 e_strv_set(struct _EStrv *strv, int index, const char *str)
 719 {
 720         struct _e_strvunpacked *s;
 721
 722         s(printf("set %d '%s'\n", index, str));
 723
 724         if (strv->length != STRV_UNPACKED)
 725                 s = strv_unpack(strv);
 726         else
 727                 s = (struct _e_strvunpacked *)strv;
 728
 729         g_assert(index>=0 && index < s->length);
 730
 731         if (s->pool == NULL)
 732                 s->pool = e_mempool_new(1024, 512, E_MEMPOOL_ALIGN_BYTE);
 733
 734         s->strings[index].string = e_mempool_alloc(s->pool, strlen(str)+1);
 735         strcpy(s->strings[index].string, str);
 736
 737         return (struct _EStrv *)s;
 738 }
 739
 740 /**
 741  * e_strv_pack:
 742  * @strv:
 743  *
 744  * Pack the @strv into a space efficient structure for later lookup.
 745  *
 746  * All strings are packed into a single allocated block, separated
 747  * by single \0 characters, together with a count byte.
 748  *
 749  * Return value:
 750  **/
 751 struct _EStrv *
 752 e_strv_pack(struct _EStrv *strv)
 753 {
 754         struct _e_strvunpacked *s;
 755         int len, i;
 756         register char *src, *dst;
 757
 758         if (strv->length == STRV_UNPACKED) {
 759                 s = (struct _e_strvunpacked *)strv;
 760
 761                 s(printf("packing string\n"));
 762
 763                 len = 0;
 764                 for (i=0;i<s->length;i++)
 765                         len += s->strings[i].string?strlen(s->strings[i].string)+1:1;
 766
 767                 strv = g_malloc(sizeof(*strv) + len);
 768                 s(printf("allocating strv=%p, size = %d\n", strv, sizeof(*strv)+len));
 769                 strv->length = s->length;
 770                 dst = strv->data;
 771                 for (i=0;i<s->length;i++) {
 772                         if ((src = s->strings[i].string)) {
 773                                 while ((*dst++ = *src++))
 774                                         ;
 775                         } else {
 776                                 *dst++ = 0;
 777                         }
 778                 }
 779                 e_strv_destroy((struct _EStrv *)s);
 780         }
 781         return strv;
 782 }
 783
 784 /**
 785  * e_strv_get:
 786  * @strv:
 787  * @index:
 788  *
 789  * Retrieve a string by index.  This function works
 790  * identically on both packed and unpacked strv's, although
 791  * may be much slower on a packed strv.
 792  *
 793  * Return value:
 794  **/
 795 char *
 796 e_strv_get(struct _EStrv *strv, int index)
 797 {
 798         struct _e_strvunpacked *s;
 799         char *p;
 800
 801         if (strv->length != STRV_UNPACKED) {
 802                 g_assert(index>=0 && index < strv->length);
 803                 p = strv->data;
 804                 while (index > 0) {
 805                         while (*p++ != 0)
 806                                 ;
 807                         index--;
 808                 }
 809                 return p;
 810         } else {
 811                 s = (struct _e_strvunpacked *)strv;
 812                 g_assert(index>=0 && index < s->length);
 813                 return s->strings[index].string?s->strings[index].string:"";
 814         }
 815 }
 816
 817 /**
 818  * e_strv_destroy:
 819  * @strv:
 820  *
 821  * Free a strv and all associated memory.  Works on packed
 822  * or unpacked strv's.
 823  **/
 824 void
 825 e_strv_destroy(struct _EStrv *strv)
 826 {
 827         struct _e_strvunpacked *s;
 828         int i;
 829
 830         s(printf("freeing strv\n"));
 831
 832         if (strv->length == STRV_UNPACKED) {
 833                 s = (struct _e_strvunpacked *)strv;
 834                 if (s->pool)
 835                         e_mempool_destroy(s->pool);
 836                 if (s->source)
 837                         e_strv_destroy(s->source);
 838                 for (i=0;i<s->length;i++) {
 839                         if (s->strings[i].free)
 840                                 g_free(s->strings[i].free);
 841                 }
 842         }
 843
 844         s(printf("freeing strv=%p\n", strv));
 845
 846         g_free(strv);
 847 }
 848
 849
 850
 851 /* string pool stuff */
 852
 853 /* TODO:
 854     garbage collection, using the following technique:
 855       Create a memchunk for each possible size of poolv, and allocate every poolv from those
 856       To garbage collect, scan all memchunk internally, ignoring any free areas (or mark each
 857         poolv when freeing it - set length 0?), and find out which strings are not anywhere,
 858         then free them.
 859
 860     OR:
 861        Just keep a refcount in the hashtable, instead of duplicating the key pointer.
 862
 863    either would also require a free for the mempool, so ignore it for now */
 864
 865 /*#define POOLV_REFCNT*/ /* Define to enable refcounting code that does
 866                         automatic garbage collection of unused strings */
 867
 868 static GHashTable *poolv_pool = NULL;
 869 static EMemPool *poolv_mempool = NULL;
 870
 871 #ifdef MALLOC_CHECK
 872 static GPtrArray *poolv_table = NULL;
 873 #endif
 874
 875 #ifdef PROFILE_POOLV
 876 static gulong poolv_hits = 0;
 877 static gulong poolv_misses = 0;
 878 static unsigned long poolv_mem, poolv_count;
 879 #endif
 880
 881 #ifdef G_THREADS_ENABLED
 882 static GStaticMutex poolv_mutex = G_STATIC_MUTEX_INIT;
 883 #endif
 884
 885 struct _EPoolv {
 886         unsigned char length;
 887         char *s[1];
 888 };
 889
 890 /**
 891  * e_poolv_new: @size: The number of elements in the poolv, maximum of 254 elements.
 892  *
 893  * create a new poolv (string vector which shares a global string
 894  * pool).  poolv's can be used to work with arrays of strings which
 895  * save memory by eliminating duplicated allocations of the same
 896  * string.
 897  *
 898  * this is useful when you have a log of read-only strings that do not
 899  * go away and are duplicated a lot (such as email headers).
 900  *
 901  * we should probably in the future ref count the strings contained in
 902  * the hash table, but for now let's not.
 903  *
 904  * Return value: new pooled string vector
 905  **/
 906 EPoolv *
 907 e_poolv_new(unsigned int size)
 908 {
 909         EPoolv *poolv;
 910
 911         g_assert(size < 255);
 912
 913         poolv = g_malloc0(sizeof (*poolv) + (size - 1) * sizeof (char *));
 914         poolv->length = size;
 915
 916 #ifdef G_THREADS_ENABLED
 917         g_static_mutex_lock(&poolv_mutex);
 918 #endif
 919         if (!poolv_pool)
 920                 poolv_pool = g_hash_table_new(g_str_hash, g_str_equal);
 921
 922         if (!poolv_mempool)
 923                 poolv_mempool = e_mempool_new(32 * 1024, 512, E_MEMPOOL_ALIGN_BYTE);
 924
 925 #ifdef MALLOC_CHECK
 926         {
 927                 int i;
 928
 929                 if (poolv_table == NULL)
 930                         poolv_table = g_ptr_array_new();
 931
 932                 for (i=0;i<poolv_table->len;i++)
 933                         MPROBE(poolv_table->pdata[i]);
 934
 935                 g_ptr_array_add(poolv_table, poolv);
 936         }
 937 #endif
 938
 939 #ifdef G_THREADS_ENABLED
 940         g_static_mutex_unlock(&poolv_mutex);
 941 #endif
 942
 943         p(printf("new poolv=%p\tsize=%d\n", poolv, sizeof(*poolv) + (size-1)*sizeof(char *)));
 944
 945 #ifdef PROFILE_POOLV
 946         poolv_count++;
 947 #endif
 948         return poolv;
 949 }
 950
 951 /**
 952  * e_poolv_cpy:
 953  * @dest: destination pooled string vector
 954  * @src: source pooled string vector
 955  *
 956  * Copy the contents of a pooled string vector
 957  *
 958  * Return value: @dest, which may be re-allocated if the strings
 959  * are different lengths.
 960  **/
 961 EPoolv *
 962 e_poolv_cpy(EPoolv *dest, const EPoolv *src)
 963 {
 964 #ifdef POOLV_REFCNT
 965         int i;
 966         unsigned int ref;
 967         char *key;
 968 #endif
 969
 970         p2(g_return_val_if_fail (dest != NULL, NULL));
 971         p2(g_return_val_if_fail (src != NULL, NULL));
 972
 973         MPROBE(dest);
 974         MPROBE(src);
 975
 976         if (dest->length != src->length) {
 977                 e_poolv_destroy(dest);
 978                 dest = e_poolv_new(src->length);
 979         }
 980
 981 #ifdef POOLV_REFCNT
 982 #ifdef G_THREADS_ENABLED
 983         g_static_mutex_lock(&poolv_mutex);
 984 #endif
 985         /* ref new copies */
 986         for (i=0;i<src->length;i++) {
 987                 if (src->s[i]) {
 988                         if (g_hash_table_lookup_extended(poolv_pool, src->s[i], (void **)&key, (void **)&ref)) {
 989                                 g_hash_table_insert(poolv_pool, key, (void *)(ref+1));
 990                         } else {
 991                                 g_assert_not_reached();
 992                         }
 993                 }
 994         }
 995
 996         /* unref the old ones */
 997         for (i=0;i<dest->length;i++) {
 998                 if (dest->s[i]) {
 999                         if (g_hash_table_lookup_extended(poolv_pool, dest->s[i], (void **)&key, (void **)&ref)) {
1000                                 /* if ref == 1 free it */
1001                                 g_assert(ref > 0);
1002                                 g_hash_table_insert(poolv_pool, key, (void *)(ref-1));
1003                         } else {
1004                                 g_assert_not_reached();
1005                         }
1006                 }
1007         }
1008 #ifdef G_THREADS_ENABLED
1009         g_static_mutex_unlock(&poolv_mutex);
1010 #endif
1011 #endif
1012
1013         memcpy(dest->s, src->s, src->length * sizeof (char *));
1014
1015         return dest;
1016 }
1017
1018 #ifdef PROFILE_POOLV
1019 static void
1020 poolv_profile_update (void)
1021 {
1022         static time_t last_time = 0;
1023         time_t new_time;
1024
1025         new_time = time (NULL);
1026         if (new_time - last_time < 5)
1027                 return;
1028
1029         printf("poolv profile: %lu hits, %lu misses: %d%% hit rate, memory: %lu, instances: %lu\n",
1030                poolv_hits, poolv_misses,
1031                (int)(100.0 * ((double) poolv_hits / (double) (poolv_hits + poolv_misses))),
1032                poolv_mem, poolv_count);
1033
1034         last_time = new_time;
1035 }
1036 #endif
1037
1038 /**
1039  * e_poolv_set:
1040  * @poolv: pooled string vector
1041  * @index: index in vector of string
1042  * @str: string to set
1043  * @freeit: whether the caller is releasing its reference to the
1044  * string
1045  *
1046  * Set a string vector reference.  If the caller will no longer be
1047  * referencing the string, freeit should be TRUE.  Otherwise, this
1048  * will duplicate the string if it is not found in the pool.
1049  *
1050  * Return value: @poolv
1051  **/
1052 EPoolv *
1053 e_poolv_set (EPoolv *poolv, int index, char *str, int freeit)
1054 {
1055 #ifdef POOLV_REFCNT
1056         unsigned int ref;
1057         char *key;
1058 #endif
1059
1060         p2(g_return_val_if_fail (poolv != NULL, NULL));
1061
1062         g_assert(index >=0 && index < poolv->length);
1063
1064         MPROBE(poolv);
1065
1066         p(printf("setting %d `%s'\n", index, str));
1067
1068         if (!str) {
1069 #ifdef POOLV_REFCNT
1070                 if (poolv->s[index]) {
1071                         if (g_hash_table_lookup_extended(poolv_pool, poolv->s[index], (void **)&key, (void **)&ref)) {
1072                                 g_assert(ref > 0);
1073                                 g_hash_table_insert(poolv_pool, key, (void *)(ref-1));
1074                         } else {
1075                                 g_assert_not_reached();
1076                         }
1077                 }
1078 #endif
1079                 poolv->s[index] = NULL;
1080                 return poolv;
1081         }
1082
1083 #ifdef G_THREADS_ENABLED
1084         g_static_mutex_lock(&poolv_mutex);
1085 #endif
1086
1087 #ifdef POOLV_REFCNT
1088         if (g_hash_table_lookup_extended(poolv_pool, str, (void **)&key, (void **)&ref)) {
1089                 g_hash_table_insert(poolv_pool, key, (void *)(ref+1));
1090                 poolv->s[index] = key;
1091 # ifdef PROFILE_POOLV
1092                 poolv_hits++;
1093                 poolv_profile_update ();
1094 # endif
1095         } else {
1096 # ifdef PROFILE_POOLV
1097                 poolv_misses++;
1098                 poolv_mem += strlen(str);
1099                 poolv_profile_update ();
1100 # endif
1101                 poolv->s[index] = e_mempool_strdup(poolv_mempool, str);
1102                 g_hash_table_insert(poolv_pool, poolv->s[index], (void *)1);
1103         }
1104
1105 #else  /* !POOLV_REFCNT */
1106         if ((poolv->s[index] = g_hash_table_lookup(poolv_pool, str)) != NULL) {
1107 # ifdef PROFILE_POOLV
1108                 poolv_hits++;
1109                 poolv_profile_update ();
1110 # endif
1111         } else {
1112 # ifdef PROFILE_POOLV
1113                 poolv_misses++;
1114                 poolv_mem += strlen(str);
1115                 poolv_profile_update ();
1116 # endif
1117                 poolv->s[index] = e_mempool_strdup(poolv_mempool, str);
1118                 g_hash_table_insert(poolv_pool, poolv->s[index], poolv->s[index]);
1119         }
1120 #endif /* !POOLV_REFCNT */
1121
1122 #ifdef G_THREADS_ENABLED
1123         g_static_mutex_unlock(&poolv_mutex);
1124 #endif
1125
1126         if (freeit)
1127                 g_free(str);
1128
1129         return poolv;
1130 }
1131
1132 /**
1133  * e_poolv_get:
1134  * @poolv: pooled string vector
1135  * @index: index in vector of string
1136  *
1137  * Retrieve a string by index.  This could possibly just be a macro.
1138  *
1139  * Since the pool is never freed, this string does not need to be
1140  * duplicated, but should not be modified.
1141  *
1142  * Return value: string at that index.
1143  **/
1144 const char *
1145 e_poolv_get(EPoolv *poolv, int index)
1146 {
1147         g_assert(poolv != NULL);
1148         g_assert(index>= 0 && index < poolv->length);
1149
1150         MPROBE(poolv);
1151
1152         p(printf("get %d = `%s'\n", index, poolv->s[index]));
1153
1154         return poolv->s[index]?poolv->s[index]:"";
1155 }
1156
1157 /**
1158  * e_poolv_destroy:
1159  * @poolv: pooled string vector to free
1160  *
1161  * Free a pooled string vector.  This doesn't free the strings from
1162  * the vector, however.
1163  **/
1164 void
1165 e_poolv_destroy(EPoolv *poolv)
1166 {
1167 #ifdef POOLV_REFCNT
1168         int i;
1169         unsigned int ref;
1170         char *key;
1171
1172         MPROBE(poolv);
1173
1174 #ifdef G_THREADS_ENABLED
1175         g_static_mutex_lock(&poolv_mutex);
1176 #endif
1177
1178 #ifdef MALLOC_CHECK
1179         for (i=0;i<poolv_table->len;i++)
1180                 MPROBE(poolv_table->pdata[i]);
1181
1182         g_ptr_array_remove_fast(poolv_table, poolv);
1183 #endif
1184
1185         for (i=0;i<poolv->length;i++) {
1186                 if (poolv->s[i]) {
1187                         if (g_hash_table_lookup_extended(poolv_pool, poolv->s[i], (void **)&key, (void **)&ref)) {
1188                                 /* if ref == 1 free it */
1189                                 g_assert(ref > 0);
1190                                 g_hash_table_insert(poolv_pool, key, (void *)(ref-1));
1191                         } else {
1192                                 g_assert_not_reached();
1193                         }
1194                 }
1195         }
1196 #ifdef G_THREADS_ENABLED
1197         g_static_mutex_unlock(&poolv_mutex);
1198 #endif
1199 #endif
1200
1201 #ifdef PROFILE_POOLV
1202         poolv_count++;
1203 #endif
1204         g_free(poolv);
1205 }
1206
1207 #if 0
1208
1209 #define CHUNK_SIZE (20)
1210 #define CHUNK_COUNT (32)
1211
1212 #define s(x)
1213
1214 main()
1215 {
1216         int i;
1217         MemChunk *mc;
1218         void *mem, *last;
1219         GMemChunk *gmc;
1220         struct _EStrv *s;
1221
1222         s = strv_new(8);
1223         s = strv_set(s, 1, "Testing 1");
1224         s = strv_set(s, 2, "Testing 2");
1225         s = strv_set(s, 3, "Testing 3");
1226         s = strv_set(s, 4, "Testing 4");
1227         s = strv_set(s, 5, "Testing 5");
1228         s = strv_set(s, 6, "Testing 7");
1229
1230         for (i=0;i<8;i++) {
1231                 printf("s[%d] = %s\n", i, strv_get(s, i));
1232         }
1233
1234         s(sleep(5));
1235
1236         printf("packing ...\n");
1237         s = strv_pack(s);
1238
1239         for (i=0;i<8;i++) {
1240                 printf("s[%d] = %s\n", i, strv_get(s, i));
1241         }
1242
1243         printf("setting ...\n");
1244
1245         s = strv_set_ref(s, 1, "Testing 1 x");
1246
1247         for (i=0;i<8;i++) {
1248                 printf("s[%d] = %s\n", i, strv_get(s, i));
1249         }
1250
1251         printf("packing ...\n");
1252         s = strv_pack(s);
1253
1254         for (i=0;i<8;i++) {
1255                 printf("s[%d] = %s\n", i, strv_get(s, i));
1256         }
1257
1258         strv_free(s);
1259
1260 #if 0
1261         time_start("Using memchunks");
1262         mc = memchunk_new(CHUNK_COUNT, CHUNK_SIZE);
1263         for (i=0;i<1000000;i++) {
1264                 mem = memchunk_alloc(mc);
1265                 if ((i & 1) == 0)
1266                         memchunk_free(mc, mem);
1267         }
1268         s(sleep(10));
1269         memchunk_destroy(mc);
1270         time_end("allocating 1000000 memchunks, freeing 500k");
1271
1272         time_start("Using gmemchunks");
1273         gmc = g_mem_chunk_new("memchunk", CHUNK_SIZE, CHUNK_SIZE*CHUNK_COUNT, G_ALLOC_AND_FREE);
1274         for (i=0;i<1000000;i++) {
1275                 mem = g_mem_chunk_alloc(gmc);
1276                 if ((i & 1) == 0)
1277                         g_mem_chunk_free(gmc, mem);
1278         }
1279         s(sleep(10));
1280         g_mem_chunk_destroy(gmc);
1281         time_end("allocating 1000000 gmemchunks, freeing 500k");
1282
1283         time_start("Using memchunks");
1284         mc = memchunk_new(CHUNK_COUNT, CHUNK_SIZE);
1285         for (i=0;i<1000000;i++) {
1286                 mem = memchunk_alloc(mc);
1287         }
1288         s(sleep(10));
1289         memchunk_destroy(mc);
1290         time_end("allocating 1000000 memchunks");
1291
1292         time_start("Using gmemchunks");
1293         gmc = g_mem_chunk_new("memchunk", CHUNK_SIZE, CHUNK_COUNT*CHUNK_SIZE, G_ALLOC_ONLY);
1294         for (i=0;i<1000000;i++) {
1295                 mem = g_mem_chunk_alloc(gmc);
1296         }
1297         s(sleep(10));
1298         g_mem_chunk_destroy(gmc);
1299         time_end("allocating 1000000 gmemchunks");
1300
1301         time_start("Using malloc");
1302         for (i=0;i<1000000;i++) {
1303                 malloc(CHUNK_SIZE);
1304         }
1305         time_end("allocating 1000000 malloc");
1306 #endif
1307
1308 }
1309
1310 #endif