JudyHS(3)

📦
version 1.0.5 · 14 versions
, in centos-stream 9

💖 JudyHS — the manual page, but make it make sense 💖

okay bestie, so this is JudyHS(3) from the Library Functions Manual — it lives in section 3 with all the other C library calls, and it's genuinely one of the coolest data structures you'll ever meet. no cap. let's get into it 🫶

✨ NAME ✨

JudyHS macros — a C library for creating and accessing a dynamic array, using an array-of-bytes of Length as an Index and a word as a Value. 💅

🌸 SYNOPSIS 🌸

cc [flags] sourcefiles -lJudy

#include <Judy.h>

Word_t  * PValue;                           // JudyHS array element
int       Rc_int;                           // return flag
Word_t    Rc_word;                          // full word return value
Pvoid_t   PJHSArray = (Pvoid_t) NULL;       // initialize JudyHS array
uint8_t * Index;                            // array-of-bytes pointer
Word_t    Length;                           // number of bytes in Index

JHSI( PValue,  PJHSArray, Index, Length);   // JudyHSIns()
JHSD( Rc_int,  PJHSArray, Index, Length);   // JudyHSDel()
JHSG( PValue,  PJHSArray, Index, Length);   // JudyHSGet()
JHSFA(Rc_word, PJHSArray);                  // JudyHSFreeArray()

like, literally all the boilerplate is right there, you just copy it and go ✨

🦋 DESCRIPTION 🦋

So a JudyHS array is basically the equivalent of an array of word-sized value/pointers. An Index is a pointer to an array-of-bytes of a specified length: Length. And here's the iconic part — instead of using a null terminated string, this difference from JudySL(3) lets your strings contain all the bits, specifically the null character. yes ma'am, the null char gets to exist. 🙈

This new addition (May 2004, so it's vintage but it still ate) to the Judy arrays is a hybrid using the best capabilities of hashing and Judy methods. And the killer feature? JudyHS does not have a poor performance case where knowledge of the hash algorithm can be used to degrade the performance. nobody can sabotage you. main character energy honestly. 👑

Now because JudyHS is based on a hash method, Indexes are not stored in any particular order. so like, don't expect a nice sorted lineup. Therefore the JudyHSFirst(), JudyHSNext(), JudyHSPrev() and JudyHSLast() neighbor search functions are not practical — they just don't have a vibe here. 😭 The Length of each array-of-bytes can be from 0 to the limits of malloc() (about 2GB).

The hallmark of JudyHS is speed with scalability, but memory efficiency is excellent too. The speed is very competitive with the best hashing methods. The memory efficiency is similar to a linked list of the same Indexes and Values. JudyHS is designed to scale from 0 to billions of Indexes. billions, bestie. 🌈

A JudyHS array is allocated with a NULL pointer:

Pvoid_t PJHSArray = (Pvoid_t) NULL;

And since the macro forms of the API have a simpler error handling interface than the equivalent functions, they are the preferred way to use JudyHS. macros slay, fr fr. 🎀

💜 JHSI(PValue, PJHSArray, Index, Length) — a.k.a. JudyHSIns() 💜

Given a pointer to a JudyHS array (PJHSArray), insert an Index string of length: Length and a Value into the JudyHS array: PJHSArray. If the Index is successfully inserted, the Value is initialized to 0. If the Index was already present, the Value is not modified. (iconic "first one wins" behaviour 🫶)

Return PValue pointing to Value. Your program should use this pointer to read or modify the Value, for example:

Value = *PValue;
*PValue = 1234;
⚠️ Note: JHSI() and JHSD can reorganize the JudyHS array. Therefore, pointers returned from previous JudyHS calls become invalid and must be re-acquired (using JHSG()). so like, don't hoard your pointers, they go stale. re-acquire, diva. 💀

🍓 JHSD(Rc_int, PJHSArray, Index, Length) — a.k.a. JudyHSDel() 🍓

Given a pointer to a JudyHS array (PJHSArray), delete the specified Index along with the Value from the JudyHS array.

Return Rc_int set to 1 if successfully removed from the array. Return Rc_int set to 0 if Index was not present. bye girl, or... bye nothing. 😭

🧚 JHSG(PValue, PJHSArray, Index, Length) — a.k.a. JudyHSGet() 🧚

Given a pointer to a JudyHS array (PJHSArray), find Value associated with Index.

Return PValue pointing to Index's Value. Return PValue set to NULL if the Index was not present. no notes. 🌸

⭐ JHSFA(Rc_word, PJHSArray) — a.k.a. JudyHSFreeArray() ⭐

Given a pointer to a JudyHS array (PJHSArray), free the entire array.

Return Rc_word set to the number of bytes freed and PJHSArray set to NULL. the whole thing, gone, clean slate, we love a tidy exit. ✨

💀 ERRORS 💀

See: Judy_3.htm#ERRORS — that's where the full tea is, go read it bestie.

🔥 EXAMPLES 🔥

Show how to program with the JudyHS macros. This program will print duplicate lines and their line number from stdin. (yes, it's a dupe-finder, and yes it's lowkey iconic 🎀)

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <Judy.h>

//  Compiled:
//  cc -O PrintDupLines.c -lJudy -o PrintDupLines

#define MAXLINE 1000000                 /* max fgets length of line */
uint8_t   Index[MAXLINE];               // string to check

int     // Usage:  PrintDupLines < file
main()
{
    Pvoid_t   PJArray = (PWord_t)NULL;  // Judy array.
    PWord_t   PValue;                   // Judy array element pointer.
    Word_t    Bytes;                    // size of JudyHS array.
    Word_t    LineNumb = 0;             // current line number
    Word_t    Dups = 0;                 // number of duplicate lines

    while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
    {
        LineNumb++;                     // line number

        // store string into array
        JHSI(PValue, PJArray, Index, strlen(Index));
        if (PValue == PJERR)            // See ERRORS section
        {
            fprintf(stderr, "Out of memory -- exit\n");
            exit(1);
        }
        if (*PValue == 0)               // check if duplicate
        {
            Dups++;
            printf("Duplicate lines %lu:%lu:%s", *PValue, LineNumb, Index);
        }
        else
        {
            *PValue = LineNumb;         // store Line number
        }
    }
    printf("%lu Duplicates, free JudyHS array of %lu Lines\n",
                    Dups, LineNumb - Dups);
    JHSFA(Bytes, PJArray);              // free JudyHS array
    printf("JudyHSFreeArray() free'ed %lu bytes of memory\n", Bytes);
    return (0);
}

copy it, compile it, run it on a big file, feel powerful. you're welcome. 💅

👑 AUTHOR 👑

JudyHS was invented and implemented by Doug Baskins after retiring from Hewlett-Packard. retired and then casually invented a whole data structure. that's the flex. we stan. 🫶

🌈 SEE ALSO 🌈

okay that's the whole page, bestie — this was JudyHS(3) from the Library Functions Manual (that's source and version, literally in the JudyHS(3) footer), dated like the rest of the page, so go forth and hash responsibly. mwah 💖🎀✨

📦 where this page comes from