doorbell

annotate doorbelld/src/dynarr.c @ 2:d3f2a2b19504

find changesets by author, revision, files, or words in the commit message
doorbell server under construction
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 13 Mar 2016 07:56:03 +0200
parents
children
rev   line source
nuclear@2 1 /* dynarr - dynamic resizable C array data structure
nuclear@2 2 * author: John Tsiombikas <nuclear@member.fsf.org>
nuclear@2 3 * license: public domain
nuclear@2 4 */
nuclear@2 5 #include <stdio.h>
nuclear@2 6 #include <stdlib.h>
nuclear@2 7 #include <string.h>
nuclear@2 8 #include "dynarr.h"
nuclear@2 9
nuclear@2 10 /* The array descriptor keeps auxilliary information needed to manipulate
nuclear@2 11 * the dynamic array. It's allocated adjacent to the array buffer.
nuclear@2 12 */
nuclear@2 13 struct arrdesc {
nuclear@2 14 int nelem, szelem;
nuclear@2 15 int max_elem;
nuclear@2 16 int bufsz; /* not including the descriptor */
nuclear@2 17 };
nuclear@2 18
nuclear@2 19 #define DESC(x) ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
nuclear@2 20
nuclear@2 21 void *dynarr_alloc(int elem, int szelem)
nuclear@2 22 {
nuclear@2 23 struct arrdesc *desc;
nuclear@2 24
nuclear@2 25 if(!(desc = malloc(elem * szelem + sizeof *desc))) {
nuclear@2 26 return 0;
nuclear@2 27 }
nuclear@2 28 desc->nelem = desc->max_elem = elem;
nuclear@2 29 desc->szelem = szelem;
nuclear@2 30 desc->bufsz = elem * szelem;
nuclear@2 31 return (char*)desc + sizeof *desc;
nuclear@2 32 }
nuclear@2 33
nuclear@2 34 void dynarr_free(void *da)
nuclear@2 35 {
nuclear@2 36 if(da) {
nuclear@2 37 free(DESC(da));
nuclear@2 38 }
nuclear@2 39 }
nuclear@2 40
nuclear@2 41 void *dynarr_resize(void *da, int elem)
nuclear@2 42 {
nuclear@2 43 int newsz;
nuclear@2 44 void *tmp;
nuclear@2 45 struct arrdesc *desc;
nuclear@2 46
nuclear@2 47 if(!da) return 0;
nuclear@2 48 desc = DESC(da);
nuclear@2 49
nuclear@2 50 newsz = desc->szelem * elem;
nuclear@2 51
nuclear@2 52 if(!(tmp = realloc(desc, newsz + sizeof *desc))) {
nuclear@2 53 return 0;
nuclear@2 54 }
nuclear@2 55 desc = tmp;
nuclear@2 56
nuclear@2 57 desc->nelem = desc->max_elem = elem;
nuclear@2 58 desc->bufsz = newsz;
nuclear@2 59 return (char*)desc + sizeof *desc;
nuclear@2 60 }
nuclear@2 61
nuclear@2 62 int dynarr_empty(void *da)
nuclear@2 63 {
nuclear@2 64 return DESC(da)->nelem ? 0 : 1;
nuclear@2 65 }
nuclear@2 66
nuclear@2 67 int dynarr_size(void *da)
nuclear@2 68 {
nuclear@2 69 return DESC(da)->nelem;
nuclear@2 70 }
nuclear@2 71
nuclear@2 72
nuclear@2 73 /* stack semantics */
nuclear@2 74 void *dynarr_push(void *da, void *item)
nuclear@2 75 {
nuclear@2 76 struct arrdesc *desc;
nuclear@2 77 int nelem;
nuclear@2 78
nuclear@2 79 desc = DESC(da);
nuclear@2 80 nelem = desc->nelem;
nuclear@2 81
nuclear@2 82 if(nelem >= desc->max_elem) {
nuclear@2 83 /* need to resize */
nuclear@2 84 struct arrdesc *tmp;
nuclear@2 85 int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
nuclear@2 86
nuclear@2 87 if(!(tmp = dynarr_resize(da, newsz))) {
nuclear@2 88 fprintf(stderr, "failed to resize\n");
nuclear@2 89 return da;
nuclear@2 90 }
nuclear@2 91 da = tmp;
nuclear@2 92 desc = DESC(da);
nuclear@2 93 desc->nelem = nelem;
nuclear@2 94 }
nuclear@2 95
nuclear@2 96 if(item) {
nuclear@2 97 memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem);
nuclear@2 98 }
nuclear@2 99 return da;
nuclear@2 100 }
nuclear@2 101
nuclear@2 102 void *dynarr_pop(void *da)
nuclear@2 103 {
nuclear@2 104 struct arrdesc *desc;
nuclear@2 105 int nelem;
nuclear@2 106
nuclear@2 107 desc = DESC(da);
nuclear@2 108 nelem = desc->nelem;
nuclear@2 109
nuclear@2 110 if(!nelem) return da;
nuclear@2 111
nuclear@2 112 if(nelem <= desc->max_elem / 3) {
nuclear@2 113 /* reclaim space */
nuclear@2 114 struct arrdesc *tmp;
nuclear@2 115 int newsz = desc->max_elem / 2;
nuclear@2 116
nuclear@2 117 if(!(tmp = dynarr_resize(da, newsz))) {
nuclear@2 118 fprintf(stderr, "failed to resize\n");
nuclear@2 119 return da;
nuclear@2 120 }
nuclear@2 121 da = tmp;
nuclear@2 122 desc = DESC(da);
nuclear@2 123 desc->nelem = nelem;
nuclear@2 124 }
nuclear@2 125 desc->nelem--;
nuclear@2 126
nuclear@2 127 return da;
nuclear@2 128 }