Created
March 9, 2012 16:02
-
-
Save darconeous/2007249 to your computer and use it in GitHub Desktop.
Useful Public-Domain C Stuff
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file assert-macros.h | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
** | |
** See <http://www.deepdarc.com/> for other cool stuff. | |
** | |
** ------------------------------------------------------------------- | |
** | |
** See <http://www.mactech.com/articles/develop/issue_11/Parent_final.html> | |
** for an explanation about how to use these macros and justification | |
** for using this pattern in general. | |
*/ | |
#ifndef __DARC_ASSERT_MACROS__ | |
#define __DARC_ASSERT_MACROS__ | |
#if CONTIKI | |
#define assert_error_stream stdout | |
#else | |
#define assert_error_stream stderr | |
#endif | |
#if !DEBUG && !defined(NDEBUG) | |
#define NDEBUG 1 | |
#endif | |
#if ASSERT_MACROS_USE_SYSLOG | |
#include <syslog.h> | |
#endif | |
#if HAS_ASSERTMACROS_H | |
#include <AssertMacros.h> | |
#else | |
#include <stdio.h> | |
#include <assert.h> | |
#if !DEBUG && !VERBOSE_DEBUG | |
#define assert_printf(fmt, ...) do { } while(0) | |
#define check_string(c, s) do { } while(0) | |
#define require_action_string(c, l, a, s) \ | |
do { if(!(c)) { \ | |
a; goto l; \ | |
} \ | |
} while(0) | |
#else | |
#if __AVR__ | |
#define assert_printf(fmt, ...) \ | |
fprintf_P(assert_error_stream, \ | |
PSTR(__FILE__ ":%d: "fmt"\n"), \ | |
__LINE__, \ | |
__VA_ARGS__) | |
#else | |
#if ASSERT_MACROS_USE_SYSLOG | |
#define assert_printf(fmt, ...) \ | |
syslog(7, \ | |
__FILE__ ":%d: "fmt"\n", \ | |
__LINE__, \ | |
__VA_ARGS__) | |
#else | |
#define assert_printf(fmt, ...) \ | |
fprintf(assert_error_stream, \ | |
__FILE__ ":%d: "fmt"\n", \ | |
__LINE__, \ | |
__VA_ARGS__) | |
#endif | |
#endif | |
#define check_string(c, s) \ | |
do { if(!(c)) assert_printf("Check Failed (%s)", \ | |
s); } while(0) | |
#define require_action_string(c, l, a, s) \ | |
do { if(!(c)) { \ | |
assert_printf("Requirement Failed (%s)", \ | |
s); a; goto l; \ | |
} \ | |
} while(0) | |
#endif | |
#define check(c) check_string(c, # c) | |
#define check_noerr(c) check((c) == 0) | |
#define require_quiet(c, l) do { if(!(c)) goto l; } while(0) | |
#define require(c, l) require_action_string(c, l, {}, # c) | |
#define require_noerr(c, l) require((c) == 0, l) | |
#define require_action(c, l, a) require_action_string(c, l, a, # c) | |
#define require_string(c, l, s) \ | |
require_action_string(c, l, \ | |
do {} while(0), s) | |
#endif | |
#if OVERRIDE_ASSERT_H | |
#undef assert | |
#undef __assert | |
#define assert(e) \ | |
((void) ((e) ? 0 : __assert (#e, __FILE__, __LINE__))) | |
#define __assert(e, file, line) \ | |
((void)assert_printf ("%s:%u: failed assertion `%s'\n", file, line, e), abort()) | |
#endif // OVERRIDE_ASSERT_H | |
#endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file btree.c | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
** | |
** ------------------------------------------------------------------- | |
** | |
** ## Unit Test ## | |
** | |
** This file includes its own unit test. To compile the unit test, | |
** simply compile this file with the macro BTREE_SELF_TEST set to 1. | |
** For example: | |
** | |
** cc btree.c -Wall -DBTREE_SELF_TEST=1 -o btree | |
** | |
** ## Todo ## | |
** | |
** * Add some sort of automatic tree-balancing algorithm, | |
** like <http://en.wikipedia.org/wiki/Scapegoat_tree>. | |
*/ | |
#include "btree.h" | |
#include <assert.h> | |
int | |
bt_insert( | |
void** bt, | |
void* item, | |
bt_compare_func_t compare_func, | |
bt_delete_func_t delete_func, | |
void* context | |
) { | |
int depth = 0; | |
bt_item_t const item_ = item; | |
bt_item_t location_; | |
again: | |
location_ = *bt; | |
if(location_) { | |
bt_compare_result_t result = | |
(*compare_func)(location_, item_, context); | |
if(result) { | |
// One more step down the rabit hole... | |
item_->parent = location_; | |
bt = (result < 0) ? | |
(void**)&location_->rhs : (void**)&location_->lhs; | |
depth++; | |
goto again; | |
} else if(item_ != location_) { | |
// Item already exists, so we replace. | |
item_->parent = location_->parent; | |
if(item_->parent) { | |
if(location_->parent->rhs == location_) | |
location_->parent->rhs = item; | |
else | |
location_->parent->lhs = item; | |
} | |
item_->lhs = location_->lhs; | |
if(location_->lhs) | |
location_->lhs->parent = item_; | |
item_->rhs = location_->rhs; | |
if(location_->rhs) | |
location_->rhs->parent = item_; | |
*bt = item_; | |
(*delete_func)(location_, context); | |
} | |
} else { | |
// Found ourselves a good spot. Put the item here. | |
*bt = item_; | |
} | |
return depth; | |
} | |
void* | |
bt_find( | |
void*const* bt, | |
const void* item, | |
bt_compare_func_t compare_func, | |
void* context | |
) { | |
bt_item_t location_ = *bt; | |
bt_compare_result_t result = -1; | |
while(location_) { | |
result = (*compare_func)(location_, item, context); | |
if(result) | |
location_ = (result < 0) ? location_->rhs : location_->lhs; | |
else | |
break; | |
} | |
return location_; | |
} | |
bool | |
bt_remove( | |
void** bt, | |
void* item, | |
bt_compare_func_t compare_func, | |
bt_delete_func_t delete_func, | |
void* context | |
) { | |
bt_item_t const item_ = bt_find(bt, item, compare_func, context); | |
if(item_) { | |
if(item_->parent) { | |
bt = (void**)((item_->parent->lhs == item_)?&item_->parent->lhs:&item_->parent->rhs); | |
} | |
if(item_->lhs && !item_->rhs) { | |
*bt = item_->lhs; | |
item_->lhs->parent = item_->parent; | |
} else if(item_->rhs && !item_->lhs) { | |
*bt = item_->rhs; | |
item_->rhs->parent = item_->parent; | |
} else if(!item_->rhs && !item_->lhs) { | |
*bt = NULL; | |
} else { | |
bt_item_t last_item = (bt_item_t)bt_last(item_->lhs); | |
item_->rhs->parent = last_item; | |
last_item->rhs = item_->rhs; | |
*bt = item_->lhs; | |
item_->lhs->parent = item_->parent; | |
} | |
item_->lhs = NULL; | |
item_->rhs = NULL; | |
item_->parent = NULL; | |
if(delete_func) | |
(*delete_func)(item_, context); | |
return true; | |
} | |
return false; | |
} | |
void* | |
bt_first(void* item) { | |
bt_item_t item_ = item; | |
if(item_) | |
while(item_->lhs) | |
item_ = item_->lhs; | |
return (void*)item_; | |
} | |
void* | |
bt_next(void* item) { | |
bt_item_t item_ = item; | |
if(item) { | |
if(item_->rhs) { | |
item_ = bt_first(item_->rhs); | |
} else { | |
while(item_->parent && (item_->parent->rhs == item_)) { | |
item_ = item_->parent; | |
} | |
item_ = item_->parent; | |
} | |
} | |
return (void*)item_; | |
} | |
void* | |
bt_last(void* item) { | |
bt_item_t item_ = item; | |
if(item_) | |
while(item_->rhs) | |
item_ = item_->rhs; | |
return (void*)item_; | |
} | |
void* | |
bt_prev(void* item) { | |
bt_item_t item_ = item; | |
if(item) { | |
if(item_->lhs) { | |
item_ = bt_last(item_->lhs); | |
} else { | |
while(item_->parent && (item_->parent->lhs == item_)) { | |
item_ = item_->parent; | |
} | |
item_ = item_->parent; | |
} | |
} | |
return (void*)item_; | |
} | |
size_t | |
bt_count(void*const* bt) { | |
size_t ret = 0; | |
if(*bt) { | |
bt_item_t iter = bt_first(*bt); | |
const bt_item_t end = bt_last(*bt); | |
// We start at 1 here because our end | |
// iterator is pointing at the last | |
// item instead of the end marker. | |
// Without this, this method will | |
// be off by 1. | |
ret = 1; | |
for(; iter != end; iter = bt_next(iter)) | |
ret++; | |
} | |
return ret; | |
} | |
void | |
bt_rotate_right(void** bt) { | |
bt_item_t item = *bt; | |
if(item && item->lhs) { | |
item->lhs->parent = item->parent; | |
item->parent = item->lhs; | |
*bt = item->lhs; | |
if(item->lhs->rhs) | |
item->lhs->rhs->parent = item; | |
item->lhs = item->lhs->rhs; | |
((bt_item_t)*bt)->rhs = item; | |
} | |
} | |
void | |
bt_rotate_left(void** bt) { | |
bt_item_t item = *bt; | |
if(item && item->rhs) { | |
item->rhs->parent = item->parent; | |
item->parent = item->rhs; | |
*bt = item->rhs; | |
if(item->rhs->lhs) | |
item->rhs->lhs->parent = item; | |
item->rhs = item->rhs->lhs; | |
((bt_item_t)*bt)->lhs = item; | |
} | |
} | |
unsigned int | |
bt_unbalance(void** bt) { | |
unsigned int ret = 0; | |
bt_item_t item = *bt; | |
if(!item) | |
goto bail; | |
while(item->lhs) { | |
bt_rotate_right(bt); | |
item = *bt; | |
ret++; | |
} | |
ret += bt_unbalance((void**)&item->rhs); | |
bail: | |
return ret; | |
} | |
unsigned int | |
bt_splay(void** bt, void* root) { | |
unsigned int ret = 0; | |
bt_item_t item = root; | |
if(*bt==root) | |
goto bail; | |
while((item!=*bt) && item && item->parent&& item->parent->parent) { | |
void** pivot; | |
if(item->parent->parent->lhs==item->parent) | |
pivot=(void**)&item->parent->parent->lhs; | |
else | |
pivot=(void**)&item->parent->parent->rhs; | |
if(item->parent->lhs==item) | |
bt_rotate_right(pivot); | |
else | |
bt_rotate_left(pivot); | |
ret++; | |
} | |
if(*bt!=root) { | |
if(((bt_item_t)*bt)->lhs==root) | |
bt_rotate_right(bt); | |
else | |
bt_rotate_left(bt); | |
ret++; | |
} | |
assert(*bt==root); | |
bail: | |
return ret; | |
} | |
int | |
bt_get_balance(void* node) { | |
int ret = 0; | |
int root_index = 0; | |
bt_item_t iter = bt_first(node); | |
const bt_item_t end = bt_next(bt_last(node)); | |
for(;iter!=end;iter=bt_next(iter)) { | |
if(iter==node) | |
root_index = ret; | |
ret++; | |
} | |
ret /= 2; | |
ret -= root_index; | |
return ret; | |
} | |
unsigned int | |
bt_rebalance(void** bt) { | |
unsigned int ret = 0; | |
bt_item_t iter = bt_first(*bt); | |
bt_item_t median = iter; | |
const bt_item_t end = bt_next(bt_last(*bt)); | |
if(!iter) | |
goto bail; | |
// Find the median node. | |
while(iter!=end) { | |
iter = bt_next(iter); | |
if(iter==end) | |
break; | |
iter = bt_next(iter); | |
median = bt_next(median); | |
} | |
// Splay the tree so that the median node is at the root. | |
ret += bt_splay(bt,median); | |
// Rinse and repeat on both child branches. | |
iter = *bt; | |
ret += bt_rebalance((void**)&iter->lhs); | |
ret += bt_rebalance((void**)&iter->rhs); | |
bail: | |
return ret; | |
} | |
/* -------------------------------------------------------------------------- */ | |
#if BTREE_SELF_TEST | |
#include <stdlib.h> | |
#include <string.h> | |
static int nodes_alive = 0; | |
struct self_test_node_s { | |
struct bt_item_s item; | |
char* name; | |
}; | |
typedef struct self_test_node_s *self_test_node_t; | |
void | |
self_test_node_delete(self_test_node_t item, void* context) { | |
free(item->name); | |
memset(item, 0, sizeof(*item)); | |
free(item); | |
// Decrement total node count. | |
(*(int*)context)--; | |
} | |
bt_compare_result_t | |
self_test_node_compare( | |
self_test_node_t lhs, | |
self_test_node_t rhs, | |
void* context | |
) { | |
(void)context; // This parameter is not used. Supress warning. | |
if(lhs->name == rhs->name) | |
return 0; | |
if(!lhs->name) | |
return 1; | |
if(!rhs->name) | |
return -1; | |
return strcmp(lhs->name, rhs->name); | |
} | |
bt_compare_result_t | |
self_test_node_compare_cstr( | |
self_test_node_t lhs, | |
const char* rhs, | |
void* context | |
) { | |
(void)context; // This parameter is not used. Supress warning. | |
if(lhs->name == rhs) | |
return 0; | |
if(!lhs->name) | |
return 1; | |
if(!rhs) | |
return -1; | |
return strcmp(lhs->name, rhs); | |
} | |
void | |
forward_traversal_test(self_test_node_t root) { | |
int j = 0; | |
self_test_node_t iter; | |
printf("Forward traversal test..."); | |
fflush(stdout); | |
for(iter = bt_first(root); iter; iter = bt_next(iter)) { | |
j++; | |
if(nodes_alive < j) { | |
printf("Bad node count in forward traversal, too many nodes!\n"); | |
exit(-1); | |
} | |
} | |
if(nodes_alive != j) { | |
printf("Bad node count in forward traversal, not enough nodes!\n"); | |
exit(-1); | |
} | |
printf("OK\n"); | |
} | |
void | |
reverse_traversal_test(self_test_node_t root) { | |
int j = 0; | |
self_test_node_t iter; | |
printf("Reverse traversal test..."); | |
fflush(stdout); | |
for(iter = bt_last(root); iter; iter = bt_prev(iter)) { | |
j++; | |
if(nodes_alive < j) { | |
printf("Bad node count in forward traversal.\n"); | |
exit(-1); | |
} | |
} | |
if(nodes_alive != j) { | |
printf("Bad node count in reverse traversal.\n"); | |
exit(-1); | |
} | |
printf("OK\n"); | |
} | |
int | |
main(void) { | |
int ret = 0; | |
self_test_node_t root = NULL; | |
unsigned char c = 0; | |
int i; | |
// Insert in pseudo random order. Here we are using a very simple | |
// linear congruential generator with a=97, c=101, and m=2^8. It | |
// will produce a somewhat randomish distribution of numbers between | |
// 0 and 255. If you would like to learn more about these types of | |
// pseudo random number generators, see wikipedia: | |
// | |
// * <http://en.wikipedia.org/wiki/Linear_congruential_generator> | |
// | |
again: | |
printf("Inserting nodes in pseudo random order.\n"); | |
for(c = c * 97 + 101; c; c = c * 97 + 101) { | |
self_test_node_t new_node = calloc(sizeof(struct self_test_node_s), | |
1); | |
asprintf(&new_node->name, "item_%d", c); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
} | |
printf("Inserted %d nodes.\n", (int)bt_count((void**)&root)); | |
if(nodes_alive != (int)bt_count((void**)&root)) { | |
printf("error: Bad node count.\n"); | |
ret++; | |
} | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
bt_find((void**)&root, "item_1", &self_test_node_compare_cstr, &nodes_alive); | |
printf("Removing nodes in pseudo random order.\n"); | |
for(c = 4 * 97 + 101; c!=4; c = c * 97 + 101) { | |
char* name = NULL; | |
asprintf(&name, "item_%d", (c==0)?4:c); | |
if(!bt_remove( | |
(void**)&root, | |
name, | |
(bt_compare_func_t)&self_test_node_compare_cstr, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
)) { | |
printf("error: REMOVE FAILED FOR %d\n",c); | |
ret++; | |
} | |
free(name); | |
if(nodes_alive != (int)bt_count((void**)&root)) { | |
printf("error: Bad node count.\n"); | |
ret++; | |
break; | |
} | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
} | |
if(nodes_alive) { | |
printf("error: Bad node count, should be zero.\n"); | |
ret++; | |
} | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
printf("Inserting more nodes in pseudo random order.\n"); | |
for(c = 5 * 97 + 101; c; c = c * 97 + 101) { | |
self_test_node_t new_node = calloc(sizeof(struct self_test_node_s), | |
1); | |
asprintf(&new_node->name, "item_%d", c); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
} | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
// Insert in sequential order. | |
printf("Inserting nodes in sequential order.\n"); | |
for(i = 0; i != 255; i++) { | |
self_test_node_t new_node = | |
calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "item_%d", i); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
} | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
i = bt_unbalance((void**)&root); | |
printf("Unbalance operation took %u rotations\n", i); | |
printf(" * balance = %d\n",bt_get_balance(root)); | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
if(bt_get_balance(root)) { | |
printf( | |
"error: Tree doesn't seem balanced even after rebalancing. " | |
"balance = %d\n", | |
bt_get_balance(root) | |
); | |
ret++; | |
} | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
if(i != 0) { | |
printf( | |
"error: Rebalance operation should have been trivial, " | |
"but did %d rotations anyway.\n", | |
i | |
); | |
ret++; | |
} | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
// Cleanup. | |
printf("Removing all nodes...\n"); | |
while(root) | |
bt_remove( | |
(void**)&root, | |
root, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
bt_find((void**)&root, "item_1", &self_test_node_compare_cstr, &nodes_alive); | |
printf("Adding more nodes...\n"); | |
{ | |
self_test_node_t new_node; | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "proxy"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, ".p"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "device"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "timer"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "async_response"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
new_node = calloc(sizeof(struct self_test_node_s),1); | |
asprintf(&new_node->name, "lots_of_devices"); | |
nodes_alive++; | |
bt_insert( | |
(void**)&root, | |
new_node, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
} | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
i = bt_rebalance((void**)&root); | |
printf("Rebalance operation took %u rotations\n", i); | |
forward_traversal_test(root); | |
reverse_traversal_test(root); | |
// Cleanup. | |
while(root) | |
bt_remove((void**)&root, | |
root, | |
(bt_compare_func_t)&self_test_node_compare, | |
(bt_delete_func_t)&self_test_node_delete, | |
&nodes_alive | |
); | |
// Should have no leaks at this point. | |
if(nodes_alive != 0) { | |
printf("error: nodes_alive = %d, when it should be 0\n", nodes_alive); | |
ret++; | |
} | |
if(ret) | |
printf("Failed with %d errors.\n",ret); | |
else { | |
printf("OK\n"); | |
//goto again; | |
} | |
return ret; | |
} | |
#endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file btree.h | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
*/ | |
#ifndef __BTREE_HEADER__ | |
#define __BTREE_HEADER__ 1 | |
#if !defined(__BEGIN_DECLS) || !defined(__END_DECLS) | |
#if defined(__cplusplus) | |
#define __BEGIN_DECLS extern "C" { | |
#define __END_DECLS \ | |
} | |
#else | |
#define __BEGIN_DECLS | |
#define __END_DECLS | |
#endif | |
#endif | |
#include <stdbool.h> | |
#include <stdio.h> // For ssize_t | |
__BEGIN_DECLS | |
struct bt_item_s; | |
typedef struct bt_item_s *bt_item_t; | |
struct bt_item_s { | |
bt_item_t lhs; | |
bt_item_t rhs; | |
bt_item_t parent; | |
}; | |
typedef signed char bt_compare_result_t; | |
typedef bt_compare_result_t (*bt_compare_func_t)(const void* lhs, | |
const void* rhs, void* context); | |
typedef void (*bt_delete_func_t)(void* item, void* context); | |
//! Inserts the given item into the tree. | |
extern int bt_insert( | |
void** bt, | |
void* item, | |
bt_compare_func_t compare_func, | |
bt_delete_func_t delete_func, | |
void* context); | |
//! Finds and returns a node matching the given criteria. | |
extern void* bt_find( | |
void*const* bt, | |
const void* item, | |
bt_compare_func_t compare_func, | |
void* context); | |
//! Removes the given item from the tree, if present. | |
extern bool bt_remove( | |
void** bt, | |
void* item, | |
bt_compare_func_t compare_func, | |
bt_delete_func_t delete_func, | |
void* context); | |
//! Finds the left-most node in the subtree described by item. | |
extern void* bt_first(void* item); | |
//! Finds the right-most node in the subtree described by item. | |
extern void* bt_last(void* item); | |
//! Returns the next node in the tree, or NULL the given item is the last (right-most) node in the tree. | |
//! Performs an in-order depth-first traversal. | |
extern void* bt_next(void* item); | |
//! Returns the previous node in the tree, or NULL the given item is the first (left-most) node in the tree. | |
//! Performs a reverse-order depth-first traversal. | |
extern void* bt_prev(void* item); | |
//! Traverses the given tree to determine the number of nodes it contains. | |
extern size_t bt_count(void*const* bt); | |
extern int bt_get_balance(void* node); | |
extern void bt_rotate_left(void** pivot); | |
extern void bt_rotate_right(void** pivot); | |
extern unsigned int bt_rebalance(void** bt); | |
extern unsigned int bt_unbalance(void** bt); | |
extern unsigned int bt_splay(void** bt, void* root); | |
__END_DECLS | |
#endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file fgetln.h | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2012-10-24. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
** | |
** ------------------------------------------------------------------- | |
** | |
** This is a simple implementation of the BSD function `fgetln()`, | |
** for use on operating systems which do not have a copy. | |
** | |
** Man page URL: <http://www.openbsd.org/cgi-bin/man.cgi?query=fgetln> | |
** | |
** NOTE: This implementation is *NOT* thread safe! | |
*/ | |
#include <stdio.h> | |
#if !defined(HAVE_FGETLN) | |
#define HAVE_FGETLN (__DARWIN_C_LEVEL>=__DARWIN_C_FULL) | |
#endif | |
#if !defined(fgetln) && !HAVE_FGETLN | |
static char * | |
fgetln_(FILE *stream, size_t *len) { | |
static char* linep = NULL; | |
static size_t linecap = 0; | |
ssize_t length = getline(&linep,&linecap,stream); | |
if(length==-1) { | |
free(linep); | |
linep = NULL; | |
linecap = 0; | |
length = 0; | |
} | |
if(len) | |
*len = length; | |
return linep; | |
} | |
#define fgetln fgetln_ | |
#endif | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file ll.h | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
*/ | |
#ifndef __LL_HEADER__ | |
#define __LL_HEADER__ 1 | |
#if !defined(__BEGIN_DECLS) || !defined(__END_DECLS) | |
#if defined(__cplusplus) | |
#define __BEGIN_DECLS extern "C" { | |
#define __END_DECLS \ | |
} | |
#else | |
#define __BEGIN_DECLS | |
#define __END_DECLS | |
#endif | |
#endif | |
#include <stdbool.h> | |
#if LL_DEBUG | |
#include <assert.h> | |
#define LL_ASSERT(x) assert(x) | |
#else | |
#define LL_ASSERT(x) do { } while(0) | |
#endif | |
__BEGIN_DECLS | |
struct ll_item_s; | |
typedef struct ll_item_s *ll_item_t; | |
struct ll_item_s { | |
ll_item_t next; | |
ll_item_t prev; | |
}; | |
typedef int ll_compare_result_t; | |
typedef ll_compare_result_t (*ll_compare_func_t)(const void* lhs, | |
const void* rhs, void* context); | |
static inline void* | |
ll_last( | |
void* item | |
) { | |
ll_item_t iter = item; | |
if(iter) | |
while(iter->next) { | |
iter = iter->next; | |
} | |
return iter; | |
} | |
static inline bool | |
ll_verify(void* item) { | |
int ret = 0; | |
ll_item_t item_ = item; | |
if(item) { | |
while(item_->prev) | |
item_ = item_->prev; | |
for(; item_->next; item_ = item_->next) | |
ret++; | |
for(; item_->prev; item_ = item_->prev) | |
ret--; | |
} | |
return ret == 0; | |
} | |
static inline void | |
ll_insert_after( | |
void* where, void* item | |
) { | |
ll_item_t const location_ = where; | |
ll_item_t const item_ = item; | |
LL_ASSERT(ll_verify(where)); | |
item_->prev = location_; | |
if((item_->next = location_->next)) | |
item_->next->prev = item_; | |
location_->next = item_; | |
LL_ASSERT(ll_verify(where)); | |
} | |
static inline void | |
ll_insert( | |
void* where, void* item | |
) { | |
ll_item_t const location_ = where; | |
ll_item_t const item_ = item; | |
LL_ASSERT(ll_verify(where)); | |
item_->next = location_; | |
item_->prev = location_->prev; | |
location_->prev = item; | |
if(item_->prev) | |
item_->prev->next = item_; | |
LL_ASSERT(ll_verify(item)); | |
} | |
static inline void | |
ll_prepend( | |
void** list, void* item | |
) { | |
ll_insert(*list, item); | |
*list = item; | |
LL_ASSERT(ll_verify(*list)); | |
} | |
static inline void | |
ll_sorted_insert( | |
void** list, void* item, ll_compare_func_t compare_func, void* context | |
) { | |
ll_item_t location_ = *list; | |
LL_ASSERT(ll_verify(location_)); | |
if(location_) { | |
while(compare_func(item, location_, context) >= 0) { | |
LL_ASSERT(ll_verify(location_)); | |
if(location_->next) { | |
location_ = location_->next; | |
} else { | |
// We are at the end of the list, | |
// so go ahead and add us to the end. | |
ll_insert_after(location_, item); | |
return; | |
} | |
} | |
if(location_!=*list) | |
ll_insert(location_,item); | |
else | |
ll_prepend(list,item); | |
} else { | |
*list = item; | |
} | |
LL_ASSERT(ll_verify(*list)); | |
} | |
static inline void | |
ll_remove( | |
void** list, void* item | |
) { | |
ll_item_t const item_ = item; | |
LL_ASSERT(ll_verify(*list)); | |
if(item_->prev) | |
item_->prev->next = item_->next; | |
if(item_->next) | |
item_->next->prev = item_->prev; | |
if(*list == item_) | |
*list = item_->next; | |
LL_ASSERT(ll_verify(*list)); | |
} | |
static inline void* | |
ll_pop( | |
void** list | |
) { | |
void* item = *list; | |
ll_remove(list,item); | |
return item; | |
} | |
static inline void | |
ll_push( | |
void** list, void* item | |
) { | |
if(*list) | |
ll_insert_after(ll_last(*list),item); | |
else | |
*list = item; | |
LL_ASSERT(ll_verify(*list)); | |
} | |
static inline size_t | |
ll_count(void* item) { | |
size_t ret = 0; | |
ll_item_t item_ = item; | |
for(; item_; item_ = item_->next) | |
ret++; | |
return ret; | |
} | |
__END_DECLS | |
#endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file url-helpers.c | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
** | |
** See <http://www.deepdarc.com/> for other cool stuff. | |
*/ | |
#include <ctype.h> | |
#include <string.h> | |
#include "assert-macros.h" | |
#include "url-helpers.h" | |
#ifdef __SDCC | |
#include <malloc.h> | |
#endif | |
static bool | |
isurlchar(char src_char) { | |
return isalnum(src_char) | |
|| (src_char == '$') | |
|| (src_char == '-') | |
|| (src_char == '_') | |
|| (src_char == '.') | |
|| (src_char == '+') | |
|| (src_char == '!') | |
|| (src_char == '*') | |
|| (src_char == '\'') | |
|| (src_char == '(') | |
|| (src_char == ')') | |
|| (src_char == ','); | |
} | |
#if __AVR__ | |
#include <avr/pgmspace.h> | |
static char int_to_hex_digit(uint8_t x) { | |
return pgm_read_byte_near(PSTR( | |
"0123456789ABCDEF") + (x & 0xF)); | |
} | |
#else | |
static char int_to_hex_digit(uint8_t x) { | |
return "0123456789ABCDEF"[x & | |
0xF]; | |
} | |
#endif | |
size_t | |
url_encode_cstr( | |
char *dest, const char*src, size_t max_size | |
) { | |
size_t ret = 0; | |
if(!max_size--) | |
return 0; | |
while(true) { | |
const char src_char = *src++; | |
if(src_char==0) | |
break; | |
if(max_size==0) { | |
ret++; | |
break; | |
} | |
if(isurlchar(src_char)) { | |
*dest++ = src_char; | |
ret++; | |
max_size--; | |
} else if(src_char == ' ') { | |
*dest++ = '+'; // Stupid legacy space encoding. | |
ret++; | |
max_size--; | |
} else { | |
if(max_size < 3) { | |
// Too small for the next character. | |
ret++; | |
break; | |
} | |
*dest++ = '%'; | |
*dest++ = int_to_hex_digit(src_char >> 4); | |
*dest++ = int_to_hex_digit(src_char & 0xF); | |
ret += 3; | |
max_size -= 3; | |
} | |
} | |
*dest = 0; | |
return ret; | |
} | |
static char | |
hex_digit_to_int(char c) { | |
if(c>='0' && c<='9') | |
return c-'0'; | |
if(c>='A' && c<='F') | |
return 10+c-'A'; | |
if(c>='a' && c<='f') | |
return 10+c-'a'; | |
return 0; | |
} | |
size_t | |
url_decode_str( | |
char *dest, | |
size_t max_size, | |
const char* src, // Length determined by src_len. | |
size_t src_len | |
) { | |
size_t ret = 0; | |
if(!max_size--) | |
return 0; | |
while(src_len--) { | |
const char src_char = *src++; | |
if(!src_char) | |
break; | |
if(!max_size) { | |
ret++; | |
break; | |
} | |
if((src_char == '%') | |
&& (src_len>=2) | |
&& src[0] | |
&& src[1] | |
) { | |
*dest++ = (hex_digit_to_int(src[0]) << 4) + hex_digit_to_int( | |
src[1]); | |
src += 2; | |
src_len -= 2; | |
} else if(src_char == '+') { | |
*dest++ = ' '; // Stupid legacy space encoding. | |
} else { | |
*dest++ = src_char; | |
} | |
ret++; | |
max_size--; | |
} | |
*dest = 0; | |
return ret; | |
} | |
size_t | |
url_decode_cstr( | |
char *dest, | |
const char*src, | |
size_t max_size | |
) { | |
size_t ret = 0; | |
#if DEBUG | |
char*const dest_check = dest; | |
#endif | |
if(!max_size--) | |
goto bail; | |
while(true) { | |
const char src_char = *src++; | |
if(!src_char) { | |
break; | |
} | |
if(!max_size) { | |
ret++; | |
break; | |
} | |
if((src_char == '%') | |
&& src[0] | |
&& src[1] | |
) { | |
*dest++ = (hex_digit_to_int(src[0]) << 4) + hex_digit_to_int( | |
src[1]); | |
src += 2; | |
} else if(src_char == '+') { | |
*dest++ = ' '; // Stupid legacy space encoding. | |
} else { | |
*dest++ = src_char; | |
} | |
ret++; | |
max_size--; | |
} | |
bail: | |
*dest = 0; | |
#if DEBUG | |
assert(strlen(dest_check)==ret); | |
#endif | |
return ret; | |
} | |
void | |
url_decode_cstr_inplace(char *str) { | |
url_decode_cstr(str, str, -1); | |
} | |
size_t | |
url_form_next_value( | |
char** form_string, char** key, char** value, bool decodeValue | |
) { | |
size_t bytes_parsed = 0; | |
char c = **form_string; | |
char* v = NULL; | |
if(!c) { | |
*key = NULL; | |
goto bail; | |
} | |
*key = *form_string; | |
while(true) { | |
c = **form_string; | |
if(!c) | |
goto bail; | |
if(c == '=') | |
break; | |
bytes_parsed++; | |
if((c == ';') || (c == '&')) { | |
*(*form_string)++ = 0; | |
goto bail; | |
} | |
(*form_string)++; | |
} | |
// Zero terminate the key. | |
if(value) | |
**form_string = 0; | |
(*form_string)++; | |
bytes_parsed++; | |
v = *form_string; | |
while(true) { | |
c = **form_string; | |
if(!c || (c == ';') || (c == '&')) | |
break; | |
bytes_parsed++; | |
(*form_string)++; | |
} | |
// Zero terminate the value | |
if(*form_string[0]) { | |
*(*form_string)++ = 0; | |
bytes_parsed++; | |
} | |
bail: | |
if(v && decodeValue) | |
url_decode_cstr_inplace(v); | |
if(value) | |
*value = v; | |
return bytes_parsed; | |
} | |
size_t | |
url_path_next_component( | |
char** path_string, char** component | |
) { | |
size_t bytes_parsed = 0; | |
char c = **path_string; | |
if(!c) { | |
*component = NULL; | |
goto bail; | |
} | |
*component = *path_string; | |
while(true) { | |
c = **path_string; | |
if(!c || (c == '/')) | |
break; | |
bytes_parsed++; | |
(*path_string)++; | |
} | |
// Zero terminate the value | |
if(*path_string[0]) { | |
*(*path_string)++ = 0; | |
bytes_parsed++; | |
} | |
bail: | |
if(*component) | |
url_decode_cstr_inplace(*component); | |
return bytes_parsed; | |
} | |
int | |
url_parse( | |
char* uri, | |
char** protocol, | |
char** username, // Not yet supported: will be skipped if present. | |
char** password, // Not yet supported: will be skipped if present. | |
char** host, | |
char** port, | |
char** path, | |
char** query | |
) { | |
int bytes_parsed = 0; | |
char tmp; | |
require_string(uri, bail, "NULL uri parameter"); | |
if(protocol) | |
*protocol = uri; | |
while(*uri != ':') { | |
require_string(*uri, bail, "unexpected end of string"); | |
uri++; | |
bytes_parsed++; | |
} | |
// Zero terminate the protocol; | |
*uri++ = 0; | |
bytes_parsed++; | |
require_string(*uri, bail, "unexpected end of string"); | |
if(uri[0] == '/' && uri[1] == '/') { | |
char* addr_end; | |
char* addr_begin; | |
bool got_port = false; | |
// Contains a hostname. Parse it. | |
uri += 2; | |
bytes_parsed += 2; | |
addr_begin = uri; | |
while( (tmp=*uri) != '/' | |
&& ( isurlchar(tmp) | |
|| (tmp == '[') | |
|| (tmp == ']') | |
|| (tmp == ':') | |
|| (tmp == '@') | |
) | |
) { | |
uri++; | |
bytes_parsed++; | |
} | |
addr_end = uri - 1; | |
if(*uri) { | |
*uri++ = 0; | |
bytes_parsed++; | |
} | |
for(; | |
(addr_end >= addr_begin) && (*addr_end != '@') && | |
(*addr_end != '['); | |
addr_end--) { | |
if(*addr_end == ']') { | |
*addr_end = 0; | |
got_port = true; | |
} else if(!got_port && (*addr_end == ':')) { | |
if(port) | |
*port = addr_end + 1; | |
*addr_end = 0; | |
got_port = true; | |
} | |
} | |
if(host) | |
*host = addr_end + 1; | |
} | |
if(path) | |
*path = uri; | |
// Move to the end of the path. | |
while( ((tmp=*uri) != '#') | |
&& (tmp != '?') | |
&& ( isurlchar(tmp) | |
|| (tmp == '[') | |
|| (tmp == ']') | |
|| (tmp == ':') | |
|| (tmp == '/') | |
|| (tmp == '=') | |
|| (tmp == '&') | |
|| (tmp == '%') | |
) | |
) { | |
uri++; | |
bytes_parsed++; | |
} | |
// Handle query component | |
if(*uri == '?') { | |
*uri++ = 0; | |
bytes_parsed++; | |
if(query) | |
*query = uri; | |
// Move to the end of the query. | |
while( ((tmp=*uri) != '#') | |
&& ( isurlchar(tmp) | |
|| (tmp == '[') | |
|| (tmp == ']') | |
|| (tmp == ':') | |
|| (tmp == '/') | |
|| (tmp == '=') | |
|| (tmp == '&') | |
|| (tmp == '%') | |
|| (tmp == ';') | |
) | |
) { | |
uri++; | |
bytes_parsed++; | |
} | |
} | |
// Zero terminate | |
if(*uri) { | |
*uri = 0; | |
bytes_parsed++; | |
} | |
bail: | |
return bytes_parsed; | |
} | |
bool | |
url_is_absolute(const char* uri) { | |
bool ret = false; | |
int bytes_parsed = 0; | |
require(uri, bail); | |
while(*uri && isalpha(*uri) && (*uri != ':')) { | |
require(*uri, bail); | |
uri++; | |
bytes_parsed++; | |
} | |
if(bytes_parsed && *uri == ':') | |
ret = true; | |
bail: | |
return ret; | |
} | |
bool | |
url_is_root(const char* url) { | |
bool ret = false; | |
require(url, bail); | |
require(isalpha(url[0]),bail); | |
if(url_is_absolute(url)) { | |
while(*url && isalpha(*url) && (*url != ':')) { | |
require(*url, bail); | |
url++; | |
} | |
if( (url[0] != ':') | |
|| (url[1] != '/') | |
|| (url[2] != '/') | |
) goto bail; | |
url+=3; | |
while(*url && (*url != '/')) { | |
url++; | |
} | |
} | |
while(url[0]=='/' && url[1]=='/') url++; | |
ret = (url[0]==0) || ((url[0]=='/') && (url[1]==0)); | |
bail: | |
return ret; | |
} | |
//!< Used to identify IPv6 address strings | |
bool | |
string_contains_colons(const char* str) { | |
if(!str) | |
return false; | |
for(; (*str != ':') && *str; str++) ; | |
return *str == ':'; | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* @file url-helpers.h | |
** @author Robert Quattlebaum <darco@deepdarc.com> | |
** | |
** Originally published 2010-8-31. | |
** | |
** This file was written by Robert Quattlebaum <darco@deepdarc.com>. | |
** | |
** This work is provided as-is. Unless otherwise provided in writing, | |
** Robert Quattlebaum makes no representations or warranties of any | |
** kind concerning this work, express, implied, statutory or otherwise, | |
** including without limitation warranties of title, merchantability, | |
** fitness for a particular purpose, non infringement, or the absence | |
** of latent or other defects, accuracy, or the present or absence of | |
** errors, whether or not discoverable, all to the greatest extent | |
** permissible under applicable law. | |
** | |
** To the extent possible under law, Robert Quattlebaum has waived all | |
** copyright and related or neighboring rights to this work. This work | |
** is published from the United States. | |
** | |
** I, Robert Quattlebaum, dedicate any and all copyright interest in | |
** this work to the public domain. I make this dedication for the | |
** benefit of the public at large and to the detriment of my heirs and | |
** successors. I intend this dedication to be an overt act of | |
** relinquishment in perpetuity of all present and future rights to | |
** this code under copyright law. In jurisdictions where this is not | |
** possible, I hereby release this code under the Creative Commons | |
** Zero (CC0) license. | |
** | |
** * <http://creativecommons.org/publicdomain/zero/1.0/> | |
** | |
** See <http://www.deepdarc.com/> for other cool stuff. | |
*/ | |
#ifndef __URL_HELPERS_H__ | |
#define __URL_HELPERS_H__ 1 | |
#include <stdbool.h> | |
#include <stddef.h> | |
#include <stdint.h> | |
#define URL_HELPERS_MAX_URL_COMPONENTS (15) | |
#define MAX_URL_SIZE (256) | |
/*! Perfoms a URL encoding of the given string. | |
** @returns Number of bytes in encoded string | |
*/ | |
extern size_t url_encode_cstr( | |
char *dest, | |
const char* src, // Must be zero-terminated. | |
size_t dest_max_size | |
); | |
extern size_t url_decode_str( | |
char *dest, | |
size_t dest_max_size, | |
const char* src, // Length determined by src_len. | |
size_t src_len | |
); | |
/*! Perfoms a URL decoding of the given string. | |
** @returns Number of bytes in decoded string | |
*/ | |
extern size_t url_decode_cstr( | |
char *dest, | |
const char* src, // Must be zero-terminated. | |
size_t dest_max_size | |
); | |
extern void url_decode_cstr_inplace(char *str); | |
extern size_t url_form_next_value( | |
char** form_string, | |
char** key, | |
char** value, | |
bool decodeValue | |
); | |
extern size_t url_path_next_component( | |
char** path_string, char** component | |
); | |
extern int url_parse( | |
char* url, | |
char** protocol, | |
char** username, | |
char** password, | |
char** host, | |
char** port, | |
char** path, | |
char** query | |
); | |
extern bool url_is_absolute(const char* url); | |
extern bool url_is_root(const char* url); | |
#if defined(__SDCC) | |
#define path_is_absolute(path) ((path)[0] == '/') | |
#else | |
inline static bool path_is_absolute(const char* path) { return path[0] == '/'; } | |
#endif | |
extern bool string_contains_colons(const char* str); | |
#endif // __URL_HELPERS_H__ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment