ref: 6813e1071ffc4f451135daa79a928207a63d5e85
parent: 77eabfb31feddd18ecf6fcb2da6bb5b13ae853d0
author: Sigrid Solveig Haflínudóttir <sigrid@ftrv.se>
date: Tue Dec 24 23:24:13 EST 2024
qp tries: clean up a bit
--- a/3rd/fn.c
+++ b/3rd/fn.c
@@ -36,7 +36,7 @@
// Recurse to find either this leaf (*pkey != nil)
// or the next one (*pkey == nil).
Tbitmap b = twigbit(i, *pkey, *plen);
- uint s, m; TWIGOFFMAX(s, m, i, b);
+ uint32_t s, m; TWIGOFFMAX(s, m, i, b);
for(; s < m; s++){if(next_rec(Tbranch_twigs(t)+s, pkey, plen, pval))
return true;
@@ -96,7 +96,7 @@
return nil;
}
Trie *twigs = Tbranch_twigs(p);
- uint m = popcount(Tindex_bitmap(i));
+ uint32_t m = __builtin_popcount(Tindex_bitmap(i));
assert(twigs <= t && t < twigs+m);
if(m == 2){// Move the other twig to the parent branch.
@@ -144,14 +144,14 @@
// twig we choose since the keys are all the same up to this
// index. Note that blindly using twigoff(t, b) can cause
// an out-of-bounds index if it equals twigmax(t).
- uint s = hastwig(i, b) ? twigoff(i, b) : 0;
+ uint32_t s = hastwig(i, b) ? twigoff(i, b) : 0;
t = Tbranch_twigs(t) + s;
}
// Do the keys differ, and if so, where?
- uint off, xor, shf;
+ uint32_t off, xor, shf;
const char *tkey = Tleaf_key(t);
for(off = 0; off <= len; off++){- xor = (byte)key[off] ^ (byte)tkey[off];
+ xor = (uint8_t)key[off] ^ (uint8_t)tkey[off];
if(xor != 0)
goto newkey;
}
@@ -158,8 +158,8 @@
Tset_val(t, val);
return tbl;
newkey:; // We have the branch's byte index; what is its chunk index?
- uint bit = off * 8 + __builtin_clz(xor) + 8 - sizeof(uint) * 8;
- uint qo = bit / 5;
+ uint32_t bit = off * 8 + __builtin_clz(xor) + 8 - sizeof(uint32_t) * 8;
+ uint32_t qo = bit / 5;
off = qo * 5 / 8;
shf = qo * 5 % 8;
// re-index keys with adjusted offset
@@ -197,7 +197,7 @@
return tbl;
growbranch:
assert(!hastwig(i, nb));
- uint s, m; TWIGOFFMAX(s, m, i, nb);
+ uint32_t s, m; TWIGOFFMAX(s, m, i, nb);
twigs = MEM_REALLOC(Tbranch_twigs(t), sizeof(Trie) * (m + 1));
if(twigs == nil)
return nil;
--- a/3rd/fn.h
+++ b/3rd/fn.h
@@ -17,17 +17,14 @@
// You may do anything with this. It has no warranty.
// <http://creativecommons.org/publicdomain/zero/1.0/>
-typedef unsigned char byte;
-typedef unsigned int uint;
+#pragma once
typedef uint32_t Tbitmap;
typedef uint64_t Tindex;
-const char *dump_bitmap(Tbitmap w);
-
#if defined(__plan9__)
-static inline uint
-popcount(Tbitmap w)
+static inline uint32_t
+__builtin_popcount(Tbitmap w)
{w -= (w >> 1) & 0x55555555;
w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
@@ -35,8 +32,6 @@
w = (w * 0x01010101) >> 24;
return(w);
}
-#else
-#define popcount(w) __builtin_popcount(w)
#endif
typedef struct Tbl {@@ -103,8 +98,8 @@
#define Tix_mask(field) ((1ULL << Tix_width_##field) - 1ULL)
-#define Tunmask(field,index) ((uint)(((index) >> Tix_base_##field) \
- & Tix_mask(field)))
+#define Tunmask(field,index) \
+ ((uint32_t)(((index) >> Tix_base_##field) & Tix_mask(field)))
#define Tmaxlen Tix_mask(offset)
@@ -119,18 +114,19 @@
struct dummy
Tindex_get(bool, branch);
-Tindex_get(uint, shift);
-Tindex_get(uint, offset);
+Tindex_get(uint32_t, shift);
+Tindex_get(uint32_t, offset);
Tindex_get(Tbitmap, bitmap);
static inline Tindex
-Tindex_new(uint shift, uint offset, Tbitmap bitmap)
+Tindex_new(uint32_t shift, uint32_t offset, Tbitmap bitmap)
{- uint branch = 1;
- return( Tix_place(branch) |
+ uint32_t branch = 1;
+ return
+ Tix_place(branch) |
Tix_place(shift) |
Tix_place(offset) |
- Tix_place(bitmap) );
+ Tix_place(bitmap) ;
}
static inline Tindex
@@ -147,15 +143,14 @@
// sanity checks!
-#if !defined(__plan9__)
#if !defined(static_assert)
#define static_assert_cat(a,b) a##b
#define static_assert_name(line) static_assert_cat(static_assert_,line)
-#define static_assert(must_be_true,message) \
- static const void *static_assert_name(__LINE__) \
- [must_be_true ? 2 : -1] = { \- message, \
- &static_assert_name(__LINE__) }
+#define static_assert(must_be_true, message) \
+ static const void *static_assert_name(__LINE__) \
+ [must_be_true ? 2 : -1] = { \+ message, \
+ static_assert_name(__LINE__) }
#endif
static_assert(Tix_base_bitmap + Tix_width_bitmap == 64,
@@ -175,22 +170,21 @@
// 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
// | | | | | | | | |
// shift=0 shift=5 shift=2 shift=7 shift=4 shift=1 shift=6 shift=3
-#endif
-static inline byte
-knybble(const char *key, uint off, uint shift)
+static inline uint8_t
+knybble(const char *key, uint32_t off, uint32_t shift)
{- uint word = key[off]<<8;
+ uint32_t word = key[off]<<8;
if(word)
word |= key[off+1];
- uint right = 16 - 5 - shift;
+ uint32_t right = 16 - 5 - shift;
return (word >> right) & 0x1FU;
}
-static inline byte
+static inline uint8_t
nibble(Tindex i, const char *key, size_t len)
{- uint off = Tindex_offset(i);
+ uint32_t off = Tindex_offset(i);
if(off >= len)
return(0);
else return knybble(key, off, Tindex_shift(i));
@@ -208,13 +202,13 @@
return Tindex_bitmap(i) & bit;
}
-static inline uint
+static inline uint32_t
twigoff(Tindex i, Tbitmap bit)
{- return popcount(Tindex_bitmap(i) & (bit-1));
+ return __builtin_popcount(Tindex_bitmap(i) & (bit-1));
}
#define TWIGOFFMAX(off, max, i, b) do{ \off = twigoff(i, b); \
- max = popcount(Tindex_bitmap(i)); \
+ max = __builtin_popcount(Tindex_bitmap(i)); \
}while(0)
--- a/3rd/tbl.c
+++ b/3rd/tbl.c
@@ -1,4 +1,4 @@
-// Tbl.c: simpler wrappers for core table functions
+// tbl.c: simpler wrappers for core table functions
//
// Written by Tony Finch <dot@dotat.at>
// You may do anything with this. It has no warranty.
--- a/3rd/tbl.h
+++ b/3rd/tbl.h
@@ -1,4 +1,4 @@
-// Tbl.h: an abstract API for tables with string keys.
+// tbl.h: an abstract API for tables with string keys.
//
// Written by Tony Finch <dot@dotat.at>
// You may do anything with this. It has no warranty.