1298504Ssobomax/* 2298504Ssobomax * Copyright (c) 2004-2016 Maxim Sobolev <sobomax@FreeBSD.org> 3298504Ssobomax * All rights reserved. 4298504Ssobomax * 5298504Ssobomax * Redistribution and use in source and binary forms, with or without 6298504Ssobomax * modification, are permitted provided that the following conditions 7298504Ssobomax * are met: 8298504Ssobomax * 1. Redistributions of source code must retain the above copyright 9298504Ssobomax * notice, this list of conditions and the following disclaimer. 10298504Ssobomax * 2. Redistributions in binary form must reproduce the above copyright 11298504Ssobomax * notice, this list of conditions and the following disclaimer in the 12298504Ssobomax * documentation and/or other materials provided with the distribution. 13298504Ssobomax * 14298504Ssobomax * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15298504Ssobomax * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16298504Ssobomax * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17298504Ssobomax * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18298504Ssobomax * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19298504Ssobomax * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20298504Ssobomax * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21298504Ssobomax * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22298504Ssobomax * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23298504Ssobomax * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24298504Ssobomax * SUCH DAMAGE. 25298504Ssobomax */ 26298504Ssobomax 27298504Ssobomax#include <sys/cdefs.h> 28298504Ssobomax__FBSDID("$FreeBSD: releng/11.0/usr.bin/mkuzip/mkuz_fqueue.c 298504 2016-04-23 07:23:43Z sobomax $"); 29298504Ssobomax 30298504Ssobomax#include <err.h> 31298504Ssobomax#include <pthread.h> 32298504Ssobomax#include <stdint.h> 33298504Ssobomax#include <stdlib.h> 34298504Ssobomax 35298504Ssobomax#if defined(MKUZ_DEBUG) 36298504Ssobomax# include <assert.h> 37298504Ssobomax#endif 38298504Ssobomax 39298504Ssobomax#include "mkuzip.h" 40298504Ssobomax#include "mkuz_fqueue.h" 41298504Ssobomax#include "mkuz_conveyor.h" 42298504Ssobomax#include "mkuz_blk.h" 43298504Ssobomax#include "mkuz_blk_chain.h" 44298504Ssobomax 45298504Ssobomaxstruct mkuz_fifo_queue * 46298504Ssobomaxmkuz_fqueue_ctor(int wakeup_len) 47298504Ssobomax{ 48298504Ssobomax struct mkuz_fifo_queue *fqp; 49298504Ssobomax 50298504Ssobomax fqp = mkuz_safe_zmalloc(sizeof(struct mkuz_fifo_queue)); 51298504Ssobomax fqp->wakeup_len = wakeup_len; 52298504Ssobomax if (pthread_mutex_init(&fqp->mtx, NULL) != 0) { 53298504Ssobomax errx(1, "pthread_mutex_init() failed"); 54298504Ssobomax } 55298504Ssobomax if (pthread_cond_init(&fqp->cvar, NULL) != 0) { 56298504Ssobomax errx(1, "pthread_cond_init() failed"); 57298504Ssobomax } 58298504Ssobomax return (fqp); 59298504Ssobomax} 60298504Ssobomax 61298504Ssobomaxvoid 62298504Ssobomaxmkuz_fqueue_enq(struct mkuz_fifo_queue *fqp, struct mkuz_blk *bp) 63298504Ssobomax{ 64298504Ssobomax struct mkuz_bchain_link *ip; 65298504Ssobomax 66298504Ssobomax ip = mkuz_safe_zmalloc(sizeof(struct mkuz_bchain_link)); 67298504Ssobomax ip->this = bp; 68298504Ssobomax 69298504Ssobomax pthread_mutex_lock(&fqp->mtx); 70298504Ssobomax if (fqp->first != NULL) { 71298504Ssobomax fqp->first->prev = ip; 72298504Ssobomax } else { 73298504Ssobomax fqp->last = ip; 74298504Ssobomax } 75298504Ssobomax fqp->first = ip; 76298504Ssobomax fqp->length += 1; 77298504Ssobomax if (fqp->length >= fqp->wakeup_len) { 78298504Ssobomax pthread_cond_signal(&fqp->cvar); 79298504Ssobomax } 80298504Ssobomax pthread_mutex_unlock(&fqp->mtx); 81298504Ssobomax} 82298504Ssobomax 83298504Ssobomax#if defined(NOTYET) 84298504Ssobomaxint 85298504Ssobomaxmkuz_fqueue_enq_all(struct mkuz_fifo_queue *fqp, struct mkuz_bchain_link *cip_f, 86298504Ssobomax struct mkuz_bchain_link *cip_l, int clen) 87298504Ssobomax{ 88298504Ssobomax int rval; 89298504Ssobomax 90298504Ssobomax pthread_mutex_lock(&fqp->mtx); 91298504Ssobomax if (fqp->first != NULL) { 92298504Ssobomax fqp->first->prev = cip_l; 93298504Ssobomax } else { 94298504Ssobomax fqp->last = cip_l; 95298504Ssobomax } 96298504Ssobomax fqp->first = cip_f; 97298504Ssobomax fqp->length += clen; 98298504Ssobomax rval = fqp->length; 99298504Ssobomax if (fqp->length >= fqp->wakeup_len) { 100298504Ssobomax pthread_cond_signal(&fqp->cvar); 101298504Ssobomax } 102298504Ssobomax pthread_mutex_unlock(&fqp->mtx); 103298504Ssobomax return (rval); 104298504Ssobomax} 105298504Ssobomax#endif 106298504Ssobomax 107298504Ssobomaxstatic int 108298504Ssobomaxmkuz_fqueue_check(struct mkuz_fifo_queue *fqp, cmp_cb_t cmp_cb, void *cap) 109298504Ssobomax{ 110298504Ssobomax struct mkuz_bchain_link *ip; 111298504Ssobomax 112298504Ssobomax for (ip = fqp->last; ip != NULL; ip = ip->prev) { 113298504Ssobomax if (cmp_cb(ip->this, cap)) { 114298504Ssobomax return (1); 115298504Ssobomax } 116298504Ssobomax } 117298504Ssobomax return (0); 118298504Ssobomax} 119298504Ssobomax 120298504Ssobomaxstruct mkuz_blk * 121298504Ssobomaxmkuz_fqueue_deq_when(struct mkuz_fifo_queue *fqp, cmp_cb_t cmp_cb, void *cap) 122298504Ssobomax{ 123298504Ssobomax struct mkuz_bchain_link *ip, *newlast, *newfirst, *mip; 124298504Ssobomax struct mkuz_blk *bp; 125298504Ssobomax 126298504Ssobomax pthread_mutex_lock(&fqp->mtx); 127298504Ssobomax while (fqp->last == NULL || !mkuz_fqueue_check(fqp, cmp_cb, cap)) { 128298504Ssobomax pthread_cond_wait(&fqp->cvar, &fqp->mtx); 129298504Ssobomax } 130298504Ssobomax if (cmp_cb(fqp->last->this, cap)) { 131298504Ssobomax mip = fqp->last; 132298504Ssobomax fqp->last = mip->prev; 133298504Ssobomax if (fqp->last == NULL) { 134298504Ssobomax#if defined(MKUZ_DEBUG) 135298504Ssobomax assert(fqp->length == 1); 136298504Ssobomax#endif 137298504Ssobomax fqp->first = NULL; 138298504Ssobomax } 139298504Ssobomax } else { 140298504Ssobomax#if defined(MKUZ_DEBUG) 141298504Ssobomax assert(fqp->length > 1); 142298504Ssobomax#endif 143298504Ssobomax newfirst = newlast = fqp->last; 144298504Ssobomax mip = NULL; 145298504Ssobomax for (ip = fqp->last->prev; ip != NULL; ip = ip->prev) { 146298504Ssobomax if (cmp_cb(ip->this, cap)) { 147298504Ssobomax mip = ip; 148298504Ssobomax continue; 149298504Ssobomax } 150298504Ssobomax newfirst->prev = ip; 151298504Ssobomax newfirst = ip; 152298504Ssobomax } 153298504Ssobomax newfirst->prev = NULL; 154298504Ssobomax fqp->first = newfirst; 155298504Ssobomax fqp->last = newlast; 156298504Ssobomax } 157298504Ssobomax fqp->length -= 1; 158298504Ssobomax pthread_mutex_unlock(&fqp->mtx); 159298504Ssobomax bp = mip->this; 160298504Ssobomax free(mip); 161298504Ssobomax 162298504Ssobomax return bp; 163298504Ssobomax} 164298504Ssobomax 165298504Ssobomaxstruct mkuz_blk * 166298504Ssobomaxmkuz_fqueue_deq(struct mkuz_fifo_queue *fqp) 167298504Ssobomax{ 168298504Ssobomax struct mkuz_bchain_link *ip; 169298504Ssobomax struct mkuz_blk *bp; 170298504Ssobomax 171298504Ssobomax pthread_mutex_lock(&fqp->mtx); 172298504Ssobomax while (fqp->last == NULL) { 173298504Ssobomax pthread_cond_wait(&fqp->cvar, &fqp->mtx); 174298504Ssobomax } 175298504Ssobomax#if defined(MKUZ_DEBUG) 176298504Ssobomax assert(fqp->length > 0); 177298504Ssobomax#endif 178298504Ssobomax ip = fqp->last; 179298504Ssobomax fqp->last = ip->prev; 180298504Ssobomax if (fqp->last == NULL) { 181298504Ssobomax#if defined(MKUZ_DEBUG) 182298504Ssobomax assert(fqp->length == 1); 183298504Ssobomax#endif 184298504Ssobomax fqp->first = NULL; 185298504Ssobomax } 186298504Ssobomax fqp->length -= 1; 187298504Ssobomax pthread_mutex_unlock(&fqp->mtx); 188298504Ssobomax bp = ip->this; 189298504Ssobomax free(ip); 190298504Ssobomax 191298504Ssobomax return bp; 192298504Ssobomax} 193298504Ssobomax 194298504Ssobomax#if defined(NOTYET) 195298504Ssobomaxstruct mkuz_bchain_link * 196298504Ssobomaxmkuz_fqueue_deq_all(struct mkuz_fifo_queue *fqp, int *rclen) 197298504Ssobomax{ 198298504Ssobomax struct mkuz_bchain_link *rchain; 199298504Ssobomax 200298504Ssobomax pthread_mutex_lock(&fqp->mtx); 201298504Ssobomax while (fqp->last == NULL) { 202298504Ssobomax pthread_cond_wait(&fqp->cvar, &fqp->mtx); 203298504Ssobomax } 204298504Ssobomax#if defined(MKUZ_DEBUG) 205298504Ssobomax assert(fqp->length > 0); 206298504Ssobomax#endif 207298504Ssobomax rchain = fqp->last; 208298504Ssobomax fqp->first = fqp->last = NULL; 209298504Ssobomax *rclen = fqp->length; 210298504Ssobomax fqp->length = 0; 211298504Ssobomax pthread_mutex_unlock(&fqp->mtx); 212298504Ssobomax return (rchain); 213298504Ssobomax} 214298504Ssobomax#endif 215