From 97e97302f5ffdd03a10a083e9924d5bc41b43061 Mon Sep 17 00:00:00 2001 From: alex Date: Fri, 4 Mar 2022 18:23:07 -0800 Subject: [PATCH] ... --- inc/pqueue.h | 1 + src/pqueue.c | 74 ++++++++++++++----- test/unit/Makefile.am | 8 +- test/unit/pqueue.tests.c | 155 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 220 insertions(+), 18 deletions(-) create mode 100644 test/unit/pqueue.tests.c diff --git a/inc/pqueue.h b/inc/pqueue.h index f442908..85c33a7 100644 --- a/inc/pqueue.h +++ b/inc/pqueue.h @@ -18,6 +18,7 @@ struct priority_queue { int pqueue_access(struct priority_queue*,const void*,size_t); int pqueue_add(struct priority_queue*,const void*,size_t,void*); +void *pqueue_evict(struct priority_queue*,const void*,size_t); void *pqueue_find(struct priority_queue*,const void*,size_t); void pqueue_free(struct priority_queue*); int pqueue_init(struct priority_queue**,size_t); diff --git a/src/pqueue.c b/src/pqueue.c index e749de0..0951cea 100644 --- a/src/pqueue.c +++ b/src/pqueue.c @@ -1,6 +1,7 @@ #include -static int pqueue_swap(struct priority_queue*,size_t,size_t); +static void pqueue_swap(struct priority_queue*,size_t,size_t); +static int priority_queue_entry_init(struct priority_queue_entry**); int pqueue_access(struct priority_queue *queue, const void *key, size_t key_size) { struct priority_queue_entry *p; @@ -16,9 +17,8 @@ int pqueue_access(struct priority_queue *queue, const void *key, size_t key_size index = p->index; while(index>0) { - if(queue->queue[index-1]->prioritypriority) { - index--; - } + if(queue->queue[index-1]->priority>=p->priority) { break; } + index--; } if(p->index!=index) { @@ -29,20 +29,34 @@ int pqueue_access(struct priority_queue *queue, const void *key, size_t key_size } int pqueue_add(struct priority_queue *queue, const void *key, size_t key_size, void *value) { - struct priority_queue_entry *p; + struct priority_queue_entry *to_add; + int i; if(NULL==queue) { return -1; } if((NULL==key)||(0==key_size)) { return -1; } - if(hashmap_find(queue->map,key,key_size)!=NULL) { return 0; } - - if(priority_queue_entry_init(&p)<0) { return -1; } - p->p = value; + // reject if queue is full + if(queue->queue[queue->size-1]!=NULL) { return -1; } + + if(priority_queue_entry_init(&to_add)<0) { return -1; } + to_add->p = value; + + if((i = hashmap_insert(queue->map,key,key_size,to_add))<=0) { + if(i<0) { return -1; } + /* + * This is necessary because resizing hashmap + * requires type/key information and can't be + * abstracted out. pqueue_add() uses must be prepared + * to resize hashmap out of band. + */ + free(to_add); + return 0; + } for(size_t i=0;isize;i++) { - if(queue->queue[i]!=NULL) { - queue->queue[i] = p; - p->index = i; + if(NULL==queue->queue[i]) { + queue->queue[i] = to_add; + to_add->index = i; return 1; } } @@ -54,10 +68,11 @@ void *pqueue_evict(struct priority_queue *queue, const void *key, size_t key_siz struct priority_queue_entry *entry; void *p; - entry = hashmap_find(queue->map,key,key_size); + entry = hashmap_remove(queue->map,key,key_size); if(entry!=NULL) { p = entry->p; + queue->queue[entry->index] = NULL; for(size_t i=entry->index;i<(queue->size-1);i++) { if(NULL==queue->queue[i+1]) { pqueue_swap(queue,entry->index,i+1); @@ -73,7 +88,12 @@ void *pqueue_evict(struct priority_queue *queue, const void *key, size_t key_siz } void *pqueue_find(struct priority_queue *queue, const void *key, size_t key_size) { - return NULL; + struct priority_queue_entry *p; + + p = hashmap_find(queue->map,key,key_size); + if(NULL==p) { return NULL; } + + return p->p; } void pqueue_free(struct priority_queue *queue) { @@ -112,11 +132,31 @@ int pqueue_init(struct priority_queue **p, size_t size) { static void pqueue_swap(struct priority_queue *queue, size_t a, size_t b) { struct priority_queue_entry *p; - queue->queue[a] = p; + p = queue->queue[a]; queue->queue[a] = queue->queue[b]; - queue->queue[a]->index = a; + if(queue->queue[a]!=NULL) { + queue->queue[a]->index = a; + } queue->queue[b] = p; - queue->queue[b]->index = b; + if(queue->queue[b]!=NULL) { + queue->queue[b]->index = b; + } +} + +static int priority_queue_entry_init(struct priority_queue_entry **p) { + if(NULL==p) { return -1; } + + *p = malloc(sizeof(struct priority_queue_entry)); + if(NULL==(*p)) { + perror("malloc"); + return -1; + } + + (*p)->p = NULL; + (*p)->priority = 0; + (*p)->index = 0; + + return 1; } diff --git a/test/unit/Makefile.am b/test/unit/Makefile.am index 0719cdd..70f810d 100644 --- a/test/unit/Makefile.am +++ b/test/unit/Makefile.am @@ -13,7 +13,7 @@ AM_CPPFLAGS += \ -DNDEBUG endif -check_PROGRAMS = bencode.tests block.tests feed.tests file.tests fs.concat.tests fs.filter.tests hash.tests hashmap.tests meta.tests opt.tests peer.tests rss.tests session.tests torrent.tests tree.tests +check_PROGRAMS = bencode.tests block.tests feed.tests file.tests fs.concat.tests fs.filter.tests hash.tests hashmap.tests meta.tests opt.tests peer.tests pqueue.tests rss.tests session.tests torrent.tests tree.tests TESTS = $(check_PROGRAMS) if ENABLE_MEMCHECK @@ -142,6 +142,12 @@ peer_tests_SOURCES = \ $(common_SOURCES) \ peer.tests.c +pqueue_tests_SOURCES = \ + $(common_SOURCES) \ + pqueue.tests.c \ + $(top_srcdir)/src/hashmap.c \ + $(top_srcdir)/src/pqueue.c + rss_tests_SOURCES = \ $(common_SOURCES) \ rss.tests.c \ diff --git a/test/unit/pqueue.tests.c b/test/unit/pqueue.tests.c new file mode 100644 index 0000000..4674a90 --- /dev/null +++ b/test/unit/pqueue.tests.c @@ -0,0 +1,155 @@ +#include + +#include + +int main(); +static void pqueue_access_basic_test(); +static void pqueue_add_basic_test(); +static void pqueue_evict_basic_test(); +static void pqueue_find_basic_test(); +static void pqueue_init_basic_test(); + +int main() { + setup_env(); + + pqueue_init_basic_test(); + + pqueue_access_basic_test(); + pqueue_add_basic_test(); + pqueue_evict_basic_test(); + pqueue_find_basic_test(); + + clean_env(); + + return EXIT_SUCCESS; +} + +static void pqueue_access_basic_test() { + struct priority_queue *queue; + int a, b, c, expected; + + assert(1==pqueue_init(&queue,10)); + memset(queue->map->key,0,crypto_shorthash_KEYBYTES); + + a = 1; + b = 2; + c = 3; + + assert(1==pqueue_add(queue,&a,sizeof(int),&a)); + assert(1==pqueue_add(queue,&b,sizeof(int),&b)); + + assert(1==pqueue_access(queue,&a,sizeof(int))); + assert(1==pqueue_access(queue,&b,sizeof(int))); + assert(0==pqueue_access(queue,&c,sizeof(int))); + + expected = 1; + for(size_t i=0;i<((rand()%256)+1);i++) { + assert(1==pqueue_access(queue,&b,sizeof(int))); + expected++; + } + + assert(queue->queue[0]->p==&b); + assert(queue->queue[0]->priority==expected); + assert(queue->queue[1]->p==&a); + + pqueue_free(queue); +} + +static void pqueue_add_basic_test() { + struct priority_queue *queue; + int a, b, c, d; + + assert(1==pqueue_init(&queue,10)); + memset(queue->map->key,0,crypto_shorthash_KEYBYTES); + + a = 1; + b = 2; + c = 3; + d = 4; + + assert(-1==pqueue_add(NULL,NULL,0,NULL)); + assert(-1==pqueue_add(queue,NULL,0,NULL)); + assert(-1==pqueue_add(queue,&a,0,NULL)); + + assert(1==pqueue_add(queue,&a,sizeof(int),&a)); + assert(1==pqueue_add(queue,&b,sizeof(int),&b)); + assert(1==pqueue_add(queue,&c,sizeof(int),&c)); + + queue->size = 3; + assert(-1==pqueue_add(queue,&d,sizeof(int),&d)); + queue->size = 10; + assert(1==pqueue_add(queue,&d,sizeof(int),&d)); + + assert(0==pqueue_add(queue,&a,sizeof(int),&a)); + + assert(queue->queue[0]->p==&a); + assert(queue->queue[1]->p==&b); + assert(queue->queue[2]->p==&c); + + pqueue_free(queue); +} + +static void pqueue_evict_basic_test() { + struct priority_queue *queue; + int a, b, c, d; + + assert(1==pqueue_init(&queue,10)); + memset(queue->map->key,0,crypto_shorthash_KEYBYTES); + + a = 1; + b = 2; + c = 3; + d = 4; + + assert(1==pqueue_add(queue,&a,sizeof(int),&a)); + assert(1==pqueue_add(queue,&b,sizeof(int),&b)); + assert(1==pqueue_add(queue,&c,sizeof(int),&c)); + + assert(NULL==pqueue_evict(queue,&d,sizeof(int))); + + assert(&a==pqueue_evict(queue,&a,sizeof(int))); + assert(&b==pqueue_evict(queue,&b,sizeof(int))); + assert(&c==pqueue_evict(queue,&c,sizeof(int))); + + for(size_t i=0;i<10;i++) { + assert(queue->queue[i]==NULL); + assert(queue->map->map[i]==NULL); + } + + pqueue_free(queue); +} + +static void pqueue_find_basic_test() { + struct priority_queue *queue; + int a, b, c, d; + + assert(1==pqueue_init(&queue,10)); + memset(queue->map->key,0,crypto_shorthash_KEYBYTES); + + a = 1; + b = 2; + c = 3; + d = 4; + + assert(1==pqueue_add(queue,&a,sizeof(int),&a)); + assert(1==pqueue_add(queue,&b,sizeof(int),&b)); + assert(1==pqueue_add(queue,&c,sizeof(int),&c)); + + assert(&a==pqueue_find(queue,&a,sizeof(int))); + assert(&b==pqueue_find(queue,&b,sizeof(int))); + assert(&c==pqueue_find(queue,&c,sizeof(int))); + assert(NULL==pqueue_find(queue,&d,sizeof(int))); + + pqueue_free(queue); +} + +static void pqueue_init_basic_test() { + struct priority_queue *p; + + assert(pqueue_init(NULL,0)==-1); + assert(pqueue_init(&p,0)==-1); + + assert(pqueue_init(&p,10)==1); + + pqueue_free(p); +} -- 2.39.5