| /*************************************************************************** |
| * _ _ ____ _ |
| * Project ___| | | | _ \| | |
| * / __| | | | |_) | | |
| * | (__| |_| | _ <| |___ |
| * \___|\___/|_| \_\_____| |
| * |
| * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al. |
| * |
| * This software is licensed as described in the file COPYING, which |
| * you should have received as part of this distribution. The terms |
| * are also available at https://curl.se/docs/copyright.html. |
| * |
| * You may opt to use, copy, modify, merge, publish, distribute and/or sell |
| * copies of the Software, and permit persons to whom the Software is |
| * furnished to do so, under the terms of the COPYING file. |
| * |
| * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY |
| * KIND, either express or implied. |
| * |
| * SPDX-License-Identifier: curl |
| * |
| ***************************************************************************/ |
| |
| #include "curl_setup.h" |
| #include "uint-table.h" |
| |
| /* The last 3 #include files should be in this order */ |
| #include "curl_printf.h" |
| #include "curl_memory.h" |
| #include "memdebug.h" |
| |
| #ifdef DEBUGBUILD |
| #define CURL_UINT_TBL_MAGIC 0x62757473 |
| #endif |
| |
| /* Clear the table, making it empty. */ |
| UNITTEST void Curl_uint_tbl_clear(struct uint_tbl *tbl); |
| |
| void Curl_uint_tbl_init(struct uint_tbl *tbl, |
| Curl_uint_tbl_entry_dtor *entry_dtor) |
| { |
| memset(tbl, 0, sizeof(*tbl)); |
| tbl->entry_dtor = entry_dtor; |
| tbl->last_key_added = UINT_MAX; |
| #ifdef DEBUGBUILD |
| tbl->init = CURL_UINT_TBL_MAGIC; |
| #endif |
| } |
| |
| |
| static void uint_tbl_clear_rows(struct uint_tbl *tbl, |
| unsigned int from, |
| unsigned int upto_excluding) |
| { |
| unsigned int i, end; |
| |
| end = CURLMIN(upto_excluding, tbl->nrows); |
| for(i = from; i < end; ++i) { |
| if(tbl->rows[i]) { |
| if(tbl->entry_dtor) |
| tbl->entry_dtor(i, tbl->rows[i]); |
| tbl->rows[i] = NULL; |
| tbl->nentries--; |
| } |
| } |
| } |
| |
| |
| CURLcode Curl_uint_tbl_resize(struct uint_tbl *tbl, unsigned int nrows) |
| { |
| /* we use `tbl->nrows + 1` during iteration, want that to work */ |
| DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); |
| if(!nrows) |
| return CURLE_BAD_FUNCTION_ARGUMENT; |
| if(nrows != tbl->nrows) { |
| void **rows = calloc(nrows, sizeof(void *)); |
| if(!rows) |
| return CURLE_OUT_OF_MEMORY; |
| if(tbl->rows) { |
| memcpy(rows, tbl->rows, (CURLMIN(nrows, tbl->nrows) * sizeof(void *))); |
| if(nrows < tbl->nrows) |
| uint_tbl_clear_rows(tbl, nrows, tbl->nrows); |
| free(tbl->rows); |
| } |
| tbl->rows = rows; |
| tbl->nrows = nrows; |
| } |
| return CURLE_OK; |
| } |
| |
| |
| void Curl_uint_tbl_destroy(struct uint_tbl *tbl) |
| { |
| DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); |
| Curl_uint_tbl_clear(tbl); |
| free(tbl->rows); |
| memset(tbl, 0, sizeof(*tbl)); |
| } |
| |
| UNITTEST void Curl_uint_tbl_clear(struct uint_tbl *tbl) |
| { |
| DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); |
| uint_tbl_clear_rows(tbl, 0, tbl->nrows); |
| DEBUGASSERT(!tbl->nentries); |
| tbl->last_key_added = UINT_MAX; |
| } |
| |
| |
| unsigned int Curl_uint_tbl_capacity(struct uint_tbl *tbl) |
| { |
| return tbl->nrows; |
| } |
| |
| |
| unsigned int Curl_uint_tbl_count(struct uint_tbl *tbl) |
| { |
| return tbl->nentries; |
| } |
| |
| |
| void *Curl_uint_tbl_get(struct uint_tbl *tbl, unsigned int key) |
| { |
| return (key < tbl->nrows) ? tbl->rows[key] : NULL; |
| } |
| |
| |
| bool Curl_uint_tbl_add(struct uint_tbl *tbl, void *entry, unsigned int *pkey) |
| { |
| unsigned int key, start_pos; |
| |
| DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); |
| if(!entry || !pkey) |
| return FALSE; |
| *pkey = UINT_MAX; |
| if(tbl->nentries == tbl->nrows) /* full */ |
| return FALSE; |
| |
| start_pos = CURLMIN(tbl->last_key_added, tbl->nrows) + 1; |
| for(key = start_pos; key < tbl->nrows; ++key) { |
| if(!tbl->rows[key]) { |
| tbl->rows[key] = entry; |
| tbl->nentries++; |
| tbl->last_key_added = key; |
| *pkey = key; |
| return TRUE; |
| } |
| } |
| /* no free entry at or above tbl->maybe_next_key, wrap around */ |
| for(key = 0; key < start_pos; ++key) { |
| if(!tbl->rows[key]) { |
| tbl->rows[key] = entry; |
| tbl->nentries++; |
| tbl->last_key_added = key; |
| *pkey = key; |
| return TRUE; |
| } |
| } |
| /* Did not find any free row? Should not happen */ |
| DEBUGASSERT(0); |
| return FALSE; |
| } |
| |
| |
| void Curl_uint_tbl_remove(struct uint_tbl *tbl, unsigned int key) |
| { |
| uint_tbl_clear_rows(tbl, key, key + 1); |
| } |
| |
| |
| bool Curl_uint_tbl_contains(struct uint_tbl *tbl, unsigned int key) |
| { |
| return (key < tbl->nrows) ? !!tbl->rows[key] : FALSE; |
| } |
| |
| |
| static bool uint_tbl_next_at(struct uint_tbl *tbl, unsigned int key, |
| unsigned int *pkey, void **pentry) |
| { |
| for(; key < tbl->nrows; ++key) { |
| if(tbl->rows[key]) { |
| *pkey = key; |
| *pentry = tbl->rows[key]; |
| return TRUE; |
| } |
| } |
| *pkey = UINT_MAX; /* always invalid */ |
| *pentry = NULL; |
| return FALSE; |
| } |
| |
| bool Curl_uint_tbl_first(struct uint_tbl *tbl, |
| unsigned int *pkey, void **pentry) |
| { |
| if(!pkey || !pentry) |
| return FALSE; |
| if(tbl->nentries && uint_tbl_next_at(tbl, 0, pkey, pentry)) |
| return TRUE; |
| DEBUGASSERT(!tbl->nentries); |
| *pkey = UINT_MAX; /* always invalid */ |
| *pentry = NULL; |
| return FALSE; |
| } |
| |
| |
| bool Curl_uint_tbl_next(struct uint_tbl *tbl, unsigned int last_key, |
| unsigned int *pkey, void **pentry) |
| { |
| if(!pkey || !pentry) |
| return FALSE; |
| if(uint_tbl_next_at(tbl, last_key + 1, pkey, pentry)) |
| return TRUE; |
| *pkey = UINT_MAX; /* always invalid */ |
| *pentry = NULL; |
| return FALSE; |
| } |