diff options
Diffstat (limited to 'libs/libcurl/src/uint-table.c')
-rw-r--r-- | libs/libcurl/src/uint-table.c | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/libs/libcurl/src/uint-table.c b/libs/libcurl/src/uint-table.c new file mode 100644 index 0000000000..c40d538348 --- /dev/null +++ b/libs/libcurl/src/uint-table.c @@ -0,0 +1,214 @@ +/***************************************************************************
+ * _ _ ____ _
+ * 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
+
+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 || (nrows == UINT_MAX))
+ 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));
+}
+
+
+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; /* always invalid */
+ 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;
+}
|